std::hash вариации объекта с произвольным количеством атрибутов фундаментального типа

Question

Обсуждение:

Допустим, у меня есть struct/class с произвольным количеством атрибутов, которые я хочу использовать в качестве ключа к std::unordered_map например,:

struct Foo {
  int    i;
  double d;
  char   c;
  bool   b;
};

Я знаю, что для этого я должен определить хеш-функтор, например:

struct FooHasher {
  std::size_t operator()(Foo const &foo) const;
};

А затем определить мой std::unordered_map как:

std::unordered_map<Foo, MyValueType, FooHasher> myMap;

Что меня беспокоит, так это то, как определить оператор вызова для FooHasher, Один из способов сделать это, который я тоже предпочитаю, это std::hash, Тем не менее, существуют многочисленные варианты, например:

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)    ^
         std::hash<double>()(foo.d) ^
         std::hash<char>()(foo.c)   ^
         std::hash<bool>()(foo.b);
}

Я также видел следующую схему:

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)           ^
         (std::hash<double>()(foo.d) << 1) ^
         (std::hash<char>()(foo.c)   >> 1) ^
         (std::hash<bool>()(foo.b)   << 1);
}

Я видел также некоторых людей, добавляющих золотое сечение:

std::size_t operator()(Foo const &foo) const {
  return (std::hash<int>()(foo.i)    + 0x9e3779b9) ^
         (std::hash<double>()(foo.d) + 0x9e3779b9) ^
         (std::hash<char>()(foo.c)   + 0x9e3779b9) ^
         (std::hash<bool>()(foo.b)   + 0x9e3779b9);
}

Вопросы:

1. Чего они пытаются достичь, добавив золотой рацион или сдвинув биты в результате std::hash,
2. Есть ли "официальная схема" для std::hash объект с произвольным количеством атрибутов фундаментального типа?

Answer 1

Простой xor является симметричным и ведет себя плохо, когда передается "одно и то же" значение несколько раз (hash(a) ^ hash(a) это ноль). Смотрите здесь для более подробной информации.

Это вопрос объединения хэшей. boost имеет hash_combine, который довольно приличный. Напишите хеш-сумматор и используйте его.

Не существует "официальной схемы" решения этой проблемы.

Сам я обычно пишу супер-хеш, который может взять что-нибудь и хэшировать. Хэш автоматически объединяет кортежи, пары и коллекции, где сначала хэширует количество элементов в коллекции, а затем элементов.

Находит hash(t) сначала через ADL, и, если это не удается, проверяет, есть ли у него написанный вручную хэш в пространстве имен помощника (используется для std контейнеры и типы), и если это не удается std::hash<T>{}(t),

Тогда мой хэш для Foo поддержка выглядит так:

struct Foo {
  int    i;
  double d;
  char   c;
  bool   b;
  friend auto mytie(Foo const& f) {
    return std::tie(f.i, f.d, f.c, f.b);
  }
  friend std::size_t hash(Foo const& f) {
    return hasher::hash(mytie(f));
  }
};

где я использую mytie двигаться Foo в tupleзатем используйте std::tuple перегрузка hasher::hash чтобы получить результат.

Мне нравится идея, что хеши структурно похожих типов имеют одинаковый хеш. Это позволяет мне действовать так, как будто мой хэш прозрачен в некоторых случаях.

Обратите внимание, что хэширование неупорядоченных мяу таким образом является плохой идеей, поскольку асимметричный хэш неупорядоченного мяу может привести к ложным ошибкам.

(Мяу - это общее название карты и набора. Не спрашивайте меня, почему: спросите STL.)

Answer 2

Стандартная структура хеширования отсутствует в отношении объединения хешей. Объединение хешей с использованием xor является неоптимальным.

Лучшее решение предлагается в N3980 "Типы Не знаю #".

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

С этой структурой ваша хеш-функция будет выглядеть так:

template <class HashAlgorithm>
void hash_append(HashAlgorithm& h, Foo const& x) noexcept
{
    using std::hash_append;
    hash_append(h, x.i);
    hash_append(h, x.d);
    hash_append(h, x.c);
    hash_append(h, x.b);
}

И контейнер:

std::unordered_map<Foo, MyValueType, std::uhash<>> myMap;