Хэш-функция для кластеризованных целых чисел

Question

Я пытаюсь настроить хеш-таблицу (на C++, используя контейнер unordered_map), который должен содержать 1875 целых элементов, которые распределены случайным образом в интервале от 0 до 4891. Теперь моя проблема в том, что распределение внутри этого интервала не является равномерным, а скорее выглядит следующим образом:

, где каждые из 1875 случайных чисел на графике как точки с й, соответствующими целым значением и у = 1 (так, чтобы визуализировать распределение) ,

Очевидно, что распределение таково, что существуют широкие пробелы, где ни одно случайное целое не лежит. Если я использую функцию идентификации как мою хеш-функцию (т. Е. Использую случайные целые числа сами по себе как хэш-значения), я получаю 714 пустых ведер, 814 ведер с одним элементом, 499 ведер с 2 элементами и 21 ведро с 3 или более элементами.

Я использую компилятор Intel C++, и он использует полномочия 2 для количества ведер в хеш-таблице. В моем случае прямо сейчас хэш-таблица имеет 2^11 = 2048 ковшей.

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

Answer 1

Я обнаружил, что Хеш функция Пирсона является отличным способом, чтобы получить хаотичность:

https://en.wikipedia.org/wiki/Pearson_hashing

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

Answer 2

Если вам нужно уменьшить количество столкновений, это может помочь просмотреть специализированную схему хэширования, например cuckoo hashing. По существу, вы амортизируете несколько хэш-функций для сохранения сложности O(1).

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

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

Answer 3

Так что я потратил некоторое время на то, чтобы попробовать разные вещи. Вот мои выводы до сих пор.

Во-первых, нужно понимать, что установка 1875 элементов в хеш-таблицу с 2048 ведрами может привести к довольно большому количеству столкновений. Действительно, если учесть, что каждый элемент имеет равную вероятность быть привязанным к одному из кодов 2048, то ожидаемое число столкновений равно 646 (аргументом, аналогичным так называемой проблеме рождения, см. https://math.stackexchange.com/questions/35791/birthday-problem-expected-number-of-collisions?rq=1, формула ожидается nb. of collisions = n - N * (1 - (1 - 1/N)^n), где n - число элементов, а N - количество ковшей). Это было бы так, если бы, например, 1875 элементов были выбраны случайным образом в интервале [0, 2047] с допустимыми повторениями или если элементы 1875 были выбраны случайным образом в очень большом интервале относительно количества ведер 2048 с или без повторений.

Принимая это во внимание, столкновения 541, полученные с помощью функции тождества как функции хэша (см. Исходный вопрос), не кажутся слишком плохими. Причина, по которой число столкновений меньше, чем в случае равномерного распределения, несмотря на те большие пробелы в распределении, состоит в том, что по характеру проблемы элементы 1875 имеют разные значения, и поэтому только элементы, превышающие 2048, могут вызвать столкновения, поскольку они обернутый вокруг оператора modulo.

Теперь мы знаем, что хеш-функция, которая отображает наш интервал ввода [0, 4891] на гораздо больший интервал (например, как 32-битное целое число), случайным образом и равномерно нежелательна, поскольку это приведет к большему количеству столкновений, хэш-функция идентичности. Однако можно было бы задаться вопросом, возможно ли иметь случайное и равномерное отображение из входного интервала [0, 4891] в некоторый не слишком большой интервал (это может быть тот же интервал [0, 4891] или любой другой интервал, такой как [0 , 2048], [0, 5000] и т. Д.), Что уменьшало бы столкновения. Я попробовал сопоставления с Pearson-подобными, как было предложено rts1, но обнаружил, что он не улучшает число столкновений.

До сих пор я использовал только функцию идентификации как функцию хеша в сочетании с тем, для количества ведер).