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

Расширяемое хеширование

Расширяемое хеширование

Алгоритм, который нам нужно использовать, называется расширяемым хешированием (extendible hashing), и чтобы им можно было воспользоваться, необходимо вернуться к функции хеширования.

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

Теперь функция хеширования будет возвращать значение типа longint. Если вернуться к первоначальной хеш-функции PJW, можно убедиться, что она вычисляла 32-разрядное хеш-значение (фактически, 28-разрядное значение, поскольку значения четырех старших разрядов всегда устанавливались равными 0), а затем выполнялось деление по модулю этого значения на размер таблицы. При использовании расширяемого хеширования заключительное деление по модулю не выполняется. Вместо этого мы используем все хеш-значение полностью.

Означает ли это, что мы получаем хеш-таблицу с 268 миллионами ячеек? Нет, и это вполне согласуется со здравым смыслом. Мы используем только несколько разрядов хеш-значения, и по мере того, как таблица заполняется, мы начинаем использовать все больше разрядов хеш-значения.

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

Начнем вставлять в таблицу хеш-значения вместе с номерами их записей. При наличии только одной группы их можно вставить только в одно место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом - в другую. Эти две группы имеют так называемую разрядную глубину (bit-depth), равную одному разряду. Теперь при каждой вставке пары хеш-значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда хеш-значения.

Со временем мы заполним еще одну группу. Предположим, что это группа, в которую мы вставляли все хеш-значения, завершающиеся 0. Снова разобьем группу на две отдельные группы. На этот раз все элементы, хеш-значения которых заканчиваются двумя нулевыми разрядами, т.е. 00, будут помещаться в первую группу, а завершающиеся разрядами 10 - во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда хеш-значения. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами 00, во вторую -разрядами 10, а в третью - просто 1.

Предположим, что мы продолжаем вставку и заполняем группу 10. Мы снова разбиваем заполненную группу на две и повторяем вставку ее элементов в две новые группы. На этот раз две новые группы будут принимать элементы, завершающиеся разрядами 010 и 110. Таким образом, теперь у нас имеются четыре группы: одна с разрядной глубиной, равной 1, в которую выполняется вставка хеш-значений, завершающихся 1, одна с разрядной глубиной равной 2, содержащая хеш-значения, которые завершаются разрядами 00, и две группы с разрядной глубиной, равной 3, которые предназначены для хеш-значений, завершающихся разрядами 010 и 110.

Почему-то есть уверенность, что читатели уже получили представление о работе расширяемого хеширования, - все остальное не представляет сложности.

