Можно ли реализовать хорошо распределенную хеш-таблицу без использования оператора%?

11

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

  • С одной стороны, вы можете убедиться, что в ваших корзинах всегда есть простое число элементов, и чтобы ограничить хеш, вы просто модулируете его по количеству блоков. Это, собственно, то, что делает словарь .NET . Проблема с этим подходом состоит в том, что использование% является чрезвычайно медленным по сравнению с другими операциями; если вы посмотрите на столах инструкции Agner Противотуманной , idiv(который является ассемблерным кодом , который получает генерируется для%) имеет задержку выполнения команд ~ 25 циклов для новых процессоров Intel. Сравните это около 3 для mul, или 1 для битового опса , как and, orили xor.

  • С другой стороны, у вас может быть число блоков, равное степени 2. Вам все равно придется вычислять модуль хэша, чтобы не пытаться индексировать вне массива, но на этот раз это будет дешевле , Поскольку для степеней 2 % Nсправедливо & (N - 1), ограничение сводится к операции маскирования, которая занимает всего 1-2 цикла. Это сделано с помощью Google sparsehash . Недостатком этого является то, что мы рассчитываем на то, что пользователи будут предоставлять хорошие хэши; Маскировка хеша фактически обрезает часть хеша, поэтому мы больше не учитываем все биты хеша. Если хеш пользователя распределен неравномерно, например, заполнены только старшие биты или младшие биты постоянно одинаковы, тогда этот подход имеет гораздо более высокую частоту коллизий.

Я ищу алгоритм, который я могу использовать, который имеет лучшее из обоих миров: он учитывает все биты хэша, а также быстрее, чем использование%. Это не обязательно должен быть модуль, просто что-то, что гарантированно находится в диапазоне 0..N-1(где N - длина сегментов) и имеет равномерное распределение для всех слотов. Существует ли такой алгоритм?

Спасибо за помощь.

Джеймс Ко
источник
1
Посмотрите на лавинный эффект , а также объяснение в murmurhash3 (smhasher) . Тем не менее, фундаментальный вопрос в вашем вопросе не решается путем принятия лучшей хэш-функции. Вместо этого, это вопрос о том, почему пользователи не принимают ту же самую лучшую хеш-функцию, а также о применении мер противодействия (как будто пользователи злонамеренно ленивы).
Rwong
Для быстрого по модулю (2^N +/- 1)см stackoverflow.com/questions/763137/...
rwong
@ rwong Извините, но я не совсем уверен, что ваш комментарий связан с моим постом. Я не контролирую хэш, предоставленный пользователем, поэтому я не ищу лучшую хэш-функцию. Я также не понимаю, что вы подразумеваете под "злобно ленивыми пользователями".
Джеймс Ко
4
Если хеш-функция плохая, разработчик хеш-таблицы ничего не может сделать, чтобы «исправить» плохое распределение. По модулю простое число не восстанавливает плохой хэш. Рассмотрим в качестве выходных данных хеш-функцию, кратную простому числу. Я видел такую ​​проблему в реальном производственном коде.
Фрэнк Хилман

Ответы:

9

Современные реализации хеш-таблиц не используют функцию по модулю. Они часто используют мощность таблиц двух размеров и отсекают ненужные биты. Идеальная хеш-функция позволила бы это. Использование модуля по модулю в сочетании с размерами таблицы простых чисел возникло в те дни, когда хеш-функции были в целом плохими, поскольку они часто находятся в разработке .net. Я рекомендую прочитать о SipHash , современной хеш-функции, а затем прочитать о некоторых других современных функциях, таких как xxHash .

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

  • инкапсуляция хеш-состояния в структуре или классе
  • хэш-функции «добавить», которые добавляют новые данные в состояние хэш-функции (например, добавить байтовый массив или двойной массив)
  • хеш-функция "финализировать", чтобы произвести лавину
  • инкапсуляция результата хеширования - в .net вы получаете один выбор, 32-битное целое число со знаком.

Для получения дополнительной информации об использовании результата хеш-функции в качестве индекса хеш-таблицы см. Определения универсальных форм хеширования в этой статье: Более быстрое 64-битное универсальное хеширование с использованием умножений без переноса

Фрэнк Хилман
источник
3

Чтобы использовать AND, сохраняя все биты, используйте также XOR.

Для примера temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);.

Для этого примера нет модуля по модулю и все 32 бита hashэффекта 8-битные index. Однако, зависит ли это от DIV или нет, это зависит от слишком многих факторов, и в некоторых случаях он может быть медленнее, чем DIV (например, большой хэш и крошечный индекс).

Brendan
источник
Это всегда будет быстрее, чем DIV / IDIV, однако я не думаю, что это отвечает на мой вопрос - indexбудет в диапазоне [0..255]. Мне нужно что-то в диапазоне [0..n-1], где nнаходится количество ведер.
Джеймс Ко
@JamesKo Но если вы реализуете словарь, вы также контролируете количество сегментов (в определенной степени). Таким образом, вместо простых чисел вы можете выбрать степени двойки. (Будет ли это на самом деле хорошей идеей, я не могу вам сказать.)
svick
@svick Для степеней 2 мы могли бы сделать простую операцию маски. Как уже упоминалось в этом вопросе, я ищу дешевый способ сделать это с простыми числами, чтобы размещались даже плохо распределенные хэши.
Джеймс Ко
1

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

В статье описывается алгоритм поиска такого числа, при котором умножение на это число и игнорирование переполнения приведут к тому же результату, что и при делении на размер индекса сегмента.

BobDalgleish
источник