Как объединить значения хеш-функции в C ++ 0x? - PullRequest
Новая
       22

Как объединить значения хеш-функции в C ++ 0x?

75 голосов
/ 07 апреля 2010

C ++ 0x добавляет hash<...>(...).

Я не смог найти функцию hash_combine, как показано в boost . Какой самый чистый способ реализовать что-то подобное? Возможно, используя C ++ 0x xor_combine?

Ответы [ 4 ]

80 голосов
/ 07 апреля 2010

Ну, просто сделайте это так, как это сделали ребята: 

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
29 голосов
/ 01 июля 2016

Я поделюсь этим здесь, так как это может быть полезно для других, ищущих это решение: начиная с @ KarlvonMoor ответа, вот вариант шаблона с вариадным кодом, который является более кратким в его использовании, если вам нужно объединить несколько значений вместе: 

inline void hash_combine(std::size_t& seed) { }

template <typename T, typename... Rest>
inline void hash_combine(std::size_t& seed, const T& v, Rest... rest) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    hash_combine(seed, rest...);
}

Использование: 

std::size_t h=0;
hash_combine(h, obj1, obj2, obj3);

Первоначально он был написан для реализации макроса variadic, чтобы легко сделать настраиваемые типы хэшируемыми (что я считаю одним из основных применений функции hash_combine): 

#define MAKE_HASHABLE(type, ...) \
    namespace std {\
        template<> struct hash<type> {\
            std::size_t operator()(const type &t) const {\
                std::size_t ret = 0;\
                hash_combine(ret, __VA_ARGS__);\
                return ret;\
            }\
        };\
    }

Использование: 

struct SomeHashKey {
    std::string key1;
    std::string key2;
    bool key3;
};

MAKE_HASHABLE(SomeHashKey, t.key1, t.key2, t.key3)
// now you can use SomeHashKey as key of an std::unordered_map
4 голосов
/ 13 мая 2018

Эту проблему также можно решить с помощью шаблона переменной следующим образом: 

#include <functional>

template <typename...> struct hash;

template<typename T> 
struct hash<T> 
    : public std::hash<T>
{
    using std::hash<T>::hash;
};


template <typename T, typename... Rest>
struct hash<T, Rest...>
{
    inline std::size_t operator()(const T& v, const Rest&... rest) {
        std::size_t seed = hash<Rest...>{}(rest...);
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

Использование: 

#include <string>

int main(int,char**)
{
    hash<int, float, double, std::string> hasher;
    std::size_t h = hasher(1, 0.2f, 2.0, "Hello World!");
}

Конечно, можно создать функцию шаблона, но это может вызвать некоторые неприятности.например, hash("Hallo World!") вычислит хеш-значение по указателю, а не по строке.Вероятно, это причина того, почему в стандарте используется структура.

2 голосов
/ 17 февраля 2019

Несколько дней назад я придумал слегка улучшенную версию этот ответ (требуется поддержка C ++ 17): 

template <typename T, typename... Rest>
void hashCombine(uint& seed, const T& v, Rest... rest)
{
    seed ^= ::qHash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (hashCombine(seed, rest), ...);
}

Код выше лучше с точки зрения генерации кода. В своем коде я использовал функцию qHash из Qt, но также можно использовать любые другие хэши.

...