Внешний поиск a

Рис. 16.13. Построение расширяемой хеш-таблицы, часть 3
Продолжая пример, приведенный на рис. 16.11 и 16.12, мы вставляем 5 ключей 526, 562, 017, 107 и 147 в крайнее правое B-дерево, показанное на рис. 16.6. Разбиение узлов происходит при вставке ключей 526 (слева) и 107 (справа).
Программа 16.7. Вставка в расширяемую хеш-таблицу
Чтобы вставить элемент в расширяемую хеш-таблицу, мы выполняем его поиск, а затем вставляем элемент в найденную страницу (и разбиваем ее, если вставка вызывает переполнение). Общая схема не отличается от используемой для B-деревьев, но алгоритмы поиска и разбиения иные. Функция разбиения создает новый узел, затем проверяет к-й бит (считая слева) ключа каждого элемента: если этот бит равен 0, элемент остается в старом узле; если 1 — перемещается в новый. В поле " количество одинаковых ведущих разрядов " обоих узлов после разбиения заносится значение к + 1. Если этот процесс не приводит к наличию по меньшей мере одного ключа в каждом узле, разбиение выполняется снова, пока элементы не станут разделены. И, наконец, мы вставляем ссылку на новый узел в каталог.
private:
void split(link h)
{ link t = new node;
while (h->m == 0 || h->m == M)
{ h->m = t->m = 0;
for (int j = 0; j < M; j++)
if (bits(h->b[j].key(), 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.key();
for (j = 0; j < h->m; j++)
if (v < h->b[j].key()) break;
for (int i = (h->m)++; i > j; i—-)
h->b[i] = h->b[i-1];
h->b[j] = x;
if (h->m == M) split(h);
}
public:
void insert(Item x)
{ insert(dir[bits(x.key(), 0, d)], x); }
Следовательно, для разбиения страницы мы создаем новую страницу, затем помещаем все элементы, для которых данный разряд равен 0, в старую страницу, а все элементы, для которых он равен 1 — в новую страницу, а затем для обеих страниц устанавливаем значение счетчика разрядов равным к + 1. Вообще-то возможен случай, когда в полном узле все ключи имеют одинаковое значение разряда к. В этом случае нужно просто перейти к следующему разряду и продолжать этот процесс до тех пор, пока каждая страница не будет содержать по меньшей мере один элемент. Однажды этот процесс должен завершиться, если только не имеется M значений одного и того же ключа. Вскоре мы рассмотрим и этот случай.
Как и в случае B-деревьев, на каждой странице резервируется свободное место для одной лишней записи, которая позволяет выполнять разбиение после вставки — это упрощает код. Данный прием почти не влияет на производительность, так что при анализе им можно пренебречь.
При создании новой страницы необходимо вставить в каталог ссылку на нее. Код, выполняющий эту вставку, приведен в программе 16.8. Простейшим является случай, когда перед вставкой каталог содержит ровно две ссылки на страницу, которая будет разбита. В этом случае нужно лишь записать вторую ссылку, указывающую на новую страницу. Если количество разрядов к, которое нужно для различения ключей на новой странице, превышает количество разрядов d для доступа к каталогу, то размер каталога нужно увеличить, чтобы в нем могла поместиться новая запись. И, наконец, выполняется соответствующее изменение ссылок в каталоге.
Если более M элементов имеют одинаковые ключи, таблица переполняется, и программа 16.7 зацикливается, пытаясь различить эти ключи. Есть еще одна похожая проблема: каталог может оказаться неоправданно большим, если ключи имеют очень много совпадающих ведущих разрядов. Эта ситуация похожа на излишнее время, требуемое для выполнения MSD-сортировки файлов с большим количеством одинаковых ключей или длинными последовательностями разрядов, в которых они совпадают. Решение этих проблем зависит от рандомизации, обеспечиваемой хеш-функцией (см. упражнение 16.43). Но даже при использовании хеширования в случае большого количества одинаковых ключей приходится предпринимать специальные действия, поскольку хеш-функции отображают равные ключи в равные хеш-значения. Повторяющиеся ключи могут сделать каталог неестественно большим, а при наличии большего количества равных ключей, чем помещается на одной странице, алгоритм просто перестает работать. Следовательно, при использовании этого кода необходимо добавить проверки, предотвращающие возникновение таких условий (см. упражнение 16.35).
С точки зрения производительности наибольший интерес представляют количество используемых страниц (как и в случае B-деревьев) и размер каталога. Для этого алгоритма рандомизация обеспечивается хеш-функциями, поэтому характеристики производительности для среднего случая верны и для любой последовательности N вставок различных ключей.