Какая целочисленная хэш-функция хороша, которая принимает целочисленный хеш-ключ?
Какая целочисленная хэш-функция хороша, которая принимает целочисленный хеш-ключ?
Ответ 1
Мультипликативный метод Кнута:
hash(i)=i*2654435761 mod 2^32
В общем, вы должны выбрать множитель, который находится в порядке вашего размера хэша (2^32 в примере) и не имеет общих факторов. Таким образом, хеш-функция равномерно охватывает все ваши хэш-пространство.
Изменить: самым большим недостатком этой хэш-функции является то, что она сохраняет делимость, поэтому, если ваши целые числа делятся на 2 или на 4 (что не редкость), их хэши тоже будут. Это проблема в хэш-таблицах - в итоге вы можете использовать только 1/2 или 1/4 используемых ведер.
Ответ 2
Я обнаружил, что следующий алгоритм обеспечивает очень хорошее статистическое распределение. Каждый входной бит влияет на каждый выходной бит с вероятностью около 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, где перечислены другие (возможно, лучшие) константы.
Ответ 3
В зависимости от того, как распределяются ваши данные. Для простого счетчика простейшая функция
f(i) = i
будет хорошим (я подозреваю, что это оптимально, но я не могу это доказать).
Ответ 4
На этой странице перечислены некоторые простые хеш-функции, которые обычно имеют тенденцию в целом, но любой простой хэш имеет патологические случаи, когда он не работает,
Ответ 5
-
32-битный мультипликативный метод (очень быстрый) см. @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
- Целочисленная функция хеширования
Ответ 6
Вот хороший обзор некоторых хэш-алгоритмов на Eternally Confuzzled. Я бы порекомендовал один раз в хэш-код Боба Дженкинса, который быстро достигает лавины и поэтому может использоваться для эффективного поиска хеш-таблицы.
Ответ 7
Ответ зависит от многих вещей, таких как:
- Где вы собираетесь его использовать?
- Что вы пытаетесь сделать с хешем?
- Вам нужна криптографически безопасная хеш-функция?
Я предлагаю вам взглянуть на семейство хеш-функций Merkle-Damgard, таких как SHA-1 и т.д.
Ответ 8
Я не думаю, что мы можем сказать, что хеш-функция "хороша", не зная ваших данных заранее! и не зная, что вы собираетесь с ним делать.
Существуют лучшие структуры данных, чем хэш-таблицы для неизвестных размеров данных (я предполагаю, что вы делаете хэширование для хеш-таблицы здесь). Я лично использовал хеш-таблицу, когда узнаю, что у меня есть "конечное" количество элементов, которые нуждаются в хранении в ограниченном объеме памяти. Я бы попытался сделать быстрый статистический анализ моих данных, посмотреть, как он распространяется и т.д., Прежде чем я начну думать о своей хэш-функции.
Ответ 9
Быстрые и хорошие хеш-функции могут быть составлены из быстрых перестановок с меньшими качествами, таких как
- умножение с неравным целым
- бинарные вращения
- xorshift
Чтобы получить функцию хеширования с превосходными качествами, как продемонстрировано с PCG для генерации случайных чисел.
На самом деле это также рецепт rrxmrrxmsx_0 и харма бормотания, сознательно или неосознанно.
Я лично нашел
uint64_t xorshift(const uint64_t& n,int i){
return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
uint64_t p = 0x5555555555555555; // pattern of alternating 0 and 1
uint64_t c = 17316035218449499591ull;// random uneven integer constant;
return c*xorshift(p*xorshift(n,32),32);
}
быть достаточно хорошим.
Хорошая хеш-функция должна
- быть биективным, чтобы не потерять информацию, если возможно, и иметь наименьшее количество столкновений
- каскадировать как можно больше и равномернее, то есть каждый входной бит должен отражать каждый выходной бит с вероятностью 0,5.
Давайте сначала посмотрим на функцию идентичности. Он удовлетворяет 1., но не 2.:
Входной бит n определяет выходной бит n с корреляцией 100% (красный) и не имеет других, поэтому они синего цвета, что дает идеальную красную линию поперек.
Ксоршифт (n, 32) ненамного лучше, получая полторы строки. Все еще удовлетворяет 1., потому что это обратимо со вторым выражением.
Умножение на целое число без знака намного лучше, более сильное каскадирование и переворачивание большего количества выходных битов с вероятностью 0,5, что и нужно, зеленым цветом. Я удовлетворяю 1. поскольку для каждого нечетного целого числа есть обратное мультипликативное значение.
Комбинация двух дает следующий результат, все еще удовлетворяя 1., поскольку композиция двух биективных функций дает другую биективную функцию.
Второе применение умножения и xorshift приведет к следующему:
Или вы можете использовать умножения полей Галуа, такие как GHash, они стали достаточно быстрыми на современных процессорах и имеют превосходные качества за один шаг.
uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){
__m128i I{};I[0]^=i;
__m128i J{};J[0]^=j;
__m128i M{};M[0]^=0xb000000000000000ull;
__m128i X = _mm_clmulepi64_si128(I,J,0);
__m128i A = _mm_clmulepi64_si128(X,M,0);
__m128i B = _mm_clmulepi64_si128(A,M,0);
return A[0]^A[1]^B[1]^X[0]^X[1];
}
Ответ 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 является довольно хорошим выбором.
Я пытался:
- total_data_entry_number/total_bucket_number = 2, 3, 4; где total_bucket_number = размер хеш-таблицы;
- отобразить область значений хеш-функции в область индекса сегмента; то есть преобразовать значение хеш-функции в индекс сегмента с помощью логической операции и операции с (hash_table_size - 1), как показано в Hash_UInt_GRPrimeNumber();
- рассчитать число столкновений каждого ковша;
- запишите ведро, которое не было отображено, то есть пустое ведро;
- узнать максимальное число столкновений всех ковшей; самая длинная цепь;
По результатам моего тестирования я обнаружил, что у простого числа с золотым соотношением всегда меньше пустых или нулевых пустых сегментов и самая короткая длина цепочки столкновений.
Некоторые хеш-функции для целых чисел заявлены как хорошие, но результаты тестирования показывают, что когда 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;
}
Ответ 11
Я использую 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 и более поздних вариантов.