Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
Листинг 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 будет поддерживать удаление, и эта дополнительная информация понадобится.
