Очень низкая стоимость хэш-функции

Question

Мне нужна хеш-функция для таблицы поиска, поэтому, если мои значения от 0 до N, мне нужна хеш-функция, которая дает мне значение от 0 до n, где n << N. Еще одна часть информации это то, что я уже знаю N заранее. </p>

Я исследовал различные недорогие хэш-функции и нашел только следующее:

h = z mod n  range(z) - 0 to N, range(h) - 0 to n

Моя хеш-функция должна быть реализована в HW, поэтому она должна иметь очень низкую стоимость. Кто-нибудь может порекомендовать любую другую формулу или алгоритм, кроме этой простой вещи? Когда я говорю «HW», я имею в виду истинную реализацию в HW, а не инструкции в микропроцессоре.

Спасибо.

Обновление с решением

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

Answer 1

Канонической формой этого является h(x) = (a*x + b) mod n, где a и b - константы, а n - размер вашей хеш-таблицы. Вы хотите сделать n простым числом, чтобы получить оптимальное (ish) распределение.

Обратите внимание, что это чувствительно к определенным типам распределений - например, просто выполнение x mod n в основном зависит от случайности младших битов; если они не случайны в вашем наборе, вы получите довольно существенный перекос.

Боб Дженкинс разработал несколько очень хороших хеш-функций; Вот один, специально разработанный для простой реализации в оборудовании: http://burtleburtle.net/bob/hash/nandhash.html

Информацию о множестве хэш-функций, обсуждениях дизайна и т. Д. См. На остальной части сайта: http://burtleburtle.net/bob/hash/

Answer 2

Я считаю, что это лучший из возможных хэшей для этой задачи (быстрее, чем по модулю, лучшее распределение), учитывая, что все ваши числа в 0..N имеют одинаковую вероятность:

h = z * n / N;

Где все значения являются целыми числами, поэтому у вас есть целочисленное деление. Таким образом, каждое значение между 0..N отображается на одно и то же количество значений в n.

Например, когда n = 3 и N = 7 (значения 3 и 7 не включены в диапазоны), хэши таковы:

z * n / N = hash
----------------
0 * 3 / 7 = 0
1 * 3 / 7 = 0
2 * 3 / 7 = 0
3 * 3 / 7 = 1
4 * 3 / 7 = 1
5 * 3 / 7 = 2
6 * 3 / 7 = 2

Таким образом, каждое значение хеш-функции используется одинаково часто, только на 1. Просто позаботьтесь, чтобы n*(N-1) не переполнялось.

Если N является степенью 2, вы можете заменить деление на сдвиг. например если N = 256:

h = (z * n) >> 8;

Answer 3

CRC

Для этого уже есть много аппаратной поддержки.

Answer 4

Если вы действительно говорите об аппаратном обеспечении (по сравнению с программным обеспечением или аппаратной реализацией программного обеспечения), и число хеш-кодов n можно записать как n = 2 ^m - 1, возможно, самым простым регистр сдвига с линейной обратной связью максимальной длины (LFSR), экземпляром которого является CRC.

Вот один из способов, которым вы могли бы использовать m-битный регистр сдвига для создания хэша пакета данных (убедитесь, что все данные последовательно представлены в виде K-битной строки, если у вас более короткие строки, то заполните один конец нулями) :

1. Инициализировать состояние LFSR (CRC-32 использует все 1; все нули, вероятно, плохие)
2. сдвиг в битах ваших данных
3. (Необязательно) Сдвиг в дополнительных j нулей (j между m и 2m, вероятно, является хорошим выбором); это добавляет дополнительное хеширование для уменьшения прямой корреляции между битами ввода / вывода
4. Используйте содержимое регистра сдвига m-bit в качестве хешированного значения.

Answer 5

Переписать биты в случайном порядке и взять младшие log2(n) биты

Или просто взять младшие log2(n) биты, если ваши данные распределены равномерно.