Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в 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).
Теперь, когда мы рассмотрели основной алгоритм, пора применить его на практике. Прежде всего, отметим следующее: все фрагменты расширяемой хеш-таблицы хранятся в отдельных файлах: каталога, группы и записей. Для хранения групп и записей мы используем класс 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));
{создать предка}
inherited Create;
{создать каталог как TList}
FList := TList.Create;
FStream := aStream;
{если поток не содержит никаких данных, то инициализировать каталог с одной записью и глубиной равной 0}
if (FStream.Size = 0) then begin
FList.Count := 1;
FCount := 1;
FDepth := 0;
end
{в противном случае выполнить загрузку из потока}
else
hdLoadFromS trearn;
end;
procedure TtdHashDirectory.hdLoadFromStream;
begin
FStream.Seek(0, soFromBeginning);
FStream.ReadBuffer(FDepth, sizeof(FDepth));
FStream.ReadBuffer(FCount, sizeof(FCount));
FList.Count := FCount;
FStream.ReadBuffer(FList.List^, FCount * sizeof(longint));
end;
Я оставил оператор Assert в конструкторе Create. Он проверяет равенство размера указателя размеру значения longint. Это связано с тем, что я немного "схитрил", сохраняя значения каталога непосредственно в TList в виде однотипных указателей. При изменении размера указателя или longint, используемый метод работать не будет. Поэтому, просто на всякий случай, я поместил здесь это утверждение. Если впоследствии компилятор будет генерировать сообщение об ошибке, это можно будет исправить. Если же нет, то во время выполнения будет выводиться сообщение о нарушении утверждения.
А пока что LoadFromStream выполняет минимальную проверку для проверки наличия допустимого каталога в потоке. Поскольку считывание выполняется непосредственно из потока в буфер фиксированного размера, в будущем, возможно, имеет смысл несколько усовершенствовать процесс, включив сигнатуру в поток или добавив проверку с применением циклического избыточного кода и т.п.
Уничтожение экземпляра каталога хеш-таблицы (листинг 7.22) требует считывания его текущего содержимого обратно в поток и освобождения внутреннего объекта TList.
Листинг 7.22. Уничтожение экземпляра класса TtdHashDirectory
