Hash Table, который пытается хэш-строки равномерно?

Question

В настоящее время я нахожусь в курсе «Структуры данных», ближе к концу семестра, и им был назначен проект, в котором мы реализуем привязанную таблицу хешей для хранения и извлечения ключей. Нам была предоставлена ​​довольно большая свобода с тем, как мы собираемся разрабатывать нашу реализацию хэш-таблицы, но для бонусных пунктов нам сказали попробовать и найти хеш-функцию, которая распределяет наши ключи (уникальные строки) близко к равномерно и случайным образом стол.

Я решил использовать ELF хэш, видел здесь http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Мой вопрос заключается в следующем: С помощью этой хэш-функции целое число возвращается, но у меня возникли проблемы со зрением, как это может быть использовано, чтобы помочь указать для ввода моего ключа в хэш-таблицу. Я мог бы просто сделать: index = ELFhash (String key)% tableSize, но это лишает цель использовать хэш ELF в первую очередь ??

Также я выбрал свою стратегию разрешения конфликтов для двойного хэширования. Есть ли хороший способ определить подходящую вторичную хэш-функцию для поиска ваших прыжков? Моя хеш-таблица не будет постоянным размером (множество строк будет добавлено и удалено из набора данных, которые я использую, и я буду переигрывать их после каждой итерации добавления и удаления, чтобы иметь коэффициент загрузки .75), поэтому мне сложно просто сделать что-то вроде k% n, где n - это число, которое является относительно простым с моим размером таблицы.

Спасибо, что нашли время, чтобы прочитать мой вопрос, и дайте мне знать, что вы думаете!

Answer 1

Вы правы, чтобы думать о «обертывании», но для большинства практических целей это не будет проблемой.

Если хеш-таблица имеет размер N, а значение хеша находится в диапазоне [0..M), то пусть k = floor(M/N). Любое значение хэша в диапазоне [0..k*N) является «хорошим» в этом, используя mod N в качестве карты, каждый хэш-ведро отображается точно в k хеш-значениях. Хэш-значения в [k*N..M) являются «плохими» в том случае, если вы их используете, соответствующие M-K*n нижние хэш-ковши отобразятся из одного дополнительного значения хэш-функции. Даже если хеш-функция идеальна, эти ведра имеют более высокую вероятность получения заданного значения.

Вопрос, однако, заключается в том, «насколько выше?». Это зависит от M и N. Если хэш-значение является unsigned int в [0..2^32), и, прочитав Knuth и другие, вы решили выбрать простое количество ведер около тысячи, скажем, 1009, что происходит?

floor(2^32/1009) = 4256657 

число «плохих» значений

2^32 - 4256657 * 1009 = 383 

Следовательно, все ведра сопоставляются из 4256657 «хороших» значений, и 383 получить еще один нежелательный «плохой» значение для 4256658. Таким образом, «смещение» для 1/4 256 657.

Очень маловероятно, что вы найдете хеш-функцию, где разница в 1 в 4 миллиона разниц между ведрами будет заметна.

Теперь, если вы повторите расчет с миллионом ведер вместо тысячи, тогда все выглядит немного по-другому. В этом случае, если вы немного OC, вы можете переключиться на 64-битный хеш.

Дополнительная информация: Хэш эльфа вряд ли принесет абсолютно ужасные результаты, и это довольно быстро, но есть намного лучшие хэш-функции. Хорошо оцененный, который вы, возможно, захотите попробовать, - Murmur 32.(В статье Wiki упоминается, что в исходном alg есть некоторые недостатки, которые могут быть использованы для DoS-атак, но для вашего приложения все будет в порядке.) Я уверен, что ваш проф не хочет, чтобы вы копировали код, но на странице Википедии есть он завершен. Было бы интересно реализовать Эльфа самостоятельно и попробовать его против Мурмура, чтобы посмотреть, как они сравниваются.