Фундаментальные алгоритмы и структуры данных в Delphi

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

В рассмотренном нами примере максимальная разрядная глубина группы была равна 3, поэтому разрядная глубина каталога также равна этому значению. Три разряда позволяют образовать восемь комбинаций разрядов: 000, 001, 010, 011, 100, 101, 110 и 111. Все комбинации, которые завершаются 1 (т.е. вторая, четвертая, шестая и восьмая), указывают на одну и ту же группу, принимающую элементы, хеш-значения которых завершаются 1. Аналогично, записи каталога для значений 000 и 100 указывают на одну и ту же группу, в которую помещаются элементы с хеш-значениями, завершающимися разрядами 00.

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

Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами 001, при поиске мы обратимся не к записи 001 каталога, а к записи 100 (4, которая соответствует инвертированному значению 001). В результате использование каталога значительно упрощается. В нашем примере хеш-значения, которые завершаются разрядами 00, помещаются в запись каталога 000 (0) или 001 (1). Хеш-значения, которые завершаются разрядами 010, помещаются в запись каталога 010 (2). Хеш-значения, которые завершаются разрядами 011, помещаются в запись каталога 011 (3). И, наконец, хеш-значения, которые завершаются разрядом 1, помещаются в записи 100, 101, 110 или 111 (4, 5, 6, 7).

Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, как это было сделано ранее. Выполняемые при этом действия показаны на рис. 7.1. Мы начинаем с каталога только с одной записью с индексом 0 (а). Принято считать, что в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее А) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись 0 (исходная запись А), а на вторую - запись 1, В (с). Все элементы, хеш-значения которых завершаются разрядом 0, помещаются в группу А, а остальные - в группу В. Снова заполним группу A. Теперь разрядную глубину каталога необходимо увеличить с 1 до 2, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога 00 и 01 будут указывать на исходную группу А, а записи 10 и 11 - на группу В (d). Группа А разбивается на группу, которая принимает хеш-значения с окончанием 00 (снова А), и группу, которая принимает хеш-значения с окончанием 10, С. На группу А будет указывать запись 00 каталога, а на группу С - запись 01 (e). И, наконец, группа С (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.

Рисунок 7.1.Вставка в расширяемую хеш-таблицу

Теперь записи 000 и 001 указывают на запись А, записи 010 и 011- на группу С, а 100, 101, 110 и 111 - на группу В (f). Мы создаем новую группу D и повторяем вставку всех элементов группы С в группы С и D, причем первая группа, которой соответствует запись каталога 010 (2), принимает хеш-значения с окончанием 010, а вторая, которой соответствует запись каталога 011 (3), - хеш-значения с окончанием 110 (g).