Алгоритмы - построение и анализ (1021735), страница 59
Текст из файла (страница 59)
Для вычисления последовательности исследований для открытой адресации обычно используются три метода: линейное исследование, квадратичное исследование и двойное хеширование. Эти методы гарантируют, что для каждого ключа Ь (Ь ()с,О), Ь (й, 1),..., Ь (Ь, т — 1)) является перестановкой (О, 1,..., т — 1). Однако эти методы не удовлетворяют предположению о равномерном хешировании, так как ни один из них не в состоянии сгенерировать более тз различных последовательностей исследований (вместо т!, требующихся для равномерного хеширования). Наибольшее количество последовательностей исследований дает двойное хеширование и, как и следовало ожидать, дает наилучшие результаты. Линейное исследование Пусть задана обычная хеш-функция Ь': У вЂ” (О, 1,..., т — 1), которую мы будем в дальнейшем именовать вспомогательной хеш-функцией (апх1!1агу Ьай бшсбоп).
Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию Ь(к,() = (Ь'(Ь) + !) шой т, где 1 принимает значения от О до т — 1 включительно. Для данного ключа к первой исследуемой ячейкой является Т [Ь' (к)], т.е. ячейка, которую дает вспомогательная хеш-функцня. Далее мы исследуем ячейку Т «Ь' (!с) + 1] и далее последовательно все до ячейки Т [т — 1], после чего переходим в начало таблицы и последовательно исследуем ячейки Т [0], Т [1], и так до ячейки Т [Ь' (Ь) — 1]. Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется т различных последовательностей.
Линейное исследование легко реализуется, однако с ним связана проблема первичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска. Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют 1 заполненных ячеек, равна (1 + 1)/т. Таким образом, длинные серии заполненных ячеек имеют тенденцию ко все большему удлинению, что приводит к увеличению среднего времени поиска.
Глава 11. Хеш-таблицы 303 Квадратичное исследование Квадратичное исследование использует хеш-функцию вида Ь(К,1) = (Ь'(й) + сг1+ сг1 ) шос1 т, (11.5) где Ь' — вспомогательная хеш-функция, с1 и сг ф 0 — вспомогательные константы, а 1 принимает значения от 0 до т — 1 включительно. Начальная исследуемая ячейка — Т [Ь' ()с)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования С Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений сы сг и т (в задаче 11-3 показан один из путей выбора этих параметров).
Кроме того, если два ключа имеют одну и то же начальную позицию исследования, то одинаковы и последовательности исследования в целом, так как из Ь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п —.