Как и в программе С, переменная С описывает количество проб, а 5 указывает, успешным ли был поиск. Проигнорировать переменную Е, которая равна 1, можно только в случае проверки фиктивного узла TABLE [-1]; ее среднее значение равно {С - 1)/М.

Опыты с линейным исследованием показывают, что алгоритм хорошо работает в начале заполнения таблицы, однако по мере заполнения процесс замедляется, а длинные серии проб становятся все более частыми. Причину такого поведения можно понять, рассмотрев следующую гипотетическую хеш-таблицу при М = 19 и N = 9.

0 12 3 4

б 7 8 9 10 11 12 13 14 15 16 17 18

(21)

Темные квадраты представляют собой занятые позиции. Следующий ключ К, вставляемый в таблицу, попадет в одно из десяти пустых мест, которые, однако, отнюдь не равновероятны. Так, К будет вставлен в позицию И при И < h{K) < 15, в то время как в позицию 8 он попадет, только когда h{K) = 8. Следовательно, вероятность попадания в ячейку 11 в пять раз больше, чем вероятность попадания в ячейку 8; общая тенденция такова, что длинные списки стремятся стать еще длиннее.

Этого явления, тем не менее, самого по себе недостаточно для описания происходящего, поскольку подобная ситуация складывается и при использовании алгоритма С (вероятность увеличения списка из четырех элементов в четыре раза больше вероятности увеличения списка из одного элемента). Впрочем, настоящие неприятности начинаются при вставке в ячейку типа 4 или 16, когда разные списки объединятся в один (в то время как в алгоритме С списки никогда не удлинялись при вставке более чем на 1 элемент). Следовательно, при приближении N к М производительность алгоритма резко снижается,

Ниже в этом разделе будет доказано, что среднее количество проб, требуемое алгоритмом L, составляет примерно

(неудачный поиск).

(успешный поиск).

(22) (23)

где а = N/M - коэффициент заполненности таблицы. Таким образом, программа L практически столь же быстра, как и программа С при заполненности таблицы менее чем на 75%, несмотря на то что программа С работает с неправдоподобно короткими ключами. С другой стороны, когда а 1, лучшее, что можно сказать о программе L, - это то, что она работает медленно, но верно. В самом деле, при N = М - I в таблице имеется только одно вакантное место, а потому среднее число проверок при неудачном поиске составит (М + 1)/2; мы докажем также, что среднее количество проб при успешном поиске в заполненной таблице равно примерно у/тгМ/8.

Явление скучивания, которое делает линейное исследование дорогостоящим при почти заполненных таблицах, усугубляется при хешировании методом деления, если вероятно появление последовательных значений ключей {К, К+1, К+2,...}, поскольку эти ключи будут иметь последовательные хеш-коды. Мультипликативное хеширование позволяет успешно разбить такие кластеры.

Другой путь защиты от последовательных хеш-кодов состоит в установке на шаге L3 г <- г - с вместо г <- г - 1. Можно использовать любое положительное значение с, взаимно простое с М, поскольку последовательность проб в этом случае будет проверять в конечном счете все позиции таблицы без исключения. Такое изменение немного замедлит работу программы L из-за проверки г < 0. Уменьшение на с вместо уменьшения на 1 не устранит явление скучивания, так как теперь будут формироваться группы записей на расстоянии с одна от другой; формулы (22) и (23) останутся приемлемыми. Однако в этой ситуации последовательные ключи {К, К+1, К+2,...} станут не помехой, а помощниками.

Хотя фиксированное значение с не приводит к устранению скучивания, можно существенно улучшить ситуацию, сделав с зависящим от К. Эта идея позволяет выполнить важную модификацию алгоритма L, впервые предложенного Гюи деВальбином (Guy deBalbine) [Ph. D. thesis, Cahf. Inst, of Technology (1968), 149-150].

Алгоритм D (Открытая адресация с двойным хешированием). Этот алгоритм почти идентичен алгоритму L, но проверяет таблицу немного иначе, используя две хеш-функции: hi(K) и h2(K). Как обычно, значения hi(K) находятся в диапазоне от О до М - 1 включительно; функция h2(K) должна порождать значения от 1 до М - 1, взаимно простые с М. (Например, если М простое число, то h2(K) может быть любой величиной от 1 до М- 1 включительно; или, если М = 2"*, h2(K) может быть любым нечетным числом от 1 до 2™ - 1.) D1. [Первое хеширование.] Установить г <- hi(K).

D2. [Первая проба.] Если TABLE [г] пуст, перейти к шагу D6. В противном случае,

если KEY [г] = К, алгоритм завершается успешно. D3. [Второе хеширование.] Установить с <- h2(K).

D4. [Переход к следующему.] Установить i <- г -с; если после этого г < О, установить г <- г + М.

D5. [Сравнение.] Если TABLE [г] пуст, перейти к шагу D6. В противном случае, если KEY [г] = К, алгоритм завершается успешно; иначе - вернуться к шагу D4.

D6. [Вставка.] Если N - М - 1, выполнение алгоритма прекращается в связи с переполнением. В противном случае установить Л <- Л -f 1, пометить узел TABLE [г] как занятый и установить KEY [г] <- К.

Для вычисления h2{K) было предложено несколько различных вариантов. Если М - простое число и hi{K) = К mod М, можно положить к2{К) = 1+ [К mod {М - 1)); однако, поскольку М-1 четно, было бы лучше положить h2{K) = 1 + [к mod (М - 2)). Это приводит к мысли о таком выборе М, что М и М - 2 были "простыми близнецами" наподобие 1021 и 1019. Кроме того, можно взять h2{K) = 1 + {[К/М\ mod (М - 2)) в связи с тем, что частное [К/М\ может быть получено в регистре как побочный результат вычисления hi {К).

Если М = 2"* и используется мультипликативное хеширование, h2{K) может быть вычислена методом простого сдвига на m дополнительных битов влево с выполнением операции "ИЛИ" с 1, так что к последовательности команд (5) необходимо добавить следующее.

ENTA о Очистить г А.

SLB т Сдвинуть гАХ на т бит влево. (24)

OR =1= гА<-гАУ1. Эти операции выполняются быстрее метода деления.

В каждом из предложенных выше методов hi{K) и h2{K) существенно независимы - в том смысле, что для различных ключей вероятность совпадения hi и h2 пропорциональна 1/М, а не 1/М. Эмпирические тесты показывают, что число проб в алгоритме D с независимыми хеш-функциями неотличимо от числа проб, требующихся при случайной вставке ключей в таблицу; в этой ситуации практически отсутствует "скучивание" или "кластеризация" как в алгоритме L.

Можно также допустить зависимость h2{K) от hi{K), как было предложено Гари Кноттом (Gary Knott) в 1968 году; например, при простом М можно положить

Г1, если hi{K) = 0; , .

-\M-hi{K), eainhiiK)>0. >

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

Алгоритмы L и D очень похожи, однако между ними найдется достаточно различий, чтобы было полезно сравнить время работы соответствующих М1Х-программ.

Программа D (Открытая адресация с двойным хешированием). Поскольку эта программа очень похожа на программу L, она представлена здесь без комментариев. В программе г12 = с - 1.