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

Question

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

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

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

112

c++ c++11 boost hash std

Источник

user99989 07 апр '10 в 07:28

8 ответов

Решение

Я поделюсь этим здесь, так как это может быть полезно для других, ищущих это решение: начиная с ответа @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

49

Источник

user214671 01 июл '16 в 08:46

Мне очень нравится подход C++17 из ответа vt4a2h, однако он страдает от проблемы:Rest передается по значению, тогда как было бы более желательно передавать их по константным ссылкам (что является обязательным, если его можно использовать с типами, предназначенными только для перемещения).

Вот адаптированная версия, которая по-прежнему использует выражение свертки (поэтому для нее требуется C++17 или выше) и используетstd::hash (вместо хеш-функции Qt):

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

Для полноты: все типы, которые будут использоваться с этой версией hash_combineдолжен иметь специализацию шаблона дляhash введен в std пространство имен.

Пример:

namespace std // Inject hash for B into std::
{
    template<> struct hash<B>
    {
        std::size_t operator()(B const& b) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h, b.firstMember, b.secondMember, b.andSoOn);
            return h;
        }
    };
}

Так что тип B в приведенном выше примере также можно использовать в другом типе A, как показано в следующем примере использования:

struct A
{
    std::string mString;
    int mInt;
    B mB;
    B* mPointer;
}

namespace std // Inject hash for A into std::
{
    template<> struct hash<A>
    {
        std::size_t operator()(A const& a) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h,
                a.mString,
                a.mInt,
                a.mB, // calls the template specialization from above for B
                a.mPointer // does not call the template specialization but one for pointers from the standard template library
            );
            return h;
        }
    };
}

10

Источник

user387023 21 авг '19 в 18:38

Несколько дней назад я придумал слегка улучшенную версию этого ответа (требуется поддержка 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, но также можно использовать любые другие хэши.

7

Источник

user3476541 16 фев '19 в 22:29

Ответ на vt4a2h, конечно, хорошо, но использует C++17 раза выражения и не каждый способен переключиться на более новый набор инструменты легко. В приведенной ниже версии используется трюк с расширителем для имитации выражения свертки, и она также работает в C++11 и C++14.

Дополнительно я отметил функцию inline и используйте идеальную пересылку для аргументов вариативного шаблона.

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

Живой пример в Compiler Explorer

6

Источник

user1944004 18 дек '19 в 11:51

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

#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!") будет вычислять значение хеша по указателю, а не по строке. Это, вероятно, причина, почему стандарт использует структуру.

5

Источник

user7637816 13 май '18 в 11:04

Ответ Анри Менке прекрасно работает, но если рассматривать предупреждения как ошибки с, например:

      add_compile_options(-Werror)

GCC 9.3.0 выдаст эту ошибку:

      Test.h:223:67: error: ISO C++ forbids compound-literals [-Werror=pedantic]
  223 |     (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
      |                                                                  ^
cc1plus: all warnings being treated as errors

Мы можем обновить код, чтобы избежать такой ошибки:

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

1

Источник

28 фев '21 в 18:00

Для этого вы можете использовать первую библиотеку C++, которую я разработал:

      #include "rst/stl/hash.h"

struct Point {
  Point(const int x, const int y) : x(x), y(y) {}

  int x = 0;
  int y = 0;
};

bool operator==(const Point lhs, const Point rhs) {
  return (lhs.x == rhs.x) && (lhs.y == rhs.y);
}

namespace std {

template <>
struct hash<Point> {
  size_t operator()(const Point point) const {
    return rst::HashCombine({point.x, point.y});
  }
};

}

1

Источник

user2899779 03 ноя '21 в 05:43

Другие вопросы по тегам c++ c++11 boost hash std

user211359 07 апр '10 в 19:18 2010-04-07 19:18 · Accepted Answer · 2010-04-07 19:18

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

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);
}

120

Источник

user211359 07 апр '10 в 19:18