производящие функции для этих распределений вероятностей; уравнения (46) эквивалентны формуле

B{z)C{z) =ро9о + (qo -Poqo)z + qiz + =ро9о(1 - z) + zC{z). Поскольку В{1) = 1, можно записать B{z) = 1 + [z - l)D{z). Отсюда вытекает, что

\ -D[z) - \-D{zr

так как С(1) = 1. Среднее количество проб, необходимых для выборки, в соответствии с (45) составляет

1 + с (1) - 1 + - - 1 + 2iV 1 Б(1)

В связи с тем, что предполагается равновероятность всех хеш-последовательностей fli... йлг, имеем

Pk = Рг(для фиксированного j в точности к из а; равны j) следовательно,

ад. s,,., = (30,

и среднее количество проб согласно (48) составит

В состоянии ли читатель указать неверные рассуждения, вызвавшие отличие между полученным ответом и точным результатом в теореме К? (См. упр. 33.)

*Анализ одтимальности. Мы рассмотрели несколько примеров последовательностей проб для открытой адресации, в результате чего, естественно, возникает вопрос, какая из них наилучшая из возможных в некотором разумном смысле. Эта задача имеет интересную постановку, предложенную Д. Д. Ульманом (J. D. U11-man) [JACM 19 (1972), 569-575]: вместо того чтобы вычислять хеш-адрес h{K), мы отображаем каждый ключ К на перестановку множества {0,1,..., М -1}, которая представляет последовательность проб при использовании К. Каждой из М! перестановок назначена вероятность, и предполагается, что обобщенная хеш-функция выбирает каждую перестановку с этой вероятностью. Вопрос формулируется следующим образом: "Какое назначение вероятностей данным перестановкам даст наивысшую производительность, т. е. минимизирует соответствующие средние числа проб Сдг и Ср?\

Например, если назначить каждой перестановке вероятность 1/М!, то получится равномерное исследование, проанализированное в (32) и (34). Однако Ульманом был найден пример сМ = 4иЛ = 2, для которого Cj меньше, чем значение

I, полученное для равномерного исследования. Его построение назначает нулевые

значения всем перестановкам, кроме следующих шести.

Перестановка Вероятность Перестановка Вероятность

0 123 (1 + 2£)/6 1 0 3 2 (1 + 2£)/6

20 13 (1-е)/6 2 1 0 3 (1 -е)/6

30 12 (1-е)/6 3 1 0 2 (1 -б)/6

(52)

Грубо говоря, на первом шаге предпочтение отдается 2 или 3, а вторая проба всегда проверяет О или 1. Среднее количество проб, необходимых для вставки третьего элемента, Сз, равно I - € + 0{е), так что можно улучшить равномерное исследование, присвоив е малое положительное значение.

Однако соответствующее значение С[ для этих вероятностей составляет -Ь 0(e), что больше (значение для равномерного исследования). Ульман доказал, что любое назначение вероятностей, такое, что С < [М + 1)/{М -Ь 1 - N), для некоторого N всегда влечет справедливость С > (М--1)/(М--1-п) для некоторого п < N; нельзя все время побеждать равномерное хеширование...

В действительности количество проб при успешном поиске является лучшим критерием, чем С- Перестановки в (52) не приводят к улучшению значения Сдг для любых N, и Ульман предположил, что никакие назначения вероятностей не сделают Cn меньше, чем для равномерного исследования: {{М + 1)/N){Hm+\ - Hm+i-n)-Эндрю Яо (Andrew Yao) доказал асимптотическую форму этого утверждения, показав, что предельная цена при N = аМ и М -> оо всегда > j In [JACM 32 (1985), 687-693].

Строгую форму предположения Ульмана очень сложно доказать, в особенности потому, что существует много вариантов назначения вероятностей для получения эффекта равномерного исследования; нет необходимости назначать вероятности 1/М! каждой перестановке. Например, следующие назначения также дают эквивалент равномерного исследования.

Перестановка Вероятность Перестановка Вероятность

0 1 2 3 1/6 0 2 1 3 1/12

1 2 3 0 1/6 1 3 2 0 1/12 (53)

2 3 0 1 1/6 2 0 3 1 1/12

3 0 1 2 1/6 3 1 0 2 1/12

(Остальным шестнадцати перестановкам назначена нулевая вероятность.)

Следующая теорема характеризует все присвоения, дающие поведение равномерного исследования.

Теорема U. Назначив вероятности перестановкам, все () конфигурации пустых и занятых ячеек можно сделать равновероятными после N вставок для О < N < М тогда я только тогда, когда сумма вероятностей, назначенная всем перестановкам, первые N элементов которых являются членами данного N-элементного множества, равна 1/(д) для всех N и для всех N-элементных множеств.

Например, сумма вероятностей, назначенных каждой из 3!(М - 3)! перестановок, которые начинаются числами {0,1,2} в заданном порядке, должна составлять 1/() = 3!(Л/ - 3)!/Af!. Заметьте, что (53) удовлетворяет условию теоремы, поскольку 1/6-1- 1/12 - 1/4.

Доказательство. Пусть АС {0,1,..., М-1} и пусть П(Л) - множество всех перестановок, первые Л элементов которых являются членами А. Обозначим также через S{A) сумму вероятностей, назначенных этим перестановкам. Пусть Рк{А) - вероятность того, что первые \А\ вставок при гюмощи процедуры открытой адресации займут места, определенные множеством А, и последняя вставка при этом потребует ровно к проб. И, наконец, пусть Р{А) = Pi (А) + Р2{А)-\----. Доказательство проводится по индукции по iV > 1. Предположим, что

P{A) = S{A) = l/

для всех множеств Ас\А\ = п < N. Пусть В - некоторое iV-элементное множество. Тогда

Рк{В)= Е Рг{п)Р{В\{пк}),

АСВ 7гбП(Л)

где Рг(7г) представляет собой вероятность, назначенную перестановке тг, и тг/с - ее к-п элемент. По индукции

АСВ \N~l) 7гбП(Л) \А\=к

что равняется

Следовательно,

а это может быть равно тогда и только тогда, когда S(B) имеет корректное

значение.

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

1) Разумно потратить больше времени на вычисление хеш-функции, поскольку потери из-за плохого хеширования гораздо больше цены дополнительного времени, требуемого для аккурат1Юго вьшолнения вычислений.

2) Записи обычно группируются в страницы или блоки с тем, чтобы за один раз изв.лекать из внешней памяти несколько записей.

Файл делится на М блоков по Ь записей. Коллизии при этом не вызывают никаких проблем до тех пор, пока одинаковые хеш-адреса имеют не более Ь ключей. Похоже, что наилучшими методами разрешения коллизий являются следующие.

А) Использование цепочек с раздельными списками. Если в один и тот же блок попадает более b записей, в конце первого блока можно вставить ссылку на пе-реполняюш;ую запись. Такие переполняющие записи содержатся в специальной