Структуры данных и алгоритмы (1021739), страница 31
Текст из файла (страница 31)
Если К = 1000 и В = 8, то можно выбрать С = 354. ТогдаА(456) =Для применения к символьной строке описанной хеш-функции надо сначала встроке сгруппировать символы справа налево в блоки с фиксированным количествомсимволов, например по 4 символа, добавляя при необходимости слева пробелы. Каждый блок трактуется как простое целое число, из которого путем конкатенации(сцепления) формируется двоичный код символов, составляющих блок.
Например, основная таблица ASCII кодировки символов использует 7-битовый код, поэтому символыможно рассматривать как "цифры" по основанию 27 или 1281. Таким образом, символьную строку abed можно считать целым числом (128)3а + (128)26 + (128)с + d. Послепреобразования всех блоков в целые числа они суммируются2, а затем выполняетсявышеописанный процесс возведения в квадрат и извлечения средних цифр.Анализ закрытого хешированияВ случае применения схемы закрытого хеширования скорость выполнения вставки и других операций зависит не только от равномерности распределения элементовпо сегментам хеш-функцией, но и от выбранной методики повторного хешированиядля разрешения коллизий, связанных с попытками вставки элементов в уже заполненные сегменты. Например, методика линейного хеширования для разрешенияколлизий — не самый лучший выбор.
Не приводя в данной книге полного решенияэтой проблемы, мы ограничимся следующим анализом.Как только несколько последовательных сегментов будут заполнены (образуягруппу), любой новый элемент при попытке вставки в эти сегменты будет вставлен вконец этой группы, увеличивая тем самым длину группы последовательно заполненных сегментов. Другими словами, для поиска пустого сегмента в случае непрерывного расположения заполненных сегментов необходимо просмотреть больше сегментов,чем при случайном распределении заполненных сегментов. Отсюда также следуеточевидный вывод, что при непрерывном расположении заполненных сегментов увеличивается время выполнения вставки нового элемента и других операторов.Определим, сколько необходимо сделать проб (проверок) на заполненность сегментов при вставке нового элемента, предполагая, что в хеш-таблице, состоящей из Всегментов, уже находится N элементов и все комбинации расположения N элементовв В сегментах равновероятны.
Это общепринятые предположения, хотя не доказано,что схемы, отличные от схем закрытого хеширования, могут дать в среднем лучшеевремя выполнения операторов словарей. Далее мы получим формулы, оценивающие"стоимость" (количество проверок на заполненность сегментов) вставки нового элемента, если сегменты выбираются случайным образом. Наконец, мы рассмотрим не1Конечно, если вы работаете не только с латиницей, но и с кириллицей, то необходимо использоватьполную таблицу ASCII. В этом случае основанием для "цифр"-символов будет не 27,8а 2 2, но суть метода от этого не меняется. — Прим. ред.Если исходные символьные строки очень длинные, то суммирование можно выполнять помодулю некоторой константы с.
Эту константу можно взять большей любого числа, получающегося из простого блока символов.124ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВкоторые методики повторного хеширования, дающие "случайное" (равномерное) распределение элементов по сегментам.Вероятность коллизии равна N/B. Предполагая осуществление коллизии, напервом этапе повторного хеширования "работаем" с В - 1 сегментом, где находится N - 1 элемент.
Тогда вероятность возникновения двух подряд коллизийравна N(N - 1)/(В(В - 1)). Аналогично, вероятность по крайней мере i коллизий равна-l)...(N-i + l)l)...(B~i + l) 'Если значения В к N большие, то эта вероятность примерно равна (N/B)'. СреднееЧисло проб равно единице плюс сумма по всем i > 1 вероятностей событий, что, покрайней мере, осуществится i коллизий, т.е.
среднее число проб примерно равно (не1превышает) 1 + ^(ЛГ/В)' =- Можно показать, что точное значение этой сумi=iВ- NВ +1мы при подстановке в нее выражения (4.3) вместо (N/B)' равно, так чтоВ+1-Nнаша приближенная формула достаточно точна, за исключением случая, когдаN близко к В.В +1Отметим, что величинарастет очень медленно при возрастании N от: Одо В - 1, т.е.
до максимального значения N, когда еще возможна вставка новогоэлемента. Например, если N равняется половине В, то в среднем требуются две пробы для вставки нового элемента. Среднее число проб на один сегмент при заполненииI V В+1М сегментов равно — >. Последнюю сумму можно аппроксимировать инМ £Г0 В + 1- N1 гм-1 вВ . (Втегралом — Jах , который равен —In. Таким образом, для полM ° B-xM (^B-M + l Jного заполнения таблицы (М = В) требуется в среднем 1пВ проб на сегмент, или всего BlnB проб. Но для заполнения таблицы на 90% (М = 0.9В) требуется всегоВ((10/9)1п10), или примерно 2.56В проб.При проверке на принадлежность исходному множеству элемента, которого заведомо нет в этом множестве, требуется в среднем такое же число проб, как и привставке нового элемента при данном заполнении таблицы.
Но проверка на принадлежность элемента, который принадлежит множеству, требует в среднем столько жепроб, сколько необходимо для вставки всех элементов, сделанных до настоящеговремени. Удаление требует в среднем примерно столько же проб, сколько и проверкаэлемента на принадлежность множеству. Но в отличие от схемы открытого хеширования, удаление элементов из закрытой хеш-таблицы не ускоряет процесс вставкинового элемента или проверки принадлежности элемента множеству. Необходимоособо подчеркнуть, что средние числа проб, необходимые для выполнения операторовсловарей, являются константами, зависящими от доли заполнения хеш-таблицы.
Нарис. 4.5 показаны графики средних чисел проб, необходимые для выполнения операторов, в зависимости от доли заполнения хеш-таблицы.1Здесь использована следующая формула вычисления среднего (математического ожидания). Пусть х — положительная целочисленная случайная величина, принимающая положительное целое значение i с вероятностью р,. Тогда математическое ожидание случайной величины х можно вычислить по формуле М[х] = £~: ipt = ^~ml Р, + ХГ=2 £Г,( А == 1 + ^" 2 Р{х ^ i} .
Отсюда легко получается приведенная в тексте оценка. — Прим. ред.4.8. ОЦЕНКА ЭФФЕКТИВНОСТИ ХЕШ-ФУНКЦИЙ125(вставка и поискэлемента,которого нет вмножестве)4,0ооCL|3'°т01шIо.О 2,01'°0.20.40.60.8а= N/B - доля заполнения таблицыРис. 4.5. Средние числа проб, необходимые для выполнения операторов„Случайные" методики разрешения коллизийМы ранее видели, что методика линейного повторного хеширования приводит кгруппированию заполненных сегментов в большие непрерывные блоки. Можно предложить хеш-функции с более "случайным" поведением, например, ввести целочисленную константу с > 1 и определить ht(x) = (h(x) + ci) mod В. В этом случае дляВ = 8, с = 3 и h(x) = 4 получим "пробные" сегменты в следующем порядке: 4, 7, 2, 5,О, 3, 6 и 1. Конечно, если В и с имеют общие делители (отличные от единицы), тоэта методика не позволит получить все номера сегментов, например при В = 8 ис = 2.
Но более существенно, что даже если В и с взаимно простые числа (т.е. неимеют общих делителей), то все равно существует проблема "группирования", как ипри линейном хешировании, хотя здесь разделяются блоки заполненных сегментов,соответствующие различным константам с. Этот феномен увеличивает время выполнения операторов словарей (как и при линейном хешировании), поскольку попыткавставить новый элемент в заполненный сегмент приводит к просмотру цепочки заполненных сегментов, различных для различных с, и длина этих цепочек при каждой вставке увеличивается на единицу.Фактически любая методика повторного хеширования, где очередная проба зависит только от предыдущей (например, как зависимость от числа предыдущих"неудачных" проб, от исходного значения h(x) или от самого элемента х), обнаруживает группирующие свойства линейного хеширования.
Возможна простейшая методика, для которой проблема "группирования" не существует: для этого достаточноположить hi(x) = (h(x) + dt) mod В, где d b d2, ..., йв-i — "случайные" перестановкичисел 1, 2, ..., В - 1. Конечно, такой набор чисел dt, dg, ..., dB_i должен использоваться при реализации всех операторов, выполняемых над словарями, а "случайное"перемешивание целых чисел должно быть сделано (выбрано) еще при разработке алгоритма хеширования.Генерация "хороших случайных" чисел — достаточно сложная задача, но, к счастью, существуют сравнительно простые методы получения последовательности"случайных" чисел путем "перемешивания" целых чисел из заданного интервала.126ГЛАВА 4.
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВПри наличии такого генератора случайных чисел можно воспроизводить требуемуюпоследовательность d\, d2, ..., dB-i при каждом выполнении операторов, работающихс хеш-таблицей.Одним из эффективных методов "перемешивания" целых чисел является метод"последовательных сдвигов регистра".
Пусть В является степенью числа 2 и k — константа из интервала от 1 до В - 1. Начнем с некоторого числа d lf взятого из интервала от1 до В - 1. Далее генерируется последовательность чисел df путем удвоения предыдущегозначения до тех пор, пока последнее значение не превысит В. Тогда для получения следующего числа df из последнего значения отнимается число В и результат суммируетсяпобитово по модулю 2 с константой k. Сумма по модулю 2 чисел х и у (записывается какх Ф у) определяется следующим образом: числа х и у записываются в двоичном виде свозможным приписыванием ведущих нулей так, чтобы числа имели одинаковую длину.Результат формируется по правилу логической операции "исключающего ИЛИ", т.е.
1 вкакой-либо позиции результата будет стоять тогда и только тогда, когда только в однойаналогичной позиции слагаемых стоит 1, но не в обеих.Пример 4.7. 25 Ф 13 вычисляется следующим образом:25 = 1100113 = 0110125 ® 13 = 10100Отметим, что такое "суммирование" возможно с помощью обычного двоичногосуммирования, если игнорировать перенос разрядов. DНе для каждого значения k можно получить все "перемешанные" значения из 1,2, ..., В - 1, иногда некоторые сгенерированные числа повторяются. Поэтому длякаждого значения В необходимо подобрать свое значение k, которое будет "работать".Пример 4.8. Пусть В = 8.
Если мы положим k = 3, то сгенерируем все числа от Одо 7. Например, если начнем с числа di = 5, то для нахождения следующего числа d2сначала удваиваем число di, получаем число 10, которое больше 8. Поэтому из 10вычитаем 8, получаем 2 и вычисляем d2 = 2 Ф 3 = 1. Отметим, что для любого хсумму х Ф 3 можно вычислить путем инвертирования (преобразования в обратныйкод) последних двух двоичных разрядов числа х.Повторяя описанную последовательность действий, получим числа di, d2, ..., d^ ввиде 3-битовых двоичных чисел. Все этапы их вычисления показаны в табл. 4.2. Отметим, что умножение двоичного числа на 2 равнозначно сдвигу влево этого числа наодин разряд — это оправдывает название "метод последовательного сдвига регистра".Таблица 4.2. Вычисления по методу последовательного сдвига регистраdi = 101 = 5удаление ведущей 1 (вычитание 8)1010010Ф3dz = 001 = 1СДВИГda = 010 = 2сдвигdt = 100 = 4сдвиг1000сдвигудаление ведущей 1000Ф3di = Oil = 3сдвигde = 110 = 6сдвиг1100удаление ведущей 1100dj = 111 *= 7Ф34.8.
ОЦЕНКА ЭФФЕКТИВНОСТИ ХЕШ-ФУНКЦИЙ127Читатель может проверить, что полный "перемешанный" набор чисел 1, 2, ..., 7можно получить и для k = 5, но ни при каких других значениях ft. DРеструктуризация хеш-таблицПри использовании открытых хеш-таблиц среднее время выполнения оператороввозрастает с ростом параметра N/B и особенно быстро растет при превышении числаэлементов над числом сегментов.
Подобным образом среднее время выполнения операторов также возрастает с увеличением параметра N/B и для закрытых хеш-таблиц,что видно из рис. 4.5 (но превышения N над В здесь невозможно).Чтобы сохранить постоянное время выполнения операторов, которое теоретически возможно при использовании хеш-таблиц, мы предлагаем при достижении N достаточно больших значений, например при N > 0.9В для закрытыххеш-таблиц и N > 2В — для открытых хеш-таблиц, просто создавать новуюхеш-таблицу с удвоенным числом сегментов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
