Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 64
Текст из файла (страница 64)
В ходе дальнейшего анализа мы будем исходить из предположения равномерного хеширования, т.е. мы предполагаем, что для каждого ключа в качестве последовательности исследований равновероятны все т! перестановок множества (О, 1,..., т — 1). Равномерное хеширование представляет собой обобщение определенного ранее простого равномерного хеширования, заключающееся в том, что теперь хеш-функция дает не одно значение, а целую последовательность исследований.
Реализация истинно равномерного хеширования достаточно трудна, однако на практике используются подходящие аппроксимации (такие, например, как определенное ниже двойное хеширование). Мы рассмотрим три основных метода вычисления последовательности исследований для открытой адресации: линейное исследование, квадратичное исследование и двойное хеширование.
Эти методы гарантируют, что (Ь(Ь, 0), Ь(Ь, 1), ..., Ь(Ь, т — 1)) является перестановкой для каждого ключа Ь. Однако эти методы не удовлетворяют предположению о равномерном хешировании, так как ни один из них не в состоянии сгенерировать более тз различных последовательностей исследований (вместо т!, требующихся для равномерного хеширования). Наибольшее количество последовательностей исследований и, как и следовало ожидать, наилучшие результаты дает двойное хеширование. Линейное исследование Пусть задана обычная хеш-функция Ь': У вЂ” ~ (О, 1,...,т — Ц, которую мы будем в дальнейшем именовать оснимоганзельной хенг-функцией (аих(1(агу (заз(з йгпсбоп).
Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию Ь(к,з) = (Ь (Й) + () шоб т для 1 = О, 1,..., т — 1. Для данного ключа Ь первой исследуемой ячейкой является Т[Ь'((с)], т.е. ячейка, которую дает вспомогательная хеш-функция. Далее мы исследуем ячейку Т[Ь'()г) + Ц и последовательно все до ячейки Т[т — Ц, после чего переходим в начало таблицы и последовательно исследуем ячейки Т[0), Т[Ц,..., пока не дойдем до ячейки Т[Ь'(к) — Ц. Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется т различных последовательностей. 305 Глава П. Хеширование и леш-тарличы Линейное исследование легко реализуется, однако при этом возникает проблема яервичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска.
Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют 1 заполненных ячеек, равна (1+ 1)/т. Таким обраюм, длинные серии заполненных ячеек имеют тенденцию ко все большему удлинению, что приводит к увеличению среднего времени поиска. Квадратичное исследование Квадратичное иссчедоаанце использует хеш-функцию вида Ь(Ь,1) = (Ь'(lс) + 011+ сзР) шое( т, (11.5) где Ь' — вспомогательная хеш-функция, сд и сз — положительные вспомогательные константы, а 1 = О, 1,..., гп — 1. Начальная исследуемая ячейка — Т[Ь'(Ь)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования 1.
Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений сы сз и гп (в задаче 1! .3 показан один из путей выбора этих параметров). Кроме того, если два ключа имеют одну и ту же начальную позицию исследования, то одинаювы и последовательности исследования в целом, так как из Ь(йы 0) = Ь(Ьз, 0) вытекает Ь(йы 1) = Ь(/сз,з). Это свойство приводит к более мягкой вторичной кластеризации. Как и в случае линейного исследования, начальная ячейка определяет всю последовательность, поэтому всего используется гп различных последовательностей исследования. Двойное хеширование Двойное хеширование представляет собой один из наилучших способов использования открьпой адресации, поскольку получаемые при этом перестановки обладают многимн характеристиками случайно выбираемых перестановок. Двойное хеширование использует хеш-функцию вида Ь(к,1) = (Ьз(Ь) + 1Ьз(Ь)) гпос1 т, где и Ьм и Ьз — вспомогательные хеш-функции.
Начальное исследование выполняется в позиции Т[Ьз(Ь)), а смещение каждой из последуюших исследуемых ячеек относительно предыдущей равно Ьз(к) по модулю гп. Следовательно, в отличие от линейного и квадратичного исследования, в данном случае последовательность исследования зависит от ключа Ь по двум параметрам — в плане выбора начальной исследуемой ячейки и расстояния между соседними исследуемыми ячейками, так как оба эти параметра зависят от значения ключа.
На рис. 1! .5 приведен пример вставки при двойном хешировании. Для того чтобы последовательность исследования могла охватить всю таблицу, значение Ьз(Ь) должно быть взаимно простым с размером хеш-таблицы гп Часть 1!!. Сврулмзрм давних збб ~ 10 11 10 12 Рис. 11.5. Вставка при лвойном хешировании. Здесь показана хеш-таблица размером 13 ячеек, в козорой нспользузогся хеш-функции Ьг(!г) = й шог) 13 и Ьз()г) = 1 + (Ь шод 11). Тек как 14 ш 1 (шоб 13) и 14 = 3 (шод 11), ключ 14 вставляется в пустую ячейку 9, после гого как при исследовании ячеек 1 и 3 вьшсняегся, что зги ячейки заюпм. (см.
упр. 11.4.4). Удобный способ обеспечить выполнение зтого условия состоит в выборе числа т, равного степени 2, и разработке хеш-функции Ьз таким образом, чтобы она возвращала только нечетные значения. Еще один способ состоит в использовании в качестве т простого числа и построении хеш-функции Ьз, такой, чтобы она всегда возвращала натуральные числа, меньшие т. Например, можно выбрать простое т и хещ-функции Ьз(Ь) = Ь пзог) ги, Ьз(к) = 1 + (й гпог)т ), где т' должно быть немного меньше гп (скажем, т — 1).
Например, если /с = 128456, т = 701, а т' = 700, мы имеем Ьг(!с) = 80 и Ьз()с) = 257, так что первой исследуемой будет ячейка в 80-й позиции, а затем будет исследоваться каждая 257-я (по модулю т) ячейка, пока ие будет обнаружена пустая ячейка или пока не будут исследованы все ячейки таблицы. Когда т простое или представляет собой степень 2, двойное хеширование превосходит линейное или юшдратичное исследования в смысле количества сз(т~) последовательностей исследований, в то время как у упомянутых методов зто количество равно Й(т), поскольку каждая возможная пара (Ь1()с), Ьз(Ь)) дает отличную от других последовательность исследований.
В результате для таких значений т произвгщительность двойного хеширования достаточно близка к производительности "идеальной" схемы равномерного хеширования. Хотя в принципе для двойного хеширования могут использоваться значения т, отличные от простых и степеней 2, на практике при этом становится труднее эффективно генерировать Ьз(!с) так, чтобы гарантировать взаимную простоту с т, Глава !!.
Хешиваваиие и «еш-таблицы 307 в частности из-за того, что относительная плотность ф(т)/т таких чисел может быть малой (см. уравнение (31.24)). Анализ хеширования с открытой адресацией Анализ открытой адресации, как и анализ метода цепочек, выполняется с использованием коэффициента заполнения ел = и/т. Само собой разумеется, при использовании открытой адресации может быть не более одного элемента на ячейку таблицы, так что и < т и, следовательно, ее ( 1. Будем считать, что используется равномерное хеширование. При такой идеализированной схеме последовательность исследований (Ь(Ь, О), Ь(Ь, 1),..., Ь(Ь, т— 1)), используемая для вставки или поиска каждого ключа й, с равной вероятностью является одной из возможных перестановок (О, 1,..., т — 1).
Разумеется, с каждым конкретным ключом связана единственная фиксированная последовательность исследований, так что при рассмотрении распределения вероятностей ключей и хеш-функций все последовательности исследований оказываются равновероятными. Мы проанализируем математичесюе ожидание количества исследований для хеширования с открытой адресацией в предположении равномерного хеширования и начнем с анализа количества исследований в случае неудачного поиска. Теорема 11. 6 Математичесюе ожидание количества исследований при неудачном поиске в хештаблице с открытой адресацией и коэффициентом заполнения ге = и/т ( 1 в предположении равномерного хеширования не превышает 1/(1 — е«). Доказалвельслвао.
При неудачном поиске каждая последовательность исследований завершается пустой ячейкой. Определим случайную величину Х как количество исследований, выполненных при неудачном поиске, и определим также события А; (1 = 1, 2,...), заключающиеся в том, что было выполнено в-е исследование, и оно пришлось на занятую ячейку. Тогда событие (Х > 1) представляет собой пересечение событий Аз П Аз О П А, г. Ограничим вероятность Рг (Х > 1) путем ограничения вероятности Рг (А1 О Аз О .. О А, г). В соответствии с упр. В.2.5 Рг(Аг О Аз О. ПА, 1) =Рг(Аг) Рг(Аз ~ А1) Рг(Аз ~ А! ПАз) Рг(А; г ~ Аг ОАзО ПА, з) . Поскольку всего имеется и элементов и т ячеек, Рг(Аг) = и/т.
Вероятность того, что будет выполнено 7>е исследование О > 1) и что оно будет проведено над заполненной ячейкой (при этом первые 7' — 1 исследований проведены над заполненными ячейками), равна (п — 7'+ 1)/(т — 7'+ 1). Эта вероятность определяется следующим образом: мы должны проверить один из оставшихся (п — Ц вЂ” 1)) элементов в одной из оставшихся к этому времени (т — (7' — 1)) неисследованных ячеек. В соответствии с предположением о равномерном хешировании искомая вероятность равна отношению этих величин. Воспользовавшись тем фактом, что зов Часть ДЕ Структуры оаниыт из и < ги для всех 0 < з < т следует соотношение (и — 1)/(т — 1) < и/т, для всех 1 < 1 < т получаем и и — 1 и — 2 и — 1+2 Рг(Х > г) — —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
