= рЕ (36)

*:=0

так что можно вывести одну величину из другой, как в (34).

Строго говоря, даже эта уточненная модель не лишена недостатков. Первый из них заключается в том, что не все хеш-последовательности равновероятны, поскольку сами ключи различны. Это делает вероятность того, что ах =02, немного меньше, чем 1/М; однако отличие обычно незначительно, поскольку количество всех различных ключей, как правило, гораздо больше, чем М (см. упр. 24). Более того, хорошая хеш-функция способна использовать неслучайность типичных данных, дополнительно уменьшая вероятность того, что ах = «г; таким образом, оценки числа проб будут пессимистическими. Другая неточность модели указана на рис. 43: ключи, встретившиеся ранее (за небольшими исключениями), ищутся чаще других. Таким образом, оценки Cn окажутся дважды пессимистичными и на практике алгоритмы будут иметь большую производительность, чем предсказано в результате нашего анализа.

С учетом этих предостережений можно приступать к "точному" анализу линейного исследования*. Пусть f{M,N) - число хеш-последовательностей (35), таких, что позиция О таблицы будет пуста после вставки ключей с помощью алгоритма L. Из циклической симметрии линейного исследования следует, что позиция О пуста так же часто, как и любая другая позиция, поэтому она пуста с вероятностью 1 - N/M; другими словами

f{M,N)(l-)M. (37)

По определению также полагаем, что /(0,0) = 1. Пусть g{M,N,k) - число хеш-последовательностей (35), таких, что алгоритм оставляет позицию О пустой, позиции от 1 до занятыми и позицию к+1 - пустой. Имеем

g{M,N,k) = ()/(fc + l,fc)/(M-fc-l,iV-fc), (38)

поскольку все такие хеш-последовательности состоят из двух подпоследовательностей. Первая (в ней содержится к элементов а, < к) оставляет позицию О пустой, а позиции от 1 до занятыми; вторая (в ней содержится N - к элементов aj > fc + 1) оставляет позицию fc + 1 пустой. Существует /(fc+1, fc) последовательностей первого типа, f{M-k-l,N-k) последовательностей второго типа и () способов их смешения. И, наконец, положим Pf. равным вероятности того, что при вставке (Л + 1)-го ключа требуется в точности fc + 1 проб. Отсюда следует (см. упр. 25), что

Pk = М{д{М, N, k)+g{M,N,k+l) + ---+ д{М, N, N)). (39)

Теперь Cn = Yl!=oi + 1)-*:; с учетом формул (36)-(39) и после определенных упрощений получим следующий результат.

* Автор не может не сделать вставку автобиографического характера: я впервые сформулировал предлагаемый вывод в 1962 году, вскоре после начала работы над Искусством прогр&ммирова-иия". Поскольку это был первый успешно проанализированный мною нетривиальный алгоритм, он оказал сильное влияние на стоуктуоу этих книг. Даже сейчас анализ алгоритмов остается одним из главных занятий в моей жизни.

Теорема К. Среднее количество проб, необходимых при использовании алгоритма L в предположении равновероятности всех хеш-последовательностей (35), составляет

Cn = 1(1 + QoiM,N-l)) (успешный поиск), Cjr = i (1 + Ql(М, N)) (неудачный поиск).

Qr{M,N) =

fr + l\N /r + 2\iV(iV-l)

/г + 1\ I 1 )

E/r k\ N N - 1 ,[ к JM~Af

fc>0

JV-fc + l M

(40) (41)

(42)

Доказательство. Подробные вычисления проведены в упр. 27 (информацию об отклонении можно найти в упр. 28, 67 и 68).

Странная функция Qr{M,N), которая появилась в теореме, только выглядит страшно; с ней вполне можно работать. Имеем

(2)*" < N{N-1)...{N-к-1) <N>;

следовательно, если N/M = а, то г + к

fc>0

*:>0

к J \ \2J ) I \ к }

