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

Question

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

134

c algorithm hash

Источник

user80223 19 мар '09 в 20:54

9 ответов

Решение

Я обнаружил, что следующий алгоритм обеспечивает очень хорошее статистическое распределение. Каждый входной бит влияет на каждый выходной бит с вероятностью около 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, где перечислены другие (возможно, лучшие) константы.

219

Источник

user382763 21 окт '12 в 08:01

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

f(i) = i

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

32

Источник

user47161 19 мар '09 в 20:57

Быстрые и хорошие хеш-функции могут быть составлены путем объединения нескольких быстрых перестановок с меньшими качествами, таких как

умножение с неравным целым
бинарные вращения
xorshift

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

На самом деле это также рецепт rrxmrrxmsx_0 и харма бормотания, сознательно или неосознанно.

Я лично нашел

uint64_t rol(const uint64_t& n,int i){
  return (n<<i)|(n>>(64-i);
}
uint64_t hash(const uint64_t& n){
  uint64_t c = random_uneven_64_bit_integer_constant"; 
  return c*rol(c*n,32);
}

быть достаточно хорошим

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

25

Источник

user2119377 19 авг '19 в 15:14

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

7

Источник

user39375 19 мар '09 в 21:02

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
Целочисленная хеш-функция

7

Источник

user121958 14 июн '09 в 10:03

Я использую splitmix64 (указал в ответе Томаса Мюллера) с тех пор, как я нашел эту ветку. Однако недавно я наткнулся на 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 и более свежие варианты.

5

Источник

user557697 08 июн '19 в 00:37

Для случайных значений хеш-функции некоторые инженеры сказали, что простое число золотого сечения (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;
}

4

Источник

user11066923 15 фев '19 в 11:48

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

3

Источник

user48015 19 мар '09 в 21:31

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

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

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

2

Источник

user66692 19 мар '09 в 21:02

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

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

1

Источник

user2973433 25 окт '14 в 20:20

Другие вопросы по тегам c algorithm hash

user12166 20 мар '09 в 09:59 2009-03-20 09:59 · Accepted Answer · 2009-03-20 09:59

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

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

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

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