Как спроектировать хеш-функцию, которая масштабируется до ровно n элементов?

Question

У меня есть список из n строк (имен людей), которые я хочу сохранить в хеш-таблице или аналогичной структуре.Я знаю точное значение n, поэтому я хочу использовать этот факт для поиска O (1), что было бы невозможно, если бы мне пришлось использовать связанный список для хранения моих хеш-узлов.Моей первой реакцией было использование хеша djb, который по сути делает это:

for ( i = 0; i < len; i++ )
    h = 33 * h + p[i];

Чтобы сжать результирующее h в диапазон [0,n], я бы вроде просто сделать h%n, но я подозреваю, что это приведет к гораздо большей вероятности столкновений таким образом, что по сути сделает мой хэш бесполезным.

Тогда мой вопрос, как я могу хешировать либо строкуили полученный хеш, так что элементы n обеспечивают относительно равномерное распределение по [0,n]?

Answer 1

То, что вы ищете, называется Perfect Hash . Это хеш-функция, в которой все ключи известны заранее, сконструированные таким образом, чтобы не было коллизий.

Программа gperf генерирует код C для идеальных хэшей.

Answer 2

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

В любом случае, если вы 'ограничивая количество элементов до известного n, вы уже технически ищите O (1).Верхняя граница будет основана на константе n.Это было бы верно даже для решения без хэширования.

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

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

Если вы не знаете данные заранее, идеальный хеш не возможен.Если, конечно, вы не используете h сам в качестве хеш-ключа, а не h%n, но это займет очень много места: -)

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

И, в любом случае, если вы начнете полагаться на частоты, и вы получите приток людей из тех стран, которые, кажется, не используют гласные (а-ля Босния ^a ), вы в конечном итогес большим количеством столкновений.

Но имейте в виду, что это действительно зависит от n, который вы используете.

Если n достаточно мало, вы можете даже сойти с рук споследовательный поиск несортированного массива.Я предполагаю, что ваш n достаточно велик, и вы уже установили, что (или сбалансированное двоичное дерево) не даст вам достаточной производительности.

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

---

^a Без обид.Я просто помню юмористическую статью давным-давно о Клинтоне, разрешающем перенос гласных слов в Боснию.Я уверен, что есть другие страны с подобной «проблемой».

Answer 3

Оптимальный алгоритм для сопоставления n строк с целыми числами 1 - n заключается в создании DFA, где конечными состояниями являются целые числа 1 - n.(Я уверен, что здесь кто-то придумает причудливое название для этого ... но в конце концов это все DFA.) Соотношение размера / скорости можно регулировать, изменяя размер вашего алфавита (работая с байтами, полубайтами иличетные биты).

Answer 4

Похоже, вы ищете реализацию совершенной хеш-функции или, возможно, даже минимальной совершенной хеш-функции.Согласно странице Википедии, CMPH может соответствовать вашим потребностям.Отказ от ответственности: я никогда не использовал его.