Лемма 16.4 Расширяемая хеш-таблица, построенная из набора ключей, зависит только от значений этих ключей и не зависит от порядка их вставки.

Давайте рассмотрим trie-дерево, соответствующее ключам (см. лемму 15.2), в котором каждый внутренний узел помечен количеством элементов в его поддереве. Внутренний узел соответствует странице в расширяемой хеш-таблице тогда и только тогда, когда его метка меньше Л/, а метка его родительского узла не меньше чем М. Все элементы, расположенные ниже этого узла, попадают на данную страницу. Если узел находится на уровне к, он соответствует -разрядной последовательности, полученной из пути trie-дерева обычным способом, а все записи в каталоге расширяемой хеш-таблицы, индексы которых начинаются с этой /:-разрядной последовательности, содержат указатели на соответствующую страницу. Размер каталога определяется наибольшим уровнем всех внутренних узлов в trie-дереве, соответствующих страницам. Таким образом, trie-дерево можно преобразовать в расширяемую хеш-таблицу независимо от порядка вставки элементов, и это свойство сохраняется в качестве следствия леммы 15.2.

гг77

153!

51-5.27

70f> i

737 .f

742 i.

756 I

77? I

РИСУНОК 16.12 ПОСТРОЕНИЕ РАСШИРЯЕМОЙ ХЕШ-ТАБЛИЦЫ, ЧАСТЬ 2

Мы вставляем ключи 766 и 275 в крайнее справа В-дерево, показанное на рис. 16.11, без выполнения какого-либо разделения узлов (рисунок слева). Затем, при вставке ключа 737, нижняя страница разделяется и это, поскольку существует только одна связь с нижней страницей, приводит к разделению каталога (рисунок в центре). Затем мы вставляем ключи 574, 434, 641 и 207, что приводит к разделению верхней страницы (рисунок справа)

001< 17b;.

207 275

ill

РИСУНОК 16.13 ПОСТРОЕНИЕ РАСШИРЯЕМОЙ ХЕШ-ТАБЛИЦЫ, ЧАСТЬ 3

Продолжая пример, приведенный на рис. 16.11 и 16.12, мы вставляем 5 ключей 526, 562, 017, 107 и 147 в крайнее справа В-дерево, отображенное на рис. 16.6. Разделение узлов происходит при вставке ключей 526 (рисунок слева) и 107 (рисунок справа).

Программа 16.7 - реализация операции insert для расширяемой хеш-таблицы. Прежде всего, мы обращаемся к странице, которая могла бы содержать искомый ключ, посредством единственной ссылки к каталогу, как это делалось при поиске. Затем мы вставляем в нее новый элемент, как это делалось для внешних узлов в В-деревьях (см. программу 16.2). Если в результате этой вставки в узле оказывается М элементов, мы вызываем функцию разделения, как это делалось для В-деревьев, правда, на этот раз она сложнее. Каждая страница содержит к ведущих разрядов, которые заведомо совпадают в ключах всех элементов на данной странице, и, поскольку разряды нумеруются слева направо, начиная с О, /: определяет также индекс разряда, который необходимо проверять для определения способа разделения элементов.

Программа 16.7 Вставка в расширяемую хеш-таблицу

Чтобы вставить элемент в расширяемую хеш-таблицу, мы выполняем поиск; затем мы вставляем элемент в указанную страницу; далее, разделяем страницу, если вставка вызывает переполнение. Общая схема не отличается от используемой для В-деревьев, но алгоритмы поиска и разделения иные. Функция разделения создает новый узел, затем проверяет /с-тый разряд (считая слева) ключа каждого элемента: если разряд равен О, элемент остается в старом узле; если он равен 1, элемент перемещается в новый узел. Значение к + 1 присваивается полю заведомо идентичных ведущих разрядов обоих узлов после разделения. Если этот процесс не приводит к помещению по меньшей мере одного ключа в каждом узле, разделение выполняется снова, пока подобным образом не будут разделены все элементы. В конце процесса мы вставляем указатель нового узла в каталог.

private: void split(link h)

{ link t = new node;

while (h->m ==0 h->m == M) {

h->ni = t->ni = 0 ;

for (int j = 0; j < M; j++)

if (bits (h->b[j] .key 0 , h->k, 1) == 0) h->b[h->m++] = h->b[j];

else t->b[t->m++] = h->b[j]; t->k = ++ (h->k) ;

insertDIR(t, t->k);

void insert (link h, Item x) { int j; Key v = x.keyO; for (j = 0; j < h->m; j++)

if (V < h->btj] .key О) break; for (int i = (h->m)++; i > j; i-)

h->b[i] = h->b[i-l] ; h->b[j] = x;

if (h->m == M) split (h);

public: void insert (Item x)

{ insert(dir[bits(X.key 0, 0, d) ] , x) ; }