yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Анализ закрытого хеширования

Алгоритмы структуры данных

Анализ закрытого хеширования

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

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

Определим, сколько необходимо сделать проб (проверок) на заполненность сегментов при вставке нового элемента, предполагая, что в хеш-таблице, состоящей из В сегментов, уже находится N элементов и все комбинации расположения N элементов в В сегментах равновероятны. Это общепринятые предположения, хотя не доказано, что схемы, отличные от схем закрытого хеширования» могут дать в среднем лучшее время выполнения операторов словарей. Далее мы получим формулы, оценивающие "стоимость" (количество проверок на заполненность сегментов) вставки нового элемента, если сегменты выбираются случайным образом. Наконец, мы рассмотрим некоторые методики повторного хеширования, дающие "случайное" (равномерное) распределение элементов по сегментам.

Вероятность коллизии равна N/В. Предполагая осуществление коллизии, на первом этапе повторного хеширования "работаем" с В — 1 сегментом, где находится N - 1 элемент. Тогда вероятность возникновения двух подряд коллизий равна N(N - 1)/(В(В - 1)). Аналогично, вероятность по крайней мере і коллизий равна

       (4.3)

Если значения В и N большие, то эта вероятность примерно равна (N/B)1. Среднее число проб равно единице плюс сумма по всем і > 1 вероятностей событий, что, по крайней мере, осуществится і коллизий, т.е. среднее число проб примерно равно (не превышает)  (здесь использована следующая формула вычисления среднего (математического ожидания). Пусть х — положительная целочисленная случайная величина, принимающая положительное целое значение і с вероятностью рi. Тогда математическое ожидание случайной величины х можно вычислить по формуле

М[х] = . Отсюда легко получается приведенная в тексте оценка). Можно показать, что точное значение этой суммы при подстановке в нее выражения (4.3) вместо (N/B)i равно  , так что

наша приближенная формула достаточно точна, за исключением случая, когда N близко к В.

Отметим, что величина  растет очень медленно при возрастании N от 0

до В — 1, т.е. до максимального значения N, когда еще возможна вставка нового элемента. Например, если N равняется половине В, то в среднем требуются две пробы для вставки нового элемента. Среднее число проб на один сегмент при заполнении М сегментов равно

Последнюю сумму можно аппроксимировать интегралом, который равен. Таким образом, для полного заполнения таблицы (М = В) требуется в среднем InВ проб на сегмент, или всего BlnB проб. Но для заполнения таблицы на 90% (М = 0.9В) требуется всего В((10/9)1n10), или примерно 2.56В проб.

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

 

56