a = l

Решением поставленной задачи является m - l=opqG{m, п+1, к), что после некоторых преобразований становится равным т - ({т - п)/{т - п + l))(Qn + mR + pSR), где

Qj=Pj+i<f,

43. Пусть TV = аМ и М = /ЗМ и пусть e" + А = 1 3, р = а/р. Тогда Слг w 1 + р и Cjv и р + е-" прир < А; Слг и (е- - 1 2р + 2А)(3-2 3 + 2А) + i(p + 2A-Ар) и Cjv « 1 ? + 5(e2p-2A-l)(3-2 3+2A)-i(p-A) прир > А. Если а = 1, получим минимальное Слг w 1.69 при /3 w .853; наименьшее Cn w 1.79 получается при /3 w .782. Установив /3 = .86, можно получить близкую к оптимальной производительность для широкого диапазона а. Таким образом, помещение первых коллизий в область, не конфликтующую с хеш-адресами, оправдывается, даже если при меньшем диапазоне хеш-адресов получается больше коллизий. Приведенные результаты были получены Дж. С. Виттером (Jeffrey S. Vitter), JACM 30 (1983), 231-258.

44. (Рассмотренный здесь способ решения "в лоб" был найден автором в 1972 году; гораздо более элегантное решение М. С. Патерсона (М. S. Paterson) можно найти в книге Грина (Greene) и Кнута (Knuth) Mathematics for the Analysis of Algorithms (Birlchauser Boston, 1980), §3.4. Патерсон нашел также важные методы упрощения других способов выполнения анализа, описанных в этом разделе.)

Пронумеруем позиции массива от 1 до m слева направо. Рассматривая множество всех () последовательностей операций с к "р-шагами" пп - к "q-шагами" как равновероятные, обозначим через д(т,п+1, к,г) умноженную на () вероятность того, что первые г - 1 позиций становятся занятыми, а г-я осталась пуста. Таким образом, д(т,1,к,г) равна умноженной на (т - l)~(-i~=) сумме по всем конфигурациям

1 < Ш < •• < Ofc </, (ci,...,ci i fc), 2<Ci<m,

вероятностей того, что первая пустая позиция - г, когда о ,-я операция представляет собой р-шаг, а оставшиеся I - 1 - к операций представляют собой д-шаги, которые начинаются с выбора позиций ci, ..., Ci i fc соответственно. Выполнив суммирование по всем конфигурациям при дополнительном условии, что Oj-я операция занимает позицию bj при данных 1 < 6i < • • • < bfc < г, получим рекуррентное соотношение

