63. [М25] Если в хеш-таблице выполняются случайные вставки и удаления, то сколько независимых вставок в среднем следует сделать, чтобы все М позиций были занятыми в то или иное время? (Это значение представляет собой среднее время работы на отказ метода удаления, просто помечающего ячейки как "удаленные")

64. [M4i] Проанализируйте ожидаемое поведение алгоритма R (удаление с линейным исследованием). Сколько раз в среднем выполняется шаг R4?

► 65. [20] (Ключи переменной длины.) Во многих приложениях с хеш-таблицами используются ключи, представляющие набор символов произвольной длины. В таких приложениях нельзя просто хранить ключ в таблице, как в программах из этого раздела. Каким образом можно организовать работу хеш-таблиц с ключами переменной длины на MIX-компьютере?

► 66. [25] (Оле Амбль (01е Amble), 1973.) Можно ли так вставить ключи в открытую хеш-таблицу с использованием их числового или алфавитного порядка, чтобы в случае поиска по алгоритму L или D можно было сделать вывод о его неудачном завершении, встретив ключ, меньший, чем аргумент поиска?

67. [M4I] Пусть N ключей с хеш-адресами 0102 . ам вставляются в хеш-таблицу согласно алгоритму L и пусть dj - смещение j-ro ключа из его начального положения aj\

тогда Cn = 1 + (di +d2-\-----1- djv)/iV. Теорема P гласит, что перестановка а не влияет

на сумму dl + d2 + + dN] однако такая перестановка может значительно изменить сумму dj + d2 + + d. Например, хеш-последовательность 12... N-1 N-1 делает dl d2 ... djv-i djv равным 00 ... 0 N-1 и = (iV - 1), в то время как ее зеркальное отражение Л-1 N-1 ... 2 1 приводит к более "цивилизованному" перемещению 01 ... 11, для которого Y.dj = N - 1.

a) Какое размещение oi ог ... ajv минимизирует dj?

b) Поясните, каким образом следует модифицировать алгоритм L, чтобы после каждой вставки сохранялся набор перемещений с наименьшей дисперсией.

c) Определите среднее значение dj с указанной модификацией и без нее.

68. [M41] Чему равна дисперсия среднего числа проб в случае успешного поиска по алгоритму L? В частности, чему равно среднее (di -Ь Н-----h djv) в обозначениях упр. 67?

69. [М25] (Эндрю Яо (Andrew Yao).) Докажите, что схемы циклического единственного хеширования удовлетворяют неравенству Сам 2(-""V(l~)) в смысле упр. 62. [Указание. Покажите, что для неудачного поиска требуется ровно к проб с вероятностью Рк<(М- N)/M.]

70. [НМ4З] Докажите, что ожидаемое количество проб, необходимых для вставки (аМ + 1)-го элемента при помощи двойного хеширования, не превышает ожидаемого количества проб, необходимых для вставки (аМ + у/О (log М) /М) -го элемента при равномерном исследовании.

71. [40] Поэкспериментируйте с поведением алгоритма С при его адаптации к внешнему поиску так, как описано в тексте.

► 72. [М28] (Универсальное хеширование.) Представьте гигантскую матрицу Я, имеющую по Одному столбцу для каждого возможного ключа К. Элементы Я представляют собой числа от О до М - 1; строки Я представляют хеш-функции. Мы говорим, что Я определяет универсальное семейство хеш-функций, если любые два столбца совпадают не более чем в R/M строках, где R - общее количество строк.

а) Докажите, что если Я универсальна в этом смысле и хеш-функция h выбирается случайным образом из строки Я, то ожидаемый размер списка, содержащего все данные ключи К в методе раздельных цепочек (см. рис. 38) после вставки любого множества различных ключей Ki, К2, ..., Kn будет равен < 1 -l-iV/M.

b) Предположим, что каждый hj в (9) представляет собой случайно выбранное отображение множества всех символов на множество {0,1,..., М - 1}. Покажите, что это соответствует универсальному семейству хеш-функций.

c) Останется ли результат (Ь) справедливым, если hj{0) = О для всех j, но hj{x) - случайно при X фО?

73. [М26] (Картер (Carter) и Вегман (Wegman).) Покажите, что п. (Ь) предыдуш;его упражнения выполняется, даже когда hj не являются полностью случайными функциями, но имеют один из следуюш;их видов, (i) Пусть Xj - двоичное число (6j(„ i) .. .bjibjo)2-Тогда

hj(xj) = (aj(„ i)6j(n i) +----h ajibji + ajobjo) mod M,

где каждое Ujk выбирается случайно по модулю М. (ii) Пусть М - простое число; положим О < Xj < М. Тогда

hj (xj) = (ujXj + bj) mod M, где Uj и bj выбираются случайным образом по модулю М.

74. [М29] Пусть Я определяет универсальное семейство хеш-функций. Докажите или опровергните следуюш;ее. Даны N различных столбцов и некоторая случайным образом выбранная строка. При этом ожидаемое число нулей в этой строке, принадлежащих выбранным столбцам, равно 0(1) + 0{NjM). [Таким образом, каждый список в методе раздельных цепочек будет иметь ожидаемый размер.]

75. [М26] Докажите или опровергните следующие утверждения о хеш-функции h из (9), если hj представляют собой независимые случайные функции.

a) Вероятность того, что h{K) = тп, равна 1/М для всех О < m < М.

b) Если К ф К, вероятность того, что h{K) = m и h{K) = тп, равна 1/М для всех О < тп,т < М.

c) Если К, К и К" различны, вероятность того, что h{K) = тп, h{K) = тп и h{K") = тп", равна 1/М для всех О < т, пг, тп" < М.

d) Если К, К, К" и К" различны, вероятность того, что h{K) - тп, h{K) = тп , h{K") = m" и h(K") = т", равна l/M" для всех О < т, т, тп", т" < М.

► 76. [М21] Предложите путь изменения (9) для ключей с переменной длиной, сохраняющего свойства универсального хеширования.

77. [М22] Пусть Н определяет универсальное семейство хеш-функций из 32-битовых ключей в 1б-битовые (так что Н имеет 2 столбца, а в обозначениях упр. 72 М = 2). 256-битовый ключ можно рассматривать как конкатенацию восьми 32-битовых частей

а;1а:2а;за;4а;5а;ба;7Ж8;

его можно отобразить в 16-битовый адрес при помощи хеш-функции

h,ih3ih2ihl{Xl)hl(X2))h2{hl(X3)hlix,)))h3{h2{hl(x5)hl{xe))h2ihlixr)hlixs)))),

где hi, /i2, hs я hi - случайно и независимо выбранные строки Н (здесь, например, hi{xi)hi{x2) означает 32-битовое число, полученное конкатенацией hi(xi) и /11(2:2)). Докажите, что вероятность того, что два различных ключа хешируются в один и тот же адрес, меньше 2". [Для этой схемы требуется гораздо меньше случайных выборов, чем для (9).]

Она сделала из названий настоящий хаш, это уж точно*.

- ГРАНТ АЛЛЕН (GRANT ALLEN) (шатры Сима (The Tents of Stiem), 1889)

"HASH, x". Для этого слова нет определения - никто не знает, что такое "tiash".

- АМБРУАЗ БИРС (AMBROSE BIERCE) (Дьявольский словарь (The Devils Dictionary), 1906)

* В переводе пришлось использовать очень схожее по звучанию Ы даже по смыслу) слово хаш, означающее армянское горячее блюдо из рубленого мяса. - Прим. переь.