Какие целочисленные хеш-функции хороши тем, что принимает целочисленный хеш-ключ?

Question

Какие целочисленные хеш-функции хороши для принятия целочисленного хеш-ключа?

Answer 1

Я обнаружил, что следующий алгоритм обеспечивает очень хорошее статистическое распределение. Каждый входной бит влияет на каждый выходной бит с вероятностью около 50%. Коллизий нет (каждый вход приводит к другому выходу). Алгоритм быстрый, за исключением случаев, когда в CPU нет встроенной единицы умножения целых чисел. Код C, предполагая, что int является 32-битным (для Java замените >> на >>> и удалите unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

Магическое число было рассчитано с помощью специальной многопоточной тестовой программы , которая работала в течение многих часов и рассчитывала лавинный эффект (количество выходных битов, которые изменяются при изменении одного входного бита; должно быть около 16 в среднем), независимость изменений выходного бита (выходные биты не должны зависеть друг от друга) и вероятность изменения каждого выходного бита в случае изменения любого входного бита. Рассчитанные значения лучше, чем у 32-разрядного финализатора, используемого MurmurHash , и почти столь же хороши (не совсем), как при использовании AES . Небольшое преимущество заключается в том, что одна и та же константа используется дважды (она сделала ее немного быстрее в последний раз, когда я тестировал, не уверен, что это все еще так).

Вы можете полностью изменить процесс (получить входное значение из хэша), если заменить 0x45d9f3b на 0x119de1f3 ( мультипликативный обратный ):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

Для 64-битных чисел я предлагаю использовать следующее, даже если оно будет не самым быстрым. Этот основан на splitmix64 , который, кажется, основан на статье блога Better Bit Mixing (микс 13).

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

Для Java используйте long, добавьте L к константе, замените >> на >>> и удалите unsigned. В этом случае реверс более сложен:

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

Обновление: Вы также можете посмотреть на проект Hash Function Prospector , где перечислены другие (возможно, лучшие) константы.

Answer 2

Мультипликативный метод Кнута:

hash(i)=i*2654435761 mod 2^32

В общем, вы должны выбрать множитель в порядке вашего размера хэша (2^32 в примере) и не иметь с ним общих факторов. Таким образом, хеш-функция равномерно покрывает все ваше хеш-пространство.

Редактировать: Самый большой недостаток этой хеш-функции заключается в том, что она сохраняет делимость, поэтому, если все ваши целые числа делятся на 2 или 4 (что нередко), их хэши тоже будут. Это проблема в хеш-таблицах - в итоге вы можете использовать только 1/2 или 1/4 используемых сегментов.

Answer 3

Зависит от того, как распределяются ваши данные. Для простого счетчика самая простая функция

f(i) = i

будет хорошо (подозреваю, оптимально, но я не могу доказать это).

Answer 4

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

Answer 5

• 32-битный мультипликативный метод (очень быстрый) see @ rafal

  #define hash32(x) ((x)*2654435761)
  #define H_BITS 24 // Hashtable size
  #define H_SHIFT (32-H_BITS)
  unsigned hashtab[1<<H_BITS]  
  .... 
  unsigned slot = hash32(x) >> H_SHIFT
  

• 32-битные и 64-битные (хорошее распределение) в: MurmurHash

• Целочисленная хеш-функция

Answer 6

Есть хороший обзор некоторых алгоритмов хеширования в Eternally Confuzzled . Я бы порекомендовал одноразовый хэш Боба Дженкинса, который быстро достигает лавины и, следовательно, может использоваться для эффективного поиска в хеш-таблице.

Answer 7

Ответ зависит от многих вещей, таких как:

• Где вы собираетесь его использовать?
• Что вы пытаетесь сделать с хешем?
• Вам нужна криптографически безопасная хеш-функция?

Я предлагаю вам взглянуть на семейство хеш-функций Меркле-Дамгарда , таких как SHA-1 и т. Д.

Answer 8

Я не думаю, что мы можем сказать, что хеш-функция является "хорошей", не зная ваших данных заранее! и не зная, что ты собираешься делать с этим.

Существуют более качественные структуры данных, чем хеш-таблицы для неизвестных размеров данных (я предполагаю, что вы выполняете хеширование для хеш-таблицы здесь). Я бы лично использовал хеш-таблицу, когда знаю, что у меня есть «конечное» количество элементов, которые необходимо хранить в ограниченном объеме памяти. Я попытался бы сделать быстрый статистический анализ своих данных, посмотреть, как они распределяются и т. Д., Прежде чем начать думать о своей хэш-функции.

Answer 9

Я использую splitmix64 (указано в ответе Томаса Мюллера ) с тех пор, как я нашел эту тему. Однако недавно я наткнулся на Pelle Evensen rrxmrrxmsx_0 , который дал значительно лучшее статистическое распределение, чем оригинальный финализатор MurmurHash3 и его преемники (splitmix64 и другие миксы). Вот фрагмент кода в C:

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle также предоставляет углубленный анализ 64-разрядного микшера, использованного на последнем шаге MurmurHash3, и более поздних вариантов.

Answer 10

Для случайных значений хеш-функции некоторые инженеры считают, что простое число золотого сечения (2654435761) - плохой выбор. По результатам моих испытаний я обнаружил, что это не так; вместо этого 2654435761 довольно хорошо распределяет хеш-значения.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

Размер хеш-таблицы должен быть степенью двойки.

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

Я пробовал:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; где total_bucket_number = размер хеш-таблицы;
2. отображать область значений хеш-функции в область индекса сегмента; то есть преобразовать значение хеш-функции в индекс сегмента с помощью логической операции и операции с (hash_table_size - 1), как показано в Hash_UInt_GRPrimeNumber ();
3. рассчитать число столкновений каждого ковша;
4. записать контейнер, который не был отображен, то есть пустой контейнер;
5. узнать максимальное число столкновений всех ковшей; самая длинная цепь;

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

Некоторые хеш-функции для целых чисел считаются хорошими, но результаты тестирования показывают, что когда total_data_entry / total_bucket_number = 3, длина самой длинной цепочки больше 10 (максимальное число коллизий> 10), и многие сегменты не отображаются (пустые сегменты), что очень плохо, по сравнению с результатом нулевого пустого сегмента и самой длинной цепочки длиной 3 по хэшированию простого числа золотого сечения.

Кстати, с моими результатами тестирования я обнаружил, что одна версия хеш-функций shifting-xor довольно хороша (ее разделяет mikera).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}