д(т,1,к+1,г)= (7!;)(Ibj;("t-/ + l)g("t,a.fc,b);

1<Ь<а

д{т,I,О,г) = 1 (!!LzJi!( / +1) (Р, + [. 1](1 - Р,)) ,

где Pl = {т/{т- l))~ Обозначив G(m,l,k) = I]=i("* + - r)p(m,/, fc, г), получим, что

G{m, I, к+1) = "[l Т G(m, а, fc); G(m, 1,0) = Z~ llU" + m - l + 2 m - l + l

(l-l/(m + l-fc))g/c

+

~Sn;=o(i-p/("»+i-i))

При p = 1/m, Qj - 1 для всех j. Считая ш = m + 1, n = аш, ш -> оо, найдем In Д = -(Яи, - Яи,(1 а))р -(- О(р); следовательно, Д = 1 -(- ш" 1п(1 - а) -(- аналогично

S = ош + Таким образом, ответ будет таким: (1 - а)~ - 1 - о - 1п(1 - о) + 0(w~).

Примечание. Более простая задача "С вероятностью р займем крайнюю слева позицию; в противном случае займем случайным образом выбранную пустую позицию" решается, если принять Pj = 1 в приведенных выше формулах, и ответом будет т- {т + 1)(т - n)R/{m - п + 1). Чтобы получить Сдг для случайных проб с вторичной кластеризацией, установим п = N, пг = М и добавим 1 к приведенному выше ответу.

45. Да. См. L. Guibas, JACM 25 (1978), 544-555.

46. Определим числа [[]] для к>0 согласно правилу

= (х-Ь п Н-1)"

для всех X и всех целых неотрицательных п. Полагая х = -1,-2,...,-п - 1, получим, что

()(-l)(n-j)" дляО<Л<п.

Затем, рассматривая х = О, получим, что при к > п можно считать [[]] = О, так что обе части определяющего уравнения представляют собой полиномы от х степени п, совпадающие в п+1 точке. Отсюда следует, что числа [[]] обладают указанным свойством.

Пусть f{N, г) - количество хеш-последовательностей oi... одг, при которых первые г позиций заняты, а следующая - пустая. Существует (1~) способов размещения занятых ячеек, и каждый из них встречается столько раз, сколько имеется последовательностей ol .. .ам, 1 <ai < N, таких, что в каждой последовательности каждое из чисел г + 1, г + 2, ...,7V содержится хотя бы один раз. В соответствии с принципом включения-исключения имеется [[дЛ,.]] таких последовательностей. Таким образом.

Теперь

cM=i+M--j:fiN,r){j:r+ j:

а=г+1

= l + M--J2f{N,r){N + {N-l)r

Полагая Sn(x) = имеем

N N-r

(г + 1)

.)г).

-™.ЕГГ)[Н]=Е(Г*)

х + 1 + к

следовательно, Sn(x) = (х + 1)((х + п + 2)" - (х + п + 1)"). Отсюда вытекает, что Cn = N{1 + 1/М) - (TV - 1)(1 - 7V/M)(1 + l/M)" я; 7V(1 - (1 - а)е°) и Cn = {N - 1)((1 +

1/М)/2 + (1 + l/M)) + (ЗМ + бМ + 2)((1 + - 1)/N - (ЗМ + 2)(1 + 1/М) что

равно (е - 2.5)М + 0(1) при iV = М - 1.

О других свойствах чисел [[J] можно прочесть в книге John Riordan, Combinatoriai Identities (New York; Wiley, 1968), 228-229.

47. Практически так же применим анализ алгоритма L! Любая последовательность проб с циклической симметрией, которая проверяет только соседние с ранее проверенными позиции, будет вести себя точно так же.

48. Cn = 1 + р + + , где р = N/M представляет собой вероятность того, что случайная позиция заполнена; следовательно, Cn = М/(М - N) и Cn - Ylk=o к - N-M{Hm -Hm-n). Эти значения приблизительно равны значениям при равномерном исследовании, но несколько выше за счет возможности повторного опробования одного и того же места. В действительности при 4 = iV < М < 16 линейное исследование имеет лучшие характеристики!

На практике нельзя применять бесконечно много хеш-функций; в качестве последнего средства должна использоваться другая схема - схема наподобие линейного исследования. Этот метод хуже описанных в тексте и представляет только историческую ценность, так как он послужил толчком к разработке метода Морриса (Morris), который, в свою очередь, привел к разработке алгоритма D. См. САСМ 6 (1963), 101, где М. Д. Мак-Илрой (М. D. МсПгоу) приписывает эту идею В. А. Высоцки (V. А. Vyssotsky); та же технология была открыта в 1956 году А. В. Хольтом (Av W. Holt), который успешно применил ее в системе gpx для univac.

49. С;„ - 1 = Ek>bi-b)PNk ~ T,k>bif-f>)(4ab)/k] = аЫь{а). [Примечание. В общем случае имеем

Ь>0 к>Ь

ДЛЯ любой производящей функции вероятностей P{z) = Ро + Piz +

= J2(( -1) - -1)+-1))*

k>b

= le-" {ba)br {Ь + Ьа-2Ь + 2 + {ba - 2a{b -1)4-6- 1)Д(а, 6)).

[В 1957 году анализ успешного поиска с цепочками был впервые проведен В. П. Хайзин-гом (W. Р. Heising). Простые выражения в (57) и (58) были найдены Я. А. ван дер Пулом (J. А. van der Pool) в 1971 году; им также рассмотрен вопрос о минимизации функции, представляющей комбинированную стоимость используемого пространства и количества обращений. Можно определить дисперсию Cn и числа переполнений на блок, исходя из X]fc>b(fc-b)PiVfc = {2N/M){Cn - i) - {Cn - 1). Дисперсия общего количества переполнений может быть приближенно представлена увеличенной в М раз дисперсией в единичном блоке, хотя на самом деле это завышенное значение, потому что общее количество записей вынуждено быть равным N. Истинная дисперсия может быть найдена, как и в упр. 37. Обратитесь также к исследованию х-критерия в разделе 3.3.1С.]

50. А затем - что Qo(M,N-l) = {M/N){Qo{M, N) - l). В общем случае rQr{M,N) = MQr-2(M,N)-{M-N-r)Qr-iiM,N) = M{Qr-i(M,N+l)-Qr-iiM,N)y, Qr{M,N-l) = iM/N){QriM,N)~Qr-i{M,N)).

51. R{a,n) = a-nl eian)- - Qoian,n)).