19 JE SUCCESS C-l 24 DECX 1 1-5

20 LDX TABLE, 1 С -1 - 52 25 STX VACANCIES 1-5

21 JXNZ 3B С -1 - 52 25 LDA К 1-5

22 4H LDX VACANCIES 1-5 27 STA TABLE, 1 1-5

23 JXZ OVERFLOW 1-5

Счетчики частот A, С, 51, 52 здесь имеют тот же смысл, что и в программе С, приведенной выше. Еще одна переменная. В, в среднем примерно равна {С - 1)12 (если ограничить диапазон значений h2{K) до, скажем, 1 < hiiK) < М/2, В уменьшится до (С - 1)/4; такое увеличение скорости, вероятно, не компенсируется заметным увеличением числа проб). Если в таблице N = аМ ключей, среднее значение А, конечно, равно а при неудачном поиске и Л = Г - в случае поиска успешного. Как и в алгоритме С, среднее значение 51 при успешном поиске составляет 1 - {{N - 1)/М) SS 1 - а. Среднее число проб трудно установить точно, однако эмпирические тесты показывают хорошую согласованность с формулами, выведенными ниже для "равномерного исследования" при независимых hi{K) и hiK):

M+1-N (неудачный поиск), (26)

Сдг = (Hm+i-Hm+i-n) ~ -а~ In(l-a) (успешный поиск). (27)

Если h2{K) зависит от hi{K) согласно (25), вторичная кластеризация увеличивает (26) и (27) до

W (1-а)"-а-1п(1-а); (28)

Слг - 1 + Ям-ц-Ям+1-лг- ~{Hm+i-Hm+i-n)/N+0{N~)

W 1-1п(1-а)-а (29)

(см. упр. 44). Заметим, что при заполнении таблицы данные значения Cn стремятся к Нм+1 - 1 и Нм+1 - I соответственно; это существенно лучше, чем при использовании алгоритма L, но не так хорошо, как в методе цепочек.

Поскольку каждая проба в алгоритме L отнимает немного меньше времени, двойное хеширование дает вьшгрыш только при заполненной таблице. На рис. 42 сравниваются средние значения времени работы программ L, D и модифицированной программы D (эта модификация влечет за собой вторичное скучивание; сама модификация сводится к замещению медленного вычисления h2{K) в строках 10-13 следующими командами.

ENN2 1-м, 1 с<- М -г.

J1NZ *+2 (30)

ENT2 О Если г = О, с <- 1.

Программа D требует в целом 8C-f 19Л+ B-f 26 - 135- 1751 единиц времени; модификация (30) позволяет сохранить около 15(Л - 51) w 7.5q времени при успешном завершении поиска. В данном случае вторичная кластеризация предпочтительнее независимого двойного хеширования.

Модифицированная программа D (30)

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Коэффициент заполненности, a = N/M

0.9 1.0

Рис. 42. Время успешного поиска трех схем открытой адресации.

На двоичном компьютере можно было бы увеличить скорость вычисления /12 (К) другим путем - заменив (если М - простое число, большее, чем, скажем, 512) строки 10-13 строками

AND =511= rA<-rAmod512.

STA *+1(0:2) (31)

ENT2 * с<-тА + 1.

Эта идея (предложенная Беллом (Bell) и Каманом (Кашап), САСМ 13 (1970), 675-677, которые независимо открыли алгоритм D) позволяет избежать вторичной кластеризации без затрат на повторное деление.

Для улучшения алгоритма L было предложено много других последовательностей проб, но ни одна из них не превосходит алгоритм D (за исключением, возможно, метода, описанного в упр. 20),

Используя относительный порядок ключей, можно уменьшить среднее время работы при неудачном поиске согласно алгоритму L или D до среднего времени работы при успешном поиске (см. упр. 66). Эта технология может с успехом применяться для решения задач, в которых неудачный поиск - обычное явление, более частое, чем поиск успешный; например, использует такой алгоритм при поиске исключений из своих правил переноса.

Изменение Брента. Ричард П. Брент (Richard Р. Brent) открыл такой способ модификации алгоритма D, при котором среднее время успешного поиска остается ограниченным при заполнении таблицы. Его метод [САСМ 16 (1973), 105-109] основан на том факте, что обычно успешный поиск встречается гораздо чаще вставок, а потому его предложение сводится к переносу основной работы на вставку элемента путем такого перемещения записей, чтобы уменьшилось ожидаемое время выборки.

Например, на рис. 43 показано, сколько раз каждый идентификатор встречался в типичной процедуре PL/I. Эти данные указывают на то, что компилятор PL/I, который использует хеш-таблицу для хранения имен переменных, будет обращаться к ней за многими именами пять и более раз, вставляя их всего однажды. В подобном исследовании Белл и Каман обнаружили, что компилятор COBOL использовал свой

в S Й g "S * " 5 3 5""

Рис. 43. Количество поисков имен переменных компилятором в типичном случае. Имена перечислены слева направо в порядке их первого появления в программе.

табличный алгоритм при компиляции 10988 раз, в то время как было сделано только 735 вставок в таблицу; следовательно, на одну вставку приходилось около 14 успешных поисков. Иногда таблица создается только один раз (например, таблица символов кодов операций в ассемблере) и используется исключительно для получения из нее данных.

Идея Брента заключается в изменении процесса вставки в алгоритме D, как показано ниже. Предположим, что при неудачном поиске были проверены ячейки Ро, Рь • • •, Pf-b Pt, где Pj = {hi{K) - jhiiK)) mod M и TABLE[pt] пуст Если t < 1, вставляем К в позицию pt, как обычно; однако, если t > 2, вычисляем cq = Н2{Ко), где Ко = KEY[po]i и смотрим, свободен ли узел TABLE [(ро - Со) mod М]. Если это так, помещаем в него TABLE[ро]) а затем вставляем К в позицию ро- Это приводит к увеличению времени выборки Ко на один шаг, но время выборки К уменьшается на i > 2 шагов, что приводит к общему выигрышу во времени выборки. Аналогично, если узел TABLE [(ро - со) mod М] занят и i > 3, проверяем узел TABLE С(ро - 2со) mod М]; если он также занят, вычисляем Ci = /i2(KEY[pi]), проверяем TABLEС(ро - Cl) mod М] и т. д. Вообще, пусть Cj = /i2(KEY[pj]) и pjk = {Pj -kcj) mod M; если для всех j и к, таких, что j + k < г, узлы TABLE [pj,fc] заняты и если i > г -f 1, просматриваем узлы TABLE[ро,г], TABLE[pi,r-i], ..., TABLE[р-ы] • Если первое пустое место оказывается в позиции Pj,r-j, устанавливаем TABLE [pj>-j] <-TABLE Cpj] и вставляем К в позицию pj.

Анализ Брента показывает, что среднее количество проб на один успешный поиск уменьшается до уровней, показанных на рис. 44 на с. 583, с максимальным значением, равным приблизительно 2.49.

Количество проб t+l при неудачном поиске в результате внесенных в алгоритм изменений осталось прежним; оно осталось на уровне, который определен формулой (26) и достигает (М-f 1) при заполпенности таблицы. Среднее количество