Универсальное хеширование на практике

14

ЧАСчас:U→{0,...,M-1}

∀Икс,Y∈U,Икс≠Y⇒Prчас∈ЧАС[час(Икс)знак равночас(Y)]≤1M
Вы можете узнать больше о всеобщем хэширования это википедия статьи .

Концепция универсального хеширования в настоящее время является стандартной частью курсов по структуре данных студентов. Было бы неплохо мотивировать студентов на важность универсального хеширования в промышленных приложениях. Итак, мой вопрос:

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

data-structures education hash-tables applied-theory Dai
источник
Я ожидаю, что все реализации универсальных хеш-структур, которые хотят достичь (амортизированных / ожидаемых / реальных) постоянных затрат времени на вставку, поиск и удаление (что является единственной причиной, по которой мы вообще пытаемся хешировать), нуждаются в надежном способе построить «хорошие» хеш-функции. Универсальное хеширование - это (успешная) попытка формализовать, что такое «хорошая» хеш-функция, и она также дает нам инструменты для эффективной генерации таких функций для произвольных ключей. Поскольку у меня нет какого-либо отраслевого опыта, это все с теоретической точки зрения, но я очень рассчитываю на то, что они станут идеальным решением.
Г. Бах
@ G.Bach Спасибо за ваши комментарии. Но я хочу услышать мнения с промышленной точки зрения.
Дай
@Dai Это, вероятно, не подходящее место для получения заявлений от промышленности, хотя.
Рафаэль

Ответы:

4

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

См. Скотт А. Кросби и Дэн С. Уоллах "Отказ в обслуживании посредством атак алгоритмической сложности" .

jbapple
источник
Это очень полезно. Я прошел через аналогичную статью, так как ссылка была разорвана. Посмотрим и на этот. Спасибо
Риши Дуа