равна нулю. Покажите, что получившееся семейство хеш-функций универсальным не будет.

12.4. Открытая адресация

В отличие от хеширования с цепочками, при открытой адресации (open addressing) никаких списков нет, а все записи хранятся в самой хеш-таблице: каждая ячейка таблицы содержит либо элемент динамического множества, либо nil. Поиск заключается в том, что мы определённым образом просматриваем элементы таблицы, пока не найдём то, что ищем, или не удостоверимся, что элемента с таким ключом в таблице нет. Тем самым число хранимых элементов не может быть больше размера таблицы: коэффициент заполнения не больше 1.

Конечно, и при хешировании с цепочками можно использовать свободные места в хеш-таблице для хранения списков (упражнение 12.2-5), но при открытой адресации указатели вообще не используются: последовательность просматриваемых ячеек вычисляется. За счет экономии памяти на указателях можно увеличить количество позиций в таблице, что уменьшает число коллизий и сокращает поиск.

Чтобы добавить новый элемент в таблицу с открытой адресацией, ячейки которой занумерованы целыми числами от 0 до га - 1, мы просматриваем её, пока не найдем свободное место. Если всякий раз просматривать ячейки подряд (0,1,..., га- 1), потребуется время О(га), но суть в том, что порядок просмотра таблицы зависит от ключа! Иными словами, мы добавляем к хеш-функции второй аргумент - номер попытки (нумерацию начинаем с нуля), так что хеш-функция имеет вид

h: U x {0,1,..., га - 1} -> {0,1,..., га - 1}

(U - множество ключей). Последовательность испробованных мест (probe sequence), или (короче) последовательность проб для

данного ключа к имеет вид

(h(k,0),h(k,l),...,h(k,m- 1));

функция h должна быть такой, чтобы каждое из чисел от 0 до га- 1 встретилось в этой последовательности ровно один раз (для каждого ключа все позиции таблицы должны быть доступны). Ниже приводится текст процедуры добавления в таблицу Г с открытой адресацией; в нем подразумевается, что записи не содержат дополнительной информации, кроме ключа. Если ячейка таблицы пуста, в ней записан nil (фиксированное значение, отличное от всех ключей).

Hash-Insert(T, к) 1 г <- О

2repeat j <- h(k,i)

3if T[j] = nil

4then T[j] <- A;

5return j

6else i <- г + 1

7until i = m

8error «переполнение хеш-таблицы»

При поиске элемента с ключом к в таблице с открытой адресацией ячейки таблицы просматриваются в том же порядке, что и при добавлении в нее элемента с ключом к. Если при этом мы натыкаемся на ячейку, в которой записан nil, то можно быть уверенным, что искомого элемента в таблице нет (иначе он был бы занесён в эту ячейку). (Внимание: мы предполагаем, что никакие элементы из таблицы не удаляются!)

Вот текст процедуры поиска Hash-Search (если элемент с ключом к содержится в таблице Г в позиции j, процедура возвращает j, в противном случае она возвращает nil).

Hash-Search(T, к)

1г <- О

2repeat j <- h(k,i)

6until T[j] = nil или i = m

7return nil

Удалить элемент из таблицы с открытой адресацией не так просто. Если просто записать на его место nil, то в дальнейшем мы не сможем найти те элементы, в момент добавления которых в таблицу это место было занято (и из-за этого был выбран более далёкий элемент в последовательности испробованных мест). Возможное решение - записывать на место удалённого элемента не nil, а специальное значение deleted («удалён»), и при добавлении рассматривать ячейку с записью deleted как свободную, а при поиске - как занятую (и продолжать поиск). Недостаток этого подхода в том, что время поиска может оказаться большим даже при низком коэффициенте заполнения. Поэтому, если требуется удалять записи из хеш-таблицы, предпочтение обычно отдают хешированию с цепочками.

В нашем анализе открытой адресации мы будем исходить из предположения, что хеширование равномерно (uniform) в том смысле, что все то! перестановок множества {0,1,..., то - 1} равнове-

3

4 5

роятны. На практике это вряд ли так, хотя бы по той причине, что для этого необходимо, чтобы число возможных ключей было как минимум то!, где то - число хеш-значений. Поэтому обычно пользуются более или менее удачными суррогатами, вроде описываемого ниже двойного хеширования.

Обычно применяют такие три способа вычисления последовательности испробованных мест: линейный, квадратичный и двойное хеширование. В каждом из этих способов последовательность (h(k, 0), h(k, 1),..., h(k, то - 1)) будет перестановкой множества {0,1,..., то - 1} при любом значении ключа к, но ни один из этих способов не является равномерным по той причине, что они дают не более то2 перестановок из то! возможных. Больше всего разных перестановок получается при двойном хешировании; не удивительно, что и на практике этот способ дает лучшие результаты.

Линейная последовательность проб

Пусть Ы: U -т- {0,1,..., то - 1} - «обычная» хеш-функция. Функция, определяющая линейную последовательность проб (linear probing), задаётся формулой

h(k, г) = (h(k) + г) mod то.

Иными словами, при работе с ключом к начинают с ячейки T[h(k)], а затем перебирают ячейки таблицы подряд: T[h(k) + 1], T[h(k) + 2],... (после Т[т - 1] переходят к Г[0]). Поскольку последовательность проб полностью определяется первой ячейкой, реально используется всего лишь то различных последовательностей.

Открытую адресацию с линейной последовательностью проб легко реализовать, но у этого метода есть один недостаток: он может привести к образованию кластеров, то есть длинных последовательностей занятых ячеек, идущих подряд (по-английски это явление называется primary clustering). Это удлиняет поиск; в самом деле, если в таблице из то ячеек все ячейки с чётными номерами заняты, а ячейки с нечётными номерами свободны, то среднее число проб при поиске элемента, отсутствующего в таблице, есть 1,5; Если, однако, те же то/2 занятых ячеек идут подряд, то среднее число проб примерно равно то/8 = га/4 (га - число занятых мест в таблице). Тенденция к образованию кластеров объясняется просто: если г заполненных ячеек идут подряд, вероятность того, что при очередной вставке в таблицу будет использована ячейка, следующая непосредственно за ними, есть (г + 1)/то, в то время как для свободной ячейки, предшественница которой также свободна, вероятность быть использованной равна всего лишь 1/то. Всё вышеизложенное показывает, что линейная последовательность проб довольно далека от равномерного хеширования.