Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 61
Текст из файла (страница 61)
Кроме того, если два ключа имеют одну и то же начальную позицию исследования, то одинаковы и последовательности исследования в целом, так как из Ь1(Ь,О) = Ьг (Ь,О) вьпекает Ь1 (Ь,1) = Ьг ()с,1). Это свойство приводит кболее мягкой вторичной кластеризации. Как и в случае линейного исследования, начальная ячейка определяет всю последовательность, поэтому всего используется т различных последовательностей исследования.
Двойное хеширование Двойное хеширование представляет собой один из наилучших способов использования открытой адресации, поскольку получаемые при этом перестановки обладают многими характеристиками случайно выбираемых перестановок. Двойное хеширование использует хеш-функцию вида Ь ()с,1) = (Ьг (Ь) + 1Ьг (Ь)) пюс1 т, сде Ь1 и Ьг — вспомогательные хеш-функции. Начальное исследование выполняется в позиции Т [Ь| (1с)], а смещение каждой из последующих исследуемых ячеек относительно предыдущей равно Ьг()с) по модулю т.
Следовательно, в отличие отлинейного и квадратичного исследования, в данном случае последовательность исследования зависит от ключа Й по двум параметрам — в плане выбора начальной исследуемой ячейки и расстояния между соседними исследуемыми ячейками, так как оба эти параметра зависят от значения ключа. На рис.
11.5 показан пример вставки при двойном хешировании. Вы видите хеш-таблицу размером 13 ячеек, в которой используются вспомогательные хешфункции Ь1 (/с) = )с пюс1 13 и Ьг (Ь) = 1 + (/спюс1 11).так как 14 :- 1(пюс113) и 14 = 3(пюс111), ключ 14 вставляется в пустую ячейку 9, после того как при исследовании ячеек 1 и 5 выясняется, что эти ячейки заняты. Для того чтобы последовательность исследования могла охватить всю таблицу, значение Ьг (1с) должно быть взаимно простым с размером хеш-таблицы Часть П1.
Структуры данных 304 Рис. 11.5. Вставка при двой- ном хешировании т (см. упражнение 11.4-3). Удобный способ обеспечить выполнение этого условия состоит в выборе числа т, равного степени 2, и разработке хеш-функции Йз таким образом, чтобы она возвращала только нечетные значения. Еще один способ состоит в использовании в качестве т простого числа и построении хешфункции Йз такой, чтобы она всегда возвращала натуральные числа, меньшие т.
Например, можно выбрать простое число в качестве т, а хеш-функции такими: Й1 (Й) = Й пюс1 сп, Йз (х) = 1 + (сс пюс1 т ), где гп' должно быть немного меньше т (например, т — 1). Скажем, если 1с = = 123456, т = 701, а т' = 700, то Й1()с) = 80 и Йз (Й) = 257, так что первой исследуемой будет ячейка в 80-й позиции, а затем будет исследоваться каждая 257-я (по модулю т) ячейка, пока не будет обнаружена пустая ячейка, или пока не окажутся исследованы все ячейки таблицы. Двойное хеширование превосходит линейное или квадратичное исследования в смысле количества 9 (гпз) последовательностей исследований, в то время как у упомянутых методов это количество равно О (гп). Это связано с тем, что каждая возможная пара (Й1 (к), Йз (к)) дает свою, отличающуюся от других последовательность исследований.
В результате производительность двойного хеширования достаточно близка к производительности "идеальной" схемы равномерного хеширования. Глава 11. Хеш-таблицы 305 Анализ хеширования с открытой адресацией Анализ открытой адресации, как и анализ метода цепочек, выполняется с использованием коэффициента заполнения а = и/т хеш-таблицы при п и т, стремящихся к бесконечности. Само собой разумеется, при использовании открытой адресации у нас может быть не более одного элемента на ячейку таблицы, так что п < т и, следовательно, гг < 1.
Будем считать, что используется равномерное хеширование. При такой идеализированной схеме последовательность исследований (й(к, О), Ь(1с, 1),..., й(к, т — 1)), используемая для вставки или поиска каждого ключа 1с, с равной вероятностью является одной из возможных перестановок (О, 1,..., т — 1). Разумеется, с каждым конкретным ключом связана единственная фиксированная последовательность исследований, так что при рассмотрении распределения вероятностей ключей и хеш-функций все последовательности исследований оказываются равновероятными.
Сейчас мы проанализируем математическое ожидание количества исследований для хеширования с открытой адресацией в предположении равномерного хеширования, и начнем с анализа количества исследований в случае неуспешного поиска. Теорема 11.6. Математическое ожидание количества исследований при неуспешном поиске в хеш-таблице с открытой адресацией и коэффициентом заполнения гг = и/гп < 1 в предположении равномерного хеширования не превышает 1/(1 — а). Доказательство. При неуспешном поиске каждая последовательность исследований завершается на пустой ячейке.
Определим случайную величину Х как равную количеству исследований, выполненных при неуспешном поиске, и события А; (1 = 1, 2,... ), заключающиеся в том, что было выполнено г-е исследование, и оно пришлось на занятую ячейку. Тогда событие (Х > г) представляет собой пересечение событий Аз Г1АзП... ОА; ~. Ограничим вероятность Рг (Х > г) путем ограничения вероятности Рг (Аз П Аз П... П А; ~ ). В соответствии с упражнением В.2-6, Рг(А~ ПАг П...г1А г) = Рг(А~) Рг(Аз ! А~) Рг(Аз ) А~ ОАз) .. ... Рг(А, г ~ А~ О Аз П... ПА, з) .
Поскольку всего имеется и элементов и т ячеек, Рг (А~) = п/т. Вероятность того, что будет выполнено у-е исследование (~ > 1) и что оно будет проведено над заполненной ячейкой (при этом первые у — 1 исследований проведены над заполненными ячейками), равна (и — у+ 1)/(гп — у+ 1). Эта вероятность определяется следующим образом: мы должны проверить один из оставшихся Часть 1П. Структуры данных 306 (и — (/ — 1)) элементов, а всего неисследованных к этому времени ячеек остается (гп — (з — 1)).
В соответствии с предположением о равномерном хешировании, вероятность равна отношению этих величин. Воспользовавшись тем фактом, что нз п < т для всех 0 < у < т следует соотношение (и — з)/(т — з) < и/т, для всех 1 < 1 < т мы получаем: и п — 1 п — 2 п — г+2 гп ~~1 Рг(Х >1) = — ° ... (~ ~ — ~ =сз' тл гп — 1 т — 2 т — 1+2 ~т/ Теперь мы можем использовать уравнение (В.24) для того, чтобы ограничить математическое ожидание количества исследований: 00 ОО 00 Е[Х] = ~~) Рг(Х >1) < ,') а' ' = ,') гг' =— з=1 в=! в=о Полученная граница 1+ а + аз + гзз +... имеет интуитивную интерпретацию.
Одно исследование выполняется всегда. С вероятностью, приблизительно равной а, первое исследование проводится над заполненной ячейкой, и требуется выполнение второго исследования. С вероятностью, приблизительно равной сР, две первые ячейки оказываются заполненными и требуется проведение третьего исследования, и т.д. Если а — константа, то теорема 11.6 предсказывает, что неуспешный поиск выполняется за время 0(1). Например, если хеш-таблица заполнена наполовину, то среднее количество исследований при неуспешном поиске не превышает 1/(1 — 0.5) = 2. При заполненности хеш-таблицы на 90% среднее количество исследований не превышает 1/11 — 0.9) = 10.
Теорема 1!.6 практически непосредственно дает нам оценку производительности процедуры НАзн 1нзвкт. Следствие 11.7. Вставка элемента в хеш-таблицу с открытой адресацией и коэффициентом заполнения гг в предположении равномерного хеширования, требует в среднем не более 1/(1 — а) исследований. Доказааельсаво. Элемент может быть вставлен в хеш-таблицу только в том случае, если в ней есть свободное место, так что а < 1. Вставка ключа требует проведения неуспешного поиска, за которым следует размещение ключа в найденной пустой ячейке. Следовательно, математическое ожидание количества исследований не превышает 1/(1 — а).
Вычисление математического ожидания количества исследований при успешном поиске требует немного больше усилий. Глава 11. Хеш-таблицы 307 Теорема 11.8. Математическое ожидание количества исследований прн удачном поиске в хеш-таблице с открытой адресацией и коэффициентом заполнения а < 1, в предположении равномерного хеширования и равновероятного поиска любого из ключей, не превышает 1 1 — 1п —. а 1 — а Доказательство.
Поиск ключа й выполняется с той же последовательностью исследований, что и его вставка. В соответствии со следствием 11.7, если к был (г + 1)-м ключом, вставленным в хеш-таблицу, то математическое ожидание количества проб при поиске )с не превышает 1/ (1 — г/т) = т/(тп — г).
Усреднение по всем п ключам в хеш-таблнце дает нам среднее количество исследований при удачном поиске: — —, =-(н -н„„), 1 т т 1 1 и т — г тт пт — г а 1=О 1=о где Н; = 2 ' т 1/.т' представляет собой г-е гармоническое число (определяемое у= уравнением (А.7)). Воспользовавшись методом ограничения суммы интегралом, описанном в разделе А.2 (неравенство (А.12)), получаем верхнюю границу математического ожидания количества исследований при удачном поиске: 1 1 1 1 — (Н,„— Н,„„) = — ~~~ — ( — (1/х) 0х = а а к а й=т-и+1 т-и 1 т 1 1 = -1и — = -1п —. а тп — п а 1 — а Если хеш-таблица заполнена наполовину, ожидаемое количество исследований при успешном поиске не превышает 1.387; при заполненности на 90% это количество не превышает 2.559. Упражнения 11.4-1. Рассмотрите вставку ключей 1О, 22, 31, 4, 15, 28, 17, 88, 59 в хеш-таблицу длины тп = 11 с открытой адресацией и вспомогательной хешфункцией Ь' (к) = lс шот1 тп.
Проиллюстрируйте результат вставки приведенного списка ключей при использовании линейного исследования, квадратичного исследования с ст = 1 и сз = 3, и двойного хеширования с Ьз (Й) = 1+ (Й шот1 (т — 1)). 1! .4-2. Запишите псевдокод процедуры Нлзн 13н.нте, описанной в тексте, и модифицируйте процедуру Клен 1нзект для обработки специального значения 0ЕЕЕТЕ0 (удален). 308 Часть И1. Структуры данных * 11.4-3. Предположим, что для разрешения коллизий мы используем двойное хеширование, те. хеш-функцию Ь (к, г) = 1Ь1 (и) + гЬз (и)) шоп т. Покажите, что если тп и Ьз (Й) для некоторого ключа /с имеют наибольший общий делитель д > 1, то неуспешный поиск ключа Ь проверяет (1/с~)-ю часть хеш-таблицы до того, как возвращается в ячейку Ь1 (й).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
