обычно и все вспомогательные подпрограммы, выполняет большую часть работы. Из листинга 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;