г + к\ и а(г + к\(к\ jt 2 /,.г +к

к>0

к>0

т. е.

1 (г + 2\ а

<Qr{M,aM) <

(43)

(1-а)+1 М\ 2 Л1-аУ+ {1-аУ+

Это соотношение дает хорошую оценку Qr{M,N) при больших М и а, не слишком близком к 1 (нижняя оценка более точная, чем верхняя). При а -> 1 эти формулы становятся непригодными, но, к счастью, Qo{M, М - 1) представляет собой функцию Q{M), асимптотическое поведение которой детально рассматривалось в разделе 1.2.11.3; Q\{M, М-1) просто равно М (см. упр. 50). В стандартных обозначениях гипергеометрических функций 1.2.6-39 имеем Qr{M,N) = F{r -Ь 1, -N, 1, -1/М) =

r+l,-N,l 1

J )*

м)

Другой подход к анализу линейного исследования был предложен Г. Шеем (мл.) (G. Schay, Jr.) [САСМ 5 и В. Г. Спрутом (W. G. Spruth) (1962), 459-462]. Хотя их метод дает только приближение к точным формулам теоремы К, он проливает дополнительный свет на алгоритм, а потому мы вкратце изложим его. Сперва рассмотрим удивительное свойство линейного исследования, впервые отмеченное В. В. Петерсоном (W. W. Peterson) в 1957 году.

F{x,y,a,b)= Z к=0

- i + f+oj + • • - стандартное обозначение для

гипергеометрической функции. - Прим. перев.

Теорема P. Среднее количество проб при успешном поиске с помощью алгоритма L не зависит от порядка, в котором ключи были вставлены; он зависит только от числа ключей с тем или иным хеш-адресом.

Другими словами, любое переупорядочение хеш-последовательности aia .. .а дает хеш-последовательность с тем же средним смещением ключей от их хеш-адресов. (Предполагается, как упоминалось ранее, что все ключи в таблице одинаково важны. Если обращение к одним ключам происходит чаще, чем к другим, то, используя метод доказательства теоре.мы 6.IS, можно показать, что оптимальное расположение ключей достигается при их вставке в порядке уменьшения частот.)

Доказательство. Достаточно показать, что общее количество проб, необходимых для вставки ключей для хеш-последовательности ai 0-2 .. .а, такое же, как и для последовательности fli... flj-i aj+i Oi. -On, I < г < N. Очевидно, что нет никаких отличий между этими двумя случаями, пока (г--1)-й ключ второй последовательности не попадает в позицию, занимаемую г-м ключом в первой последовательности. Однако тогда г- и (г -Ь 1)-й элементы просто .меняются местами, так что количество проб для (г -Ь 1)-го ключа уменьшается на столько же, на ско.лько увеличивается число для г-го ключа.

Согласно теореме Р средняя длина поиска для хеш-последовательности ai аг • • aj\f может быть определена из чисел 6o6i...6m-i, где bj представляет собой количество элементов а, равных j. По этой последовательности можно определить "последовательность переносов" со ci... см-i, где Cj равно числу ключей, для которых при вставке ключа проверяются обе позиции {j и j - 1). Эта последовательность определяется правилом

Г О, если bj = C(j+]) mod м = 0;

[bj -\- C(j+i) mod Л/ - 1 В противном случае.

Например, пусть М = 10, iVSnbo-.. 69 = 032010000 2; тогда Со ... Cg = 2 3 1 0 0 0 0 1 2 3, поскольку один ключ должен быть перенесен из позиции 2 в позицию 1, три - из позиции 1 в позицию О, два - из позиции О в позицию 9 и т. д. Имеем Ьо + bi -Ь • • -Ь Ьм-1 = N, и среднее количество проб, необходимых для выборки N ключей, составляет

1-Ь(со-Ьс1-b-.-bCM-O/iV. (45)

Кажется, что правило (44) представляет собой циклическое опреде.ление чисел с через самих себя, но в действительности при любом N < М система имеет единственное решение (см. упр. 32).

Шей и Спрут использовали эту идею для определения вероятности д/. того, что Cj = к через вероятности pk того, что bj = к. (Эти вероятности не зависят от j.) Таким образом,

qo =poqo + Piqo +роди

Qi = Р2до + PiQi + PoQi, (46)

92 = РзЯо + Р2Ч\ +Р\Ч2+ РоЯз

и т. д., поскольку, например, вероятность того, что Cj = 2, представляет собой вероятность того, что 6j-bc(j+i) mod м = 3. Пусть Б(г) = Хрг* и C{z) = Qkz -