Является ли семейство хеш-функций Universal только для предотвращения атаки противника?

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

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

РЕДАКТИРОВАТЬ: Поскольку кто-то пытается закрыть как неясный; Этот вопрос заключается в том, чтобы узнать реальную цель использования универсального семейства хеш-функций.


hash data-structures hashtable universal-hashing
person Aravind    schedule 06.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я мог бы обойтись одной хорошей хэш-функцией, верно?

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

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

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

person Tony Delroy    schedule 08.02.2016
comment
Я понимаю, что вы говорите, но я думаю, что мы путаем здесь две вещи. Один из них — это двойное хеширование для поиска последовательности проб, а другой — семейство хэш-функций Universal. Насколько я понимаю, это 2 разные вещи. Для простоты давайте воспользуемся цепочкой как средством разрешения коллизий. Теперь, если я не беспокоюсь о вражеских атаках, мне не нужно беспокоиться о реализации универсального семейства хеш-функций, верно? Я мог бы просто выбрать одну хорошую хэш-функцию и использовать ее для своей реализации, верно? - person Aravind; 08.02.2016
comment
@Aravind: вы действительно можете выполнять двойное хеширование без универсального семейства хэш-функций: процитируем Википедия ...хэш-функции h1 и h2, i-е место в последовательности сегментов для значения k в хэш-таблице T: h(i,k)=(h1(k) + i * h2(k)) mod |T|. — только с использованием двух хеш-функций. Тем не менее, Википедия продолжает: Как правило, h_1 и h_2 выбираются из набора универсальных хеш-функций.. Также можно использовать разные хэш-функции из семейства для каждого последующего зонда, а не i * h2(k), что типично для двойного хеширования. - person Tony Delroy; 08.02.2016
comment
Как бы то ни было, моя точка зрения заключалась в том, что такие семейства хеш-функций могут давать различную склонность к коллизиям, и вам может это небезразлично даже в ситуациях, когда у вас нет противника, пытающегося вызвать коллизии. Если у вас нет особых потребностей в предсказуемой открытой адресации после столкновения и у вас нет врагов, я не могу придумать другой причины, чтобы перейти к универсальному семейству хеш-функций. Их необходимость в повседневном программном обеспечении, не защищенном от сетевых атак, является скорее исключением, чем правилом. - person Tony Delroy; 08.02.2016
comment
Хорошо! Однако у меня есть один вопрос: также возможно использовать разные хеш-функции из семейства для каждого последующего зонда, а не i * h2(k), типичный для двойного хэширования. Различные хеш-функции для каждого последующего зонда? Я думал, что хеш-функции выбираются случайным образом в начале использования хеш-таблицы. Где я могу прочитать больше об этом подходе к выбору случайных хеш-функций для каждого зонда? Как функция, используемая для конкретного зонда, позже сохраняется в ключах поиска? - person Aravind; 08.02.2016
comment
@Aravind: Я думал, что хэш-функции выбираются случайным образом в начале использования хэш-таблицы. - они могут быть такими, чтобы избежать злонамеренных атак или, например. для рандомизации хэш-функции и, следовательно, порядка итераций, поэтому код, который неправильно предполагает что-то об этом порядке, с большей вероятностью выйдет из строя на раннем этапе (надеюсь, при тестировании). Тем не менее, вы можете использовать семейства хэш-функций, даже если не выбираете какую-либо из них случайным образом: вы можете начать с h(key), в случае коллизии попробовать h'(key), затем h''(key) и т. д., где h/h'/ h'' являются последовательными членами семьи, пока вы не найдете неиспользованное ведро. - person Tony Delroy; 08.02.2016
comment
Спасибо, есть так много способов использовать семейство хеш-функций. Хотя я не очень математически склонен проверять, какой способ лучше, тем не менее, на мой вопрос был дан ответ. - person Aravind; 08.02.2016
comment
@Aravind: какой путь лучше, также не всегда можно ответить математически - иногда это зависит от размеров вашей основной и различных уровней кэш-памяти, скорости процессора и т. д. реализации хеш-таблиц в контексте хоста и приложения, которые будут иметь ваши конечные пользователи, и тщательные измерения времени. В любом случае - удачи в кодировании. - person Tony Delroy; 09.02.2016
comment
Я возился с математической частью этого и ужасно провел время. Самый разумный совет, который я читал о реализации хеш-таблиц, это именно то, что вы говорите: просто протестируйте и посмотрите, как настроить реализацию. Я готовлюсь к техническому собеседованию и хочу прояснить свои основы. Итак, я бы не стал кодировать хеш-таблицу прямо сейчас, хотя она и есть в моем списке дел. Спасибо за ваш терпеливый вклад! - person Aravind; 09.02.2016