Какова наилучшая хэш-функция для ключей uint64_t в диапазоне от 0 до максимального значения?

Question

Предполагая, что у нас есть набор элементов и мы хотим сохранить их в хэш-карте (например, std::unoredered_set), и каждый элемент имеет ключ типа uint64_t, значение которого может варьироваться от 0 до максимально возможного значенияЭто лучший выбор для использования тривиальной хэш-функции, где хэш-значение ключа является ключом?Зависит ли это от используемого контейнера (т. Е. Разреженный хэш Google против неупорядоченной карты из STL)?Вероятность появления ключевых значений неизвестна.

Answer 1

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

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

Answer 2

Я бы предложил хороший 64-битный микшер, из которого есть из чего выбирать.Финализатор из MurmerHash3 довольно быстр и выполняет разумную работу всего за пять строк кода:

key ^= key >> 33;
key *= 0xff51afd7ed558ccd;
key ^= key >> 33;
key *= 0xc4ceb9fe1a85ec53;
key ^= key >> 33;

Числовые рецепты, 3-е издание, рекомендует следующее:

public static UInt64 Next( UInt64 u )
  {
  UInt64 v = u * 3935559000370003845 + 2691343689449507681;

  v ^= v >> 21;
  v ^= v << 37;
  v ^= v >>  4;

  v *= 4768777513237032717;

  v ^= v << 20;
  v ^= v >> 41;
  v ^= v <<  5;

  return v;
  }

Answer 3

HashMaps очень полезны для обеспечения быстрого доступа к данным. Сложность операций хеширования O(1), что очень быстро по сравнению с другими известными структурами, такими как двойные связанные списки, связанные списки или деревья.

Чтобы использовать uint64_t в качестве ключа для хеша, вы можете использовать хеш-контейнеры, такие как GHASHLISH

Библиотека GLIB является поточно-ориентированной и используется несколькими проектами с открытым исходным кодом. Он не поддерживает uint64_t как ключ, поэтому вы должны предоставить свою собственную функцию hash_function.

Например, вы можете использовать FNV хэш

Вот краткий пример того, как хешировать uint64 до uint32, используя FNV:

#define FNV_offset_basis 2166136261
#define FNV_prime        16777619
guint c_uint64_t_hash(gpointer data)
{
  uint8_t* v =(uint8_t*)data;
  guint hash = FNV_offset_basis;
  for(int i=0;i<8;i++)
  {
    hash = hash ^ v[i];
    hash = hash * FNV_prime;
  }
return hash;
}