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

Теперь рассмотрим метод 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');