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;