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

Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, как это было сделано ранее. Выполняемые при этом действия показаны на рис. 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).

Теперь, когда мы рассмотрели основной алгоритм, пора применить его на практике. Прежде всего, отметим следующее: все фрагменты расширяемой хеш-таблицы хранятся в отдельных файлах: каталога, группы и записей. Для хранения групп и записей мы используем класс TtdRecordStream (в действительности мы будем использовать производный от него класс TtdRecordFile, ориентированный на использование файлов, но внутри программы мы будем считать, что применительно к расширяемой хеш-таблице этот класс является простым потоком). Каталог может храниться и извлекаться из любого класса, производного от TStream, но понятно, что длительного хранения целесообразно использовать класс TFileStream.

Извлечение и реализация каталога - следующая по сложности задача. Код интерфейса для ее выполнения приведен в листинге 7.20.

Листинг 7.20. Интерфейс класса TtdHashDirectory

type

TtdHashDirectory = class private

FCount : integer;

FDepth : integer;

FList : TList;

FName : TtdNameString;

FStream : TStream;

protected

function hdGetItem(aInx : integer): longint;

procedure hdSetItem(aInx : integer; aValue : longint);

function hdErrorMsg(aErrorCode : integer;

const aMethodName : TtdNameString; aIndex : integer): string;

procedure hdLoadFromStream;

procedure hdStoreToStream;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

procedure DoubleCount;

property Count : integer read FCount;

property Depth : integer read FDepth;

property Items [aInx : integer] : longint read hdGetItem write hdSetItem; default;

property Name : TtdNameString read FName write FName;

end;

Для выполнения поставленной задачи этого общедоступного интерфейса вполне достаточно. Мы можем удвоить количество элементов в каталоге, используя метод DoubleCount, и можем получать текущие номера элементов (свойство Count) и разрядную глубину каталога (свойство Depth). Теоретически, мы могли бы обойтись только одним свойством, поскольку Count = 2Depth. Но поддержание обоих свойств - менее трудоемкая задача по сравнению с вычислением степени двух, когда это потребуется. И, наконец, мы может обратиться к отдельным элементам, хранящимся в каталоге в виде значений типа длинных целых. Естественно, эти значения будут номерами групп.

Разделы private и protected содержат еще несколько методов и полей. Во-первых, это методы set и get свойства Items, а, во-вторых, - два метода, предназначенные для выполнения считывания и записи каталога в и из потока. Кроме того, как мы видим, реальным контейнером записей каталога является экземпляр TList.

В листинге 7.21 конструктор создает экземпляр каталога хеш-таблицы, внутренний объект TList и при необходимости выполняет автоматическое считывание из потока.

Листинг 7.21. Создание экземпляра класса TtdHashDirectory

constructor TtdHashDi rector Y.Create(aStrearn : TStream);

begin

Assert(sizeof(pointer) = sizeof(longint), hdErrorMsg(tdePointerLongSize, 1 Create1, 0));