Как правильно хешировать пользовательскую структуру?

Question

В языке C++ есть шаблон хэш-функции по умолчанию std::hash<T> для самых простых типов, таких как std::string, intи т. д. Я полагаю, что эти функции имеют хорошую энтропию и соответствующее распределение случайных величин статистически однородно. Если это не так, давайте сделаем вид, что это так.

Тогда у меня есть структура:

struct CustomType {
  int field1;
  short field2;
  string field3;
  // ...
};

Я хочу хэшировать это, используя отдельные хеши некоторых из его полей, скажем, std::hash(field1) а также std::hash(field2), Оба хэша находятся в наборе возможных значений типа size_t,

Что такое хорошая хеш-функция, которая может объединить оба этих результата и отобразить их обратно size_t?

Answer 1

boost::hash_combine действительно хорош для хеширования различных полей.

Если у вас нет библиотеки повышения, вы можете использовать это:

template <class T>
inline void hash_combine(std::size_t & s, const T & v)
{
  std::hash<T> h;
  s^= h(v) + 0x9e3779b9 + (s<< 6) + (s>> 2);
}

 struct S {
  int field1;
  short field2;
  std::string field3;
  // ...
};

template <class T>
class MyHash;

template<>
struct MyHash<S>
{
    std::size_t operator()(S const& s) const 
    {
        std::size_t res = 0;
       hash_combine(res,s.field1);
       hash_combine(res,s.field2);
       hash_combine(res,s.field3);
        return res;
    }
};

А потом наверное std::unordered_set<S> s;, так далее

Answer 2

boost::hash_combine это то, что может помочь вам здесь:

namespace std
{
template <>
struct hash<CustomType>
{
    std::size_t operator()(const CustomType& c) const
    {
        std::size_t result = 0;
        boost::hash_combine(result, field1);
        boost::hash_combine(result, field2);
        return result;
    }
};
}

Смотрите документацию здесь.

Answer 3

Более простой подход может заключаться в добавлении метода toString() и его хэшировании.

      struct CustomType {
    int field1;
    short field2;
    std::string field3;
    // ...

    std::string toString() const {
        return std::to_string(field1) + std::to_string(field2) + field3; // + ...
    }

    size_t hash() const {
        return std::hash<std::string>()(toString());
    }

};

Наличие метода toString() также удобно для ведения журнала и отладки.