в дальнейших шагах Q на К.) Затем установить R <= AVAIL, TAG(R) •(- 1, AUX(R) •(- Q, LINK(R) •(- Л. Присвоить P <- h(K), a затем,

если TAG(P) = 0, установить TAG(P) •(- 2, AUX(P) •(- R;

если TAG(P) = 1, установить S <= AVAIL, CONTENTS(S) 4- CONTENTS(P), TAG(P) 2, AUX(P) •(- R, LINK(P) •(- S;

если TAG(P) = 2, установить LINK(R) •(- AUX(P), AUX(P) •(- R.

Для получения ключа К: установить Р •(- h{K) и,

если TAG(P) Ф 2, К отсутствует;

если TAG(P) = 2, установить Р •(- AUX(P), а затем присвоить Р •(- LINK(P) нуль или несколько раз до тех пор, пока не выполнится либо Р = Л, либо TAG(P) = 1, тогда либо AUX(P) = К (если все ключи коротки), либо AUX(P) указывает на слово, содержаш;ее К (возможно, косвенно через слово с TAG = 2).

В оригинальной схеме Элькока {Сотр. J. 8 (1965), 242-243] в действительности использовались TAG = 2 и TAG = 3 Для того, чтобы различить списки единичной длины (когда можно сохранить одно слово памяти) и более длинные списки. Это улучшение заслуживает внимания, поскольку мы предположительно работаем с такой большой хеш-таблицей, что почти все списки имеют единичные длины.

Другой путь размеш;ения хеш-таблицы "наверху" большой связанной памяти с использованием срастаюш;ихся списков вместо раздельных цепочек был предложен Дж. С. Вит-тером (J. S. Vitter) [Inf. Ргос. Letters 13 (1981), 77-79].

15. Зная о том, что всегда имеется свободный узел, можно сделать внутренний цикл более быстрым, поскольку нет необходимости в счетчике для определения, сколько раз был выполнен шаг L2. Более короткая программа компенсирует одну потерянную ячейку. (С другой стороны, в алгоритме L изящно указывается, как избежать использования переменной N и допустить полное заполнение таблицы без заметного замедления работы метода (за исключением случая реального переполнения таблицы): просто проверка г < О должна выполняться дважды! К алгоритму D этот трюк неприменим.)

16. Нет: О всегда приводит к метке SUCCESS, независимо от того, был ли он вставлен. В разные моменты мы попадаем на метку SUCCESS с различными значениями г.

17. Тогда вторая проба всегда будет обращаться к позиции 0.

18. "Стоимость" кода (31) на 3(Л - 51) единиц больше, чем стоимость кода (30); экономия при этом составляет 4и, умноженное на разность между (26), (27) и (28), (29). В случае успешного лоиска (31) предпочтительнее только тогда, когда таблица заполнена более чем на 94%; выигрыш при этом не превышает и. В случае неудачного поиска (31) предпочтительнее, если таблица заполнена более чем на 71%.

20. Мы хотим показать, что

(2) = (2) ™ """" " 1 < j < fc < 2™

влечет j = к. Заметим, что тождество j(j - 1) = к(к - 1) (по модулю 2"**) приводит к (fc ~ j)(fc + j - 1) =0- Если fc - j нечетно, fc -f- j - 1 должно быть кратно 2™"", но это невозможно, поскольку 2<fc-f-j-l< 2™"" - 2. Следовательно, к - j четно, так что fc -t- j - 1 нечетно и к - j кратно 2™+, откуда к = j. (И обратно, если М не является степенью 2, такая последовательность проб не будет работать.)

Эта последовательность проб имеет вторичную кластеризацию и приводит к увеличению времени работы программы D (модифицированной в соответствии с (30)) примерно на I (С - 1) - (А - 51) единиц, поскольку В « ()/М можно не принимать во внимание. Пока таблица не заполнена примерно на 60%, это дает небольшое улучшение работы.

21. При уменьшении N алгоритм D может некорректно работать, так как, достигнув состояния, в котором отсутствует пустое пространство, он зациклится. С другой стороны, если N не будет уменьшаться, алгоритм D может сообщить о переполнении при имеющемся свободном пространстве. Причем этот вариант - меньшее из двух зол, поскольку для освобождения от удаленных ячеек можно воспользоваться рехешированием (в этом случае алгоритм D должен увеличивать N и проверять переполнение только при вставке элемента в пустую позицию, так как N - количество непустых позиций). В программе также можно поддерживать два счетчика.

22. Предположим, что позиции j - 1, j - 2, j - k заняты, а j - - 1 пуста по модулю М. Ключи, которые проверяют позицию j и находят ее занятой перед вставкой, совпадают с ключами в позициях от j - 1 до j - fc, хеш-адреса которых не лежат между j - 1 и j - fc; такие "проблематичные" ключи появляются в порядке вставки. Алгоритм R перемещает первый такой ключ в позицию j и повторяет процесс на меньшем диапазоне проблематичных позиций до тех пор, пока будет оставаться хоть один проблематичный ключ.

23. Схема удаления для срастающихся цепочек, изобретенная Дж. С.-Виттером (J. S. Vitter) [J. Algorithms 3 (1982), 261-275], сохраняет распределение времен поиска.

24. Р{Р-1)(Р-2)Р{Р-1)Р{Р-1)/(МР{МР-1)... (МР-6)) = M-(l-(5-21/iW")p-4 0(Р~)). Вобщем, вероятность появления хеш-последовательности ai... ал? равна(П]1о х xPi)/(MP)- = М- + 0{Р-), где bj - количество щ, равных j.

25. Пусть (TV + 1)-й ключ хешируется в позицию а; Pk равно iVf умноженному на количество хеш-последовательностей, которые оставляют fc позиций а, о - 1, ...,а - fc-1-l (по модулю М) занятыми, а о - fc - пустой. Количество таких последовательностей с занятыми 0+1, ..., о-1-t и пустой o-f-t-f-1 равно g{M,N, t+k) в силу циклической симметрии алгоритма.

26. ?jj/(3, 2)/(3, 2)/(5,4)/(2,1) = 22357 = 4 252 500.

27. Следуя указанию, находим

s(n,x, y) = Y, {1)х{х+к){у-кГ--(у-п)+п g~ J) ix+kyiy-kr-- (у-п).

В первой сумме заменим fc на п - fc и Применим формулу Абеля; во второй заменим к на к + 1. Теперь

g{M,N,k) = ()(fc + 1)*-(М - fc - 1)-*-(М - TV - 1) с О/О = 1 при fc = TV = M- lH

M(fc+ 1)Р. = Y1 {)9{M,N,k)

к>0

Vfc>o k>o /

Первая сумма равна iW" I] Pfc = вторая - «(TV, l,iW"-l) = M-(-2TVM-43A(A-1)М- + = MQi{M,N). (См. J. Riordan, Combinatoriai Identities (New York: Wiley, 1968), 18-23; здесь приводится дополнительная информация о суммах наподобие s(n, х, у).)

28. Пусть t(n, х,у) = Ykyo 0( + =)"(у-=)"~°~Чу-"); тогда, как и в упр. 27, находим t(n,x,y) = xs(n,x,y) + nt(n-l,x+l,y-l), t(TV,l,M-l) = М(здз(М,TV) - 2Q2(M,TV)). Значит, + = M- Yijik + If + \ik + if + (fc + 1))9{M,N,fc) = Q3(M,TV) -

Q2(M,iV) + \Q\{M,N) + . Вычитание {СТ дает дисперсию, приближенно равную (1 - сс)~ - (1 - сс)" - j. Стандартное отклонение зачастую больше среднего значения, например при а = .9 среднее значение равно 50.5, а стандартное отклонение - i\/27333 w 82.7.

29. Пусть М = т + 1, N = п\ последовательность парковки та же, что и при применении алгоритма L к хеш-последовательности (М - oi)...(M - Оп), при которой позиция О остается пустой. Следовательно, искомый ответ - /(т-(-1, п) = {т + 1)" - п{т -(-1)"". [Эта задача была поставлена в работе А. G. Konheim and В. Weiss, SIAJVf J. Applied JVfath. 14 (1966), 1266-1274; см. также R. Руке, Annals of Math. Stat. 30 (1959), 568-576, лемма 1.]

30. Очевидно, что если машины припарковались, то они определяют такую перестановку. И обратно, если имеется перестановка piP2 .. - Рп, пусть qiqi.. .Qn означает обратную перестановку (qt = j тогда и только тогда, когда pj = г) и пусть bi - количество Oj, равных г. Каждый автомобиль припаркуется, если мы докажем, что Ь„ < 1, b„-i + b„ < 2 и т. д. (что эквивалентно bi > 1, bi -Ь 62 > 2 и т. д.). Но это, очевидно, истинно, поскольку все к элементов a<,i, ..., о,,, не больше к.

[Пусть Tj означает "левое влияние" qj, а именно г , = к тогда и только тогда, когда qj-i < qj, 4j-k-i < Qj и либо j = к, либо qj-k > Qj- Из всех перестановок pi...p„, мажорируюш;их данную последовательность пробуждений ai... о„, алгоритм "немедленно остановись!" находит наименьшую (в лексикографическом порядке). Конхейм и Вейсс заметили, что количество последовательностей пробуждений, приводящих к данной перестановке Pl... Рп, равно П7=1 j интересно, что сумма этих произведений, взятая по всем перестановкам qi... qn, равна (п + 1)"~.]

31. Таких возможных связей много, но следующие три - любимые автором [см. также Foata and Riordan, quat. JVfath. 10 (1974), 10-22].

a) В обозначениях из предыдущего ответа счетчики bi,b2,... ,Ьп соответствуют полной последовательности парковок тогда и только тогда, когда (61,62,.., Ьп, 0) представляет собой корректную последовательность степеней узлов дерева в прямом порядке. (Сравните с 2.3.3-(9), иллюстрирующим обратный порядок.) Каждое такое дерево соответствует n!/6i!... 6„! различным помеченным свободным деревьям на {О,..., п}, поскольку можно пометить корень нулем, а для к = 1,2, ...,п последовательно в прямом порядке выбирать метки из оставшихся неиспользованными, из дочерних узлов fc-ro узла (Ьк + + ЬпУ./Ьк\ (6fc+i -)-•• + ЬпУ. способами, назначая метки слева направо в порядке возрастания. Каждая такая последовательность счетчиков соответствует n!/6i!.. .6„! последовательностям пробуждения.

b) Доминик Фоата (Dominique Foata) дал следующее красивое взаимно однозначное соответствие. Пусть ai... On - удачная последовательность парковок, при которой машина qj располагается в позиции j. Помеченное свободное дерево на {0,1,..., п} строится с помощью линий, проведенных из j в О при Oj = 1 и из j в ga,-i в противном случае для 1 < j < п. (Будем считать узлы дерева автомобилями; автомобиль j связан с автомобилем, который припарковался именно в том месте, где проснулась j-я жена.) Например, моменты пробуждений 314159265 приводят согласно правилу Фоата к построению свободного дерева

И обратно: последовательность припаркованных автомобилей может быть получена из дерева методом топологической сортировки в предположении, что стрелки указывают от