Для поддержания отображения того, какие хеш-значения помещаются в те или иные группы, используется структура, называемая каталогом (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

destructor TtdHashDirectory.Destroy;

begin

hdStoreToStream;

FList.Free;

inherited Destroy;

end;

procedure TtdHashDirectory.hdStoreToStream;

begin

FStream.Seek(0, soFromBeginning);

FStream.WriteBuffer(FDepth, sizeof(FDepth));

FStream.WriteBuffer(FCount, sizeof(FCount));

FStream.WriteBuffer(FList.List'4, FCount * sizeof(longint));

end;

Методы предка (листинг 723) свойства Items просто извлекают данные, однотипные longint, из внутреннего объекта TList.

Листинг 7.23. Установка и извлечение значений каталога

function TtdHashDirectory.hdGetItem(aInx : integer): longint;

begin

Assert( (0 <= aInx) and (aInx < FList.Count),

hdErrorMsg(tdeIndexOutOfBounds, 'hdGetItem', aInx));

Result := longint(FList.List^[aInx]);

end;

procedure TtdHashDirectory.hdSetItem(aInx : integer;

aValue : longint );

begin

Assert ((0 <= aInx) and (aInx < FList.Count), hdErrorMsg(tdeIndexOutOfBounds, 'hdGetItem', aInx));

FList.List^[aInx] := pointer(aValue);

end;

И, наконец, в листинге 7.24 приведен код интересного метода класса, который вдвое увеличивает размер каталога.

Листинг 7.24. Увеличение вдвое количества записей в каталоге

procedure TtdHashDirectory.DoubleCount;

var

Inx : integer;

begin

{удвоить значение счетчика, увеличить глубину}

FList.Count := FList.Count * 2;

FCount := FCount * 2;

inc(FDepth);

{теперь каждая запись в исходном каталоге удваивается; например, значению в записи 0 старого каталога теперь соответствует значение для записей 0 и 1 нового каталога}

for Inx := pred(FList.Count) downto 1 do

FList.List^[Inx] := FList.List^[Inx div 2];

end;

Во-первых, этот метод удваивает значение счетчика элементов во внутреннем объекте TList. Реализация TList гарантирует установку новых элементов в нулевые значения, хотя, как вскоре будет показано, это не имеет никакого значения. Метод удваивает значение внутреннего счетчика и увеличивает значение разрядной глубины. Затем мы копируем и удваиваем все элементы объекта TList (чтобы убедиться, что цикл работает правильно, советуем во время изучения этого материала обращаться к рисункам 7.1 (е) и 7.1 (f)).

Этот класс выполняет ряд важных подготовительных действий, необходимых для работы нашего основного класса TtdHashTableExtendible, код интерфейса которого приведен в листинге 7.25.

Листинг 7.25. Интерфейс класса TtdHashTableExtendible

type

TtdHashTableExtendible = class private

FCompare : TtdCompareRecordKey;

FCount : longint;

FDirectory: TtdHashDirectory;

FHashFunc : TtdHashFuncEx;

FName : TtdNameString;

FBuckets : TtdRecordStream;

FRecords : TtdRecordStream;

FRecord : pointer;

protected

procedure hteCreateNewHashTable;

procedure hteError(aErrorCode : integer;

const aMethodName : TtdNameString);

function hteErrorMsg(aErrorCode : integer;

const aMethodName : TtdNameString): string;

function hteFindBucket(const aKey : string; var aFindInfo): boolean;

procedure hteSplitBucket(var aFindlnfo);

public

constructor Create(aHashFunc : TtdHashFuncEx;

aCompare : TtdCompareRecordKey;

aDirStream : TStream;

aBucketStream : TtdRecordStream;

aRecordStream : TtdRecordStream);

destructor Destroy; override;

function Find(const aKey : string; var aRecord): boolean;

procedure Insert(const aKey : string; var aRecord);

property Count : longint read FCount;

property Name : TtdNameString read FName write FName;

end;

Этот класс поддерживает обычные методы конструктора и деструктора, а также возможность вставки записи и ее ключа и последующего поиска записи по ее ключу.

Как показано в листинге 7.26, конструктору Create передаются три потока и два указателя на функции. Три потока предназначены для каталога, групп и записей. Первая функция - обычная функция хеширования (хотя для этой хеш-таблицы функции хеширования должны создавать 32-разрядные значения;

в данном случае никакое деление по модулю на размер таблицы не выполняется). Вторая функция -функция сравнения значения ключа Key с записью, которая считывается из потока записей.

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

constructor TtdHashTableExtendible.Create(

aHashFunc : TtdHashFuncEx;

aCompare : TtdCompareRecordKey;

aDirStream : TStream;

aBucketStream : TtdRecordStream;

aRecordStream : TtdRecordStream);

begin

{создать предка}

inherited Create;

{создать каталог}

FDirectory := TtdHashDirectory.Create(aDirStream);

{сохранить параметры}

FHashFunc := aHashFunc;

FCompare := aCompare;

FBuckets := aBucketStream;

FRecords := aRecordStream;

{получить буфер для любой записи, которую нужно считать}

GetMem(FRecord, FRecords.RecordLength);

{если поток групп пуст, создать первую группу}

if (FBuckets.Count = 0) then

hteCreateNewHashTable;

end;

procedure TtdHashTableExtendible.hteCreateNewHashTable;

var

NewBucket : TBucket;

begin

FillChar(NewBucket, sizeof(NewBucket), 0);

FDirectory[0] := FBuckets.Add(NewBucket);

end;

Конструктор создает каталог, передавая его потоку каталогов и сохраняя параметры во внутренних полях. Если поток групп еще не содержит групп, конструктор вызывает защищенный метод hteCreateNewHashTable для определения новой таблицы. Этот метод добавляет первую пустую группу в поток групп, и сохраняет номер группы в качестве первой записи каталога.

Деструктор просто выполняет очистку, как показано в листинге 7.27

Листинг 7.27. Уничтожение экземпляра класса TtdHashTableExtendible

destructor TtdHashTableExtendible.Destroy;

begin

FDirectory.Free;

if (FRecord <> nil) then

FreeMem(FRecord, FRecords.RecordLength);

inherited Destroy;

end;

Теперь рассмотрим метод Find и его вспомогательный защищенный метод hteFindBucket, который, как обычно и все вспомогательные подпрограммы, выполняет большую часть работы. Из листинга 7.28 видно, что метод Find действительно всего лишь вызывает метод hteFindBucket, и, если тот возвращает значение "истина", копирует запись из внутреннего буфера и, в свою очередь, возвращает значение "истина". Если метод возвращает значение "ложь", это свидетельствует, что запись не была найдена, и метод Find также возвращает значение "ложь".

Листинг 7.28. Поиск записи по ее ключу type

THashElement = packed record

heHash : longint;

heItem : longint;

end;

PBucket = ^TBucket;

TBucket = packed record

bkDepth : longint;

bkCount : longint;

bkHashes : array [0..pred(tdcBucketItemCount)] of THashElement;

end;

PFindItemInfo = ^TFindItemInfo;

TFindItemlnf <= packed record

fiiHash : longint;

{хеш-значение параметра ключа}

fiiDirEntry : integer;

{запись каталога}

fiiSlot : integer;

{ячейка в группе}

fiiBucketNum : longint;

{номер группы в потоке}

fiiBucket : TBucket;

{группа}

end;

function TtdHashTableExtendible.Find(const aKey : string;

var aRecord): boolean;

var

FindInfo : TFindItemInfo;

begin

if hteFindBucket(aKey, FindInfo) then begin

Result := true;

Move(FRecord^, aRecord, FRecords.RecordLength);

end else

Result := false;

end;

function TtdHashTableExtendible.hteFindBucket(const aKey : string;

var aFindInfo): boolean;

var

FindInfo : PFindItemInfo;

Inx : integer;

IsDeleted : boolean;

begin

FindInfo := PFindItemInfo(@aFindInfo);

with Findlnfo^ do

begin

{вычислить хеш-значение для строки}

fiiHash := FHashFunc(aKey);

{вычислить запись в каталоге для этого хеш-значения, которая соответствует номеру группы}

fiiDirEntry := ReverseBits(fiiHash, FDirectory.Depth);

fiiBucketNum := FDirectory[fiiDirEntry];

{извлечь группу}

FBuckets.Read(fiiBucketNum, fiiBucket, IsDeleted);

if IsDeleted then

hteError(tdeHashTblDeletedBkt, 'hteFindBucket');

{выполнить поиск хеш-значения в группе, причем предполагается, что этот поиск будет безуспешным}

Result := false;

with fiiBucket do

begin

for Inx := 0 to pred(bkCount) do

begin {если хеш-значение совпадает...}

if (bkHashes [Inx].heHash = fiiHash) then begin

{считать запись}

FRecords.Read(bkHashes[Inx].heItem, FRecord^, IsDeleted);

if IsDeleted then

hteError(tdeHashTblDeletedRec, 'hteFindBucket');

{сравнить запись с ключом}

if FCompare(FRecord^, aKey) then begin

Result := true;

fiiSlot := Inx;

Exit;

end;

end;

end;

end;

end;

end;

Метод hteFindBucket представляет наибольший интерес. Вначале, подобно "обычной" хеш-таблице, он вычисляет хеш-значение ключа. Затем он вычисляет запись каталога, к которой это хеш-значение относится. Как упоминалось ранее, для этого необходимо инвертировать соответствующее количество младших разрядов. Требуемое количество разрядов равно разрядной глубине каталога и эту задачу выполняет небольшая подпрограмма ReverseBits.

Листинг 7.29. Вычисление записи каталога

function ReverseBits(aValue : longint;

aBitCount : integer): longint;

var

i : integer;

begin

Result := 0;

for i := 0 to pred(aBitCount) do

begin

Result := (Result shl 1) or (aValue and 1);

aValue := aValue shr 1;

end;

end;

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

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

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

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

Если запись не была найдена, метод возвращает все ранее перечисленные данные, за исключением номера ячейки. Использование этих данных показано на примере метода Insert, код которого показан в листинге 7.30.

Листинг 7.30. Вставка пары ключ/запись в хеш-таблицу

procedure TtdHashTableExtendible.Insert(const aKey : string;

var aRecord);

var

FindInfo : TFindItemInfo;

RRN : longint;

begin

if hteFindBucket(aKey, FindInfo) then

hteError(tdeHashTblKeyExists, 'Insert');

{выполнить проверку для выяснения наличия достаточного места в данной группе; если нет, разбить группу и повторить процесс поиска места для вставки элемента; процесс продолжается до момента обнаружения достаточного свободного места}

while (FindInfo.fiiBucket.bkCount >= tdcBucketItemCount) do

begin

hteSplitBucket(FindInfo);

if hteFindBucket(aKey, FindInfo) then

hteError(tdeHashTblKeyExists, 'Insert');

end;

{добавить запись в поток записей для получения номера записи}

RRN := FRecords.Add(aRecord);

{добавить хеш-значения в конец списка, обновить группу}

with Findinfo, Findinfo.fiiBucket do

begin

bkHashes[bkCount].heHash := fiiHash;

bkHashes[bkCount].heitern := RRN;

inc(bkCount);

FBuckets.Write(fiiBucketNum, fiiBucket);

end;

{имеется еще одна запись}

inc(FCount);

end;

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

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

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

Итак, рассмотрим последний метод - hteSplitBucket. На данный момент он является наиболее сложным методом класса. Листинг 7.31 содержит подробные комментарии, но чтобы работа метода была понятнее, рекомендуем снова обратиться к рисунку 7.1.

Листинг 7.31. Разбиение группы

procedure TtdHashTableExtendible.hteSplitBucket(var aFindInfo);

var

FindInfo : PFindItemInfo;

Inx : integer;

NewBucket : TBucket;

Mask : longint;

OldValue : longint;

OldInx : integer;

NewInx : integer;

NewBucketNum : longint;

StartDirEntry : longint;

NewStartDirEntry : longint;

EndDirEntry : longint;

begin

FindInfo := PFindItemInfo(@aFindInfo);

{если разбиваемая группа имеет такую же разрядную глубину, как каталог, удвоить емкость каталога}

if (FindInfo^.fiiBucket.bkDepth *= FDirectory.Depth) then begin

FDirectory.DoubleCount;

{обновить элемент каталога новой группой, которая была разбита}

FindInfo^.fiiDirEntry := FindInfo^.fiiDirEntry * 2;

end;

{вычислить диапазон записей каталога, указывающих на исходную группу, и диапазон для новой группы}

StartDirEntry := FindInfo^.fiiDirEntry;

while (StartDirEntry >= 0) and

(FDirectory[StartDirEntry] = FindInfo^.fiiBucketNum) do

dec(StartDirEntry);

inc(StartDirEntry);

EndDirEntry := FindInfo^.fiiDirEntry;

while (EndDirEntry < FDirectory.Count) and

(FDirectory[EndDirEntry] = FindInfo^.fiiBucketNum) do inc(EndDirEntry);

dec(EndDirEntry);

NewStartDirEntry := (StartDirEntry + EndDirEntry + 1) div 2;

{увеличить разрядную глубину разбиваемой группы}

inc(FindInfo^.fiiBucket.bkDepth);

{инициализировать новую группу; она будет иметь такую же разрядную глубину, как и разбиваемая группа}

FillChar(NewBucket, sizeof(NewBucket), 0);

NewBucket.bkDepth := FindInfo^.fiiBucket.bkDepth;

{вычислить маску AND, которая будет использоваться для выяснения места помещения хеш-записей}

Mask := (1 shl NewBucket.bkDepth) - 1;

{вычислить значение, полученное в результате применения маски AND, для хеш-записей старой группы}

OldValue := ReverseBits (StartDirEntry, FDirectory.Depth) and Mask;

{считать старую группу и перенести в новую группу принадлежащие ей хеш - значения}

OldInx := 0;

NewInx := 0;

with FindInfo^.fiiBucket do

for Inx := 0 to pred(bkCount) do

begin

if (bkHashes [Inx].heHash and Mask) = OldValue then

begin

bkHashes[OldInx] := bkHashes[Inx];

inc(OldInx);

end

else begin

NewBucket.bkHashes[NewInx] := bkHashes[Inx];

inc(NewInx);

end;

end;

{установить счетчики для обеих групп}

FindInfo^.fiiBucket.bkCount := OldInx;

NewBucket.bkCount := NewInx;

{добавить новую группу в поток групп, обновить старую группу}

NewBucketNum := FBucketsAdd (NewBucket);

FBuckets.Write(FindInfo^.fiiBucketNum, FindInfo^.fiiBucket);

{установить все записи в новом диапазоне каталога в соответствие с новой группой}

for Inx := NewStartDirEntry to EndDirEntry do

FDirectory[ Inx ] := NewBucketNum;

end;

Прежде всего, выполняется проверка, равна ли разрядная глубина разбиваемой группы разрядной глубине каталога. Если да, то необходимо вдвое увеличить размер каталога и обеспечить обновление отслеживаемого значения записи каталога. Например, если запись FindInfo^.fiitiirEntry имела значение, равное 3, и мы вдвое увеличили размер каталога, то теперь она должна иметь значение, равное 6 (или, если быть точным, 7, поскольку обе новые записи каталога указывают на одну и ту же группу).

Теперь нужно выяснить диапазон записей каталога, которые указывают на разбиваемую группу. В соответствии с рисунком 7.1 (g), если бы пришлось разбивать запись 2?, диапазон был бы 4-7. Разбиваемая группа должна остаться в первой половине этого диапазона, а новая группа, которую предстоит заполнить, будет занимать вторую половину диапазона записей каталога.

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

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

Желательно разработать метод, с помощью которого можно было бы непосредственно определить, в какую группу должно помещаться хеш-значение. Предположим, что имеет место следующая ситуация: разрядная глубина каталога равна 3, но разрядная глубина группы равна 2. Записи 4 и 5 каталога указывают на группу A, которая заполнена, а записи 6 и 7 - на пустую группу B. Куда Должно быть помещено данное хеш-значение? Прежде всего, следует осознать, что группа А содержит только те хеш-значения, последними разрядами которых являются 001, 101, 011 или 111 (чтобы убедиться в этом, проинвертируйте разряды для получения записей 4, 5, 6 и 7 каталога). Если хеш-значение имеет окончание 001 или 101, оно будет помещено в группу A. Если оно имеет окончание 011 или 111, оно будет помещено в группу B. Все еще не понятно, не так ли? Что ж, первые две комбинации заканчиваются разрядами 01, в то время как две вторые комбинации - разрядами 11. Почему учитываются только два разряда? Вспомним, что разрядная глубина группы равна 2. Идея состоит в том, чтобы вычислить запись каталога, соответствующую началу диапазона (которое нам известно), проинвертировать разряды, соответствующие разрядной глубине каталога, и выполнить операцию AND для полученного результата и маски, которая была сгенерирована из значения разрядной глубины группы. Затем эту маску можно использовать для разбиения хеш-значений по категориям. Именно эти действия и выполняются в среднем разделе подпрограммы.

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

Полный код класса TtdHashTableExtendible можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshExt.pas.

Оглавление книги