Использование универсального хеширования

Question

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

Из того, что я понимаю в универсальном хешировании, мы выбираем функцию

H(x)=[(ax+b)mod p]mod m

где p - простое число, превышающее все ключи, m - размер таблицы данных и a, b - случайные числа.

Так, например, если я хочу прочитать ID 80 человек, и каждый ID имеет значение между [0,200], то m будет 80, а p будет 211(следующее простое число). Правильно? Я мог бы использовать функцию, скажем,

H(x)=[(100x+50)mod 211]mod 80

Но почему это поможет? Существует высокая вероятность того, что в итоге у меня будет много пустых слотов на столе, и я буду занимать место без причины. Разве не было бы более полезно уменьшить число m, чтобы получить меньшую таблицу, чтобы пространство не использовалось без причины?

Любая помощь приветствуется

Answer 1

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

Параметр m, который вы рассматриваете, настраивает, сколько слотов находится в вашей хэш-таблице. Давайте представим, что вы планируете сбросить n элементов в вашу хэш-таблицу. Отношение n / m называется коэффициентом загрузки хеш-таблицы и обычно обозначается буквой α.

Если у вас есть таблица с высоким коэффициентом загрузки (большой α, маленький m), то у вас будет меньше потерянного места в таблице. Тем не менее, вы также увеличите стоимость поиска, так как при большом количестве объектов, распределенных в небольшом пространстве, вы, вероятно, получите кучу столкновений, для решения которых потребуется время.

С другой стороны, если у вас есть таблица с низким коэффициентом загрузки (маленький α, большой m), то вы уменьшите вероятность столкновений и, следовательно, повысите стоимость выполнения поиска. Однако, если α становится слишком маленьким - скажем, у вас есть 1000 сохраненных слотов на элемент - тогда у вас будет много потерянного пространства.

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