То есть, может существовать несколько записей каталога, ссылающихся на одну и ту же страницу, что не повлияет на возможность быстро выполнять поиск в структуре путем объединения на одной странице ключей с различными значениями, первые d разрядов которых совпадают, в то же время позволяя находить страницу, содержащую заданный ключ, за счет использования ведущих разрядов ключа для индексации внутри каталога. Во-вторых, для увеличения емкости таблицы можно удвоить размер каталога.

В частности, структура данных, используемая для расширяемого хеширования, значительно проще использованной для В-деревьев. Она состоит из страниц, которые содержат до М элементов, и каталога, содержащего 2 указателей на страницы (профамма 16.5). Указатель в ячейке каталога х ссылается на страницу, которая содержит все элементы, ведущие d разрядов которых равны х. Значение d выбирается достаточно большим, чтобы на каждой странице гарантированно хранилось менее М элементов. Реализация операции search проста: мы используем ведущие d разрядов ключа для индексации внутри каталога, что обеспечивает доступ к странице, которая содержит любые элементы с соответствующими ключами, а затем выполняем последовательный поиск такого элемента на данной странице (см. программу 16.6).

Программа 16.5 Структуры данных расширяемого хеширования

Расширяемая хеш-таблица - это каталог ссылок на страницы (подобно внешним узлам в В-деревьях), который содержит до 2М элементов. Каждая страница содержит также счетчик (т) количества элементов на странице и целочисленное значение (к), указывающее количество ведущих разрядов, которые должны совпадать в ключах элементов. Как обычно, N - количество элементов в таблице. Переменная d определяет количество разрядов, которые используются для индексации в каталоге, а D - количество записей в каталоге; таким образом, 0=2 . Вначале таблица устанавливается соответствующей каталогу размера 1, который указывает на пустую страницу.

template <class Item, class Кеу> class ST {

private: struct node

{ int m; Item b[M]; int k; nodeO { m = 0; к = 0; }

typedef node *link; link* dir; Item nullItern; int N, d, D; public:

ST(int maxN)

{ N = 0; d = 0; D = 1; dir = new link[D] ; dir[0] = new node;

Программа 16.6 Поиск в таблице расширяемого хеширования

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

private: Item search (link h, Key v) {

for (int j = 0; j < h->m; j++)

if (v == h->b[ j] .key 0 ) return h->b[j]; return nullltem;

public: Item search (Key v)

{ return search(dir[bits(v, 0, d) ], v) ; }

Для поддержки операции insert структура данных должна б1ять несколько более сложной, но одно из ее свойств заключается в том, что этот ал1оритм поиска успешно работает без каких-либо модификаций. Чтобы обеспечить поддержку операции insert, необходимо ответить н а следующие вопросы:

Что делать, когда количество элементов на странице превышает ее емкость?

Какой размер каталога следует использовать?

Например, в примере, приведенном на рис. 16.10, нельзя было бы использовать значение d = 2, поскольку некоторые страницы оказались бы переполненными, и нельзя было бы использовать значение d = 5, поскольку слишком много страниц оказались бы пустыми. Как обычно, наибольший интерес вызывает поддержка операции insert для АТД таблицы символов, чтобы, например, структура могла постепенно разрастаться по мере выполнения ряда чередующихся операций searcli и insert. Принятие такой точки зрения соответствует уточнению первого вопроса:

Что делать, когда необходимо вставить элемент в заполненную страницу?

Например, в примере, представленном на рис. 16.10, нельзя было бы вставить элемент, ключ которого начинается с 5 или 7, поскольку соответствующие страницы заполнены.

Определение 16.3 Расширяемая хеш-таблица порядка d представляет собой каталог из 2 ссылок на страницы, которые содержат до М элел1ентов с ключами. Первые к разрядов элементов на каждой странице совпадают, а като/юг содержит 2 указателей на страницу, начинающихся с ячейки, указанной ведущими к разрядами в ключах на страницах.

Некоторые -разрядные последовательности могут не появляться ни в одном из ключей. Соответствующие записи каталога оставлены в определении 16.3 не определенными, хотя существует естественный способ организации указателей на пустые страницы, который вскоре будет рассмотрен.

Глава 16, Внешний поиск

Для поддержания этих характеристик в процессе разрастания таблицы мы используем две базовые операции: разделение страницы, при котором некоторые ключи с полной страницы переносятся на другую страницу, и разделение каталога, при котором размер каталога удваивается, а значение d увеличивается на 1. В частности, при заполнении страницы мы разделяем ее на две, используя самую левую разрядную позицию, где различаются ключи, для определения элементов, которые должны быть перемещены на новую страницу. При разделении страницы мы соответствующим образом изменяем указатели каталога, при необходимости удваивая размер каталога.

Как обычно, лучщий способ понять алгоритм заключается в отслеживании его работы при вставке набора ключей в первоначально пустую таблицу. Вскоре каждая из ситуаций, которые должен обрабатывать алгоритм, проявляется в простейщей форме, и принципы, лежащие в основе алгоритма, становятся понятными. Построение расширяемой хещ-таблицы для набора из 25 восьмеричных ключей, рассматриваемого в этой главе, показано на рис. 16.11 - 16.13. Подобно тому, как это имело место в В-деревьях, большинство вставок не приводит к переполнению: они просто добавляют ключ к странице. Поскольку процесс начинается с одной страницы, а завершается восемью, можно предположить, что семь вставок вызвали разделение страниц. Поскольку в начале размер каталога равен 1, а в конце - 16, можно предположить, что четыре вставки привели к разделению каталога.

ife

176!

153 I 17 б *

373i

601:

706 773

513

52 4Г

601:

7 06 ; 742;. 773 .

РИСУНОК 16.11 ПОСТРОЕНИЕ РАСШИРЯЕМОЙ ХЕШ-ТАБЛИЦЫ. ЧАСТЬ 1

Как и в В-деревьях, первые пять вставок в расширяемую хеш-таблицу приходятся на одну страницу (рисунок слева). Затем, при вставке ключа 773, мы выполняем разделение на две страницы (одна содержит все ключи, начинающиеся с О разряда, другая - все ключи, начинающиеся с 1 разряда) и удваиваем размер каталога, чтобы он содержал по одному указателю на каждую из страниц (рисунок в центре). Ключ 742 вставляется в нижнюю страницу (поскольку он начинается с 1 разряда), а ключ 373 - в верхнюю страницу (поскольку он начинается с О разряда), но затем нижнюю страницу приходится разделить, чтобы можно было поместить ключ 524. Для выполнения этого разделения все элементы, ключи которых начинаются с разрядов 10, помещаются на одну страницу, а все элементы, ключи которых начинаются с разрядов 11 - на другую, после чего размер каталога снова удваивается, чтобы в нем могли поместиться указатели на обе эти страницы (рисунок справа). Каталог содержит два указателя на страницу, содержащую элементы с ключами, которые начинаются с О разряда: один для ключей, которые начинаются с разрядов 00, и другой для ключей, которые начинаются с разрядов 01.