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

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), то вы уменьшите вероятность столкновений и, следовательно, повысите стоимость выполнения поиска.Однако, если α становится слишком маленьким - скажем, у вас на самом деле хранится 1000 слотов на элемент - тогда у вас будет много потерянного пространства.

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