Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
end;
Конструктор создает каталог, передавая его потоку каталогов и сохраняя параметры во внутренних полях. Если поток групп еще не содержит групп, конструктор вызывает защищенный метод hteCreateNewHashTable для определения новой таблицы. Этот метод добавляет первую пустую группу в поток групп, и сохраняет номер группы в качестве первой записи каталога.
Деструктор просто выполняет очистку, как показано в листинге 7.27
Листинг 7.27. Уничтожение экземпляра класса TtdHashTableExtendible
destructor TtdHashTableExtendible.Destroy;
begin
FDirectory.Free;
if (FRecord <> nil) then
FreeMem(FRecord, FRecords.RecordLength);
inherited Destroy;
end;
Теперь
Листинг 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');
{выполнить проверку для выяснения наличия достаточного места в данной группе; если нет, разбить группу и повторить процесс поиска места для вставки элемента; процесс продолжается до момента обнаружения достаточного свободного места}