SUHA (компьютерные науки)

В информатике SUHA ( Simple U niform H ashing A ssumption) — это базовое предположение , которое облегчает математический анализ хэш-таблиц . Это предположение утверждает , что гипотетическая функция хэширования равномерно распределит элементы по слотам хэш-таблицы. Более того, каждый элемент, который должен быть хэширован, имеет равную вероятность быть помещенным в слот, независимо от других уже размещенных элементов. Это предположение обобщает детали хэш-функции и допускает определенные предположения о стохастической системе.

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

Некоторые свойства хеш-таблиц можно вывести, если предположить равномерное хеширование.

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

${\displaystyle P(h(a)=h(b))={\frac {1}{м}}.}$

При условии равномерного хеширования коэффициент загрузки и средняя длина цепочки хеш-таблицы размера m с n элементами будут равны${\displaystyle \альфа}$

${\displaystyle \альфа ={\tfrac {n}{м}}}$

При условии равномерного хеширования среднее время (в нотации «большое О» ) успешного поиска элемента в хеш-таблице с использованием цепочки равно

${\displaystyle O(\alpha +1)\,}$

При условии равномерного хеширования среднее время (в нотации «большое О») безуспешного поиска элемента в хеш-таблице с использованием цепочки равно

${\displaystyle O(\alpha +1)\,}$

Простой пример использования SUHA можно увидеть при наблюдении за произвольной хэш-таблицей размером 10 и набором данных из 30 уникальных элементов. Если для решения проблем с коллизиями используется цепочка, средняя длина цепочки этой хэш-таблицы может быть желаемым значением. Без каких-либо предположений и без дополнительной информации о данных или хэш-функции длина цепочки не может быть оценена. Однако с SUHA мы можем утверждать, что из-за предполагаемого равномерного хэширования каждый элемент имеет равную вероятность сопоставления со слотом. Поскольку ни один конкретный слот не должен быть предпочтительнее другого, 30 элементов должны хэшироваться в 10 слотов равномерно. Это создаст хэш-таблицу, в среднем, с 10 цепочками каждая длиной 3

${\displaystyle \альфа ={\tfrac {n}{м}}}$

${\displaystyle \alpha = {\tfrac {30}{10}}}$

${\displaystyle \альфа =3\,}$

• Хэш-таблица
• Столкновение хэшей
• Идеальное хеширование

• Коллинз, Уильям (2004). "Раздел 14.3.2: Допущение равномерного хеширования". Структуры данных и Java Collections Framework . McGraw-Hill. стр. 608. ISBN 0-07-282379-8.
• Кормен, Томас Х .; Чарльз Э. Лейзерсон ; Рональд Л. Ривест ; Клиффорд Стейн (2001). «Раздел 11.2: Хэш-таблицы». Введение в алгоритмы . MIT Press и McGraw-Hill. стр.  226–228 . ISBN. 0-262-03293-7.