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

Бакнелл Джулиан М.

Как уже говорилось ранее, методы 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');

{выполнить проверку для выяснения наличия достаточного места в данной группе; если нет, разбить группу и повторить процесс поиска места для вставки элемента; процесс продолжается до момента обнаружения достаточного свободного места}

while (FindInfo.fiiBucket.bkCount >= tdcBucketItemCount) do

begin

hteSplitBucket(FindInfo);

if hteFindBucket(aKey, FindInfo) then

hteError(tdeHashTblKeyExists, 'Insert');

end;

{добавить запись в поток записей для получения номера записи}

RRN := FRecords.Add(aRecord);

{добавить хеш-значения в конец списка, обновить группу}

with Findinfo, Findinfo.fiiBucket do

begin

bkHashes[bkCount].heHash := fiiHash;

bkHashes[bkCount].heitern := RRN;

inc(bkCount);

FBuckets.Write(fiiBucketNum, fiiBucket);

end;

{имеется еще одна запись}

inc(FCount);

end;

При вставке, прежде всего, следует попытаться найти пару ключ/запись. Если это удается, генерируется ошибка. Если же нет - метод hteFindBucket вернет разнообразную информацию: хеш-значение ключа (чтобы его не нужно было повторно вычислять), запись каталога, номер группы и саму группу, в которой должно находиться хеш-значение ключа.

Мы проверяем, заполнена ли группа. Пока предположим, что это не так. Мы добавляем запись в поток записей - что позволяет

получить номер записи, - а затем добавляем пару хеш-значение/номер записи в конец группы, увеличивая значения обычно применяемых в таких случаях счетчиков.

Если группа заполнена, ее нужно разбить. Это делает другой скрытый защищенный метод hteSplitBucket. Как только он осуществляет возврат, необходимо повторить попытку поиска элемента, чтобы определить необходимую информацию таким образом, чтобы можно было легко добавить пару ключ/запись. Хотя и был включен код проверки на предмет обнаружения пары ключ/запись и генерирования ошибки в случае возникновения упомянутой ситуации, хеш-таблица действительно тщательно очищена - как мы уже убедились, подобная ситуация не возникает.

Итак, рассмотрим последний метод - hteSplitBucket. На данный момент он является наиболее сложным методом класса. Листинг 7.31 содержит подробные комментарии, но чтобы работа метода была понятнее, рекомендуем снова обратиться к рисунку 7.1.

Листинг 7.31. Разбиение группы

procedure TtdHashTableExtendible.hteSplitBucket(var aFindInfo);

var

FindInfo : PFindItemInfo;

Inx : integer;

NewBucket : TBucket;

Mask : longint;

OldValue : longint;

OldInx : integer;

NewInx : integer;

NewBucketNum : longint;

StartDirEntry : longint;

NewStartDirEntry : longint;

EndDirEntry : longint;

begin

FindInfo := PFindItemInfo(@aFindInfo);

{если разбиваемая группа имеет такую же разрядную глубину, как каталог, удвоить емкость каталога}

if (FindInfo^.fiiBucket.bkDepth *= FDirectory.Depth) then begin

FDirectory.DoubleCount;

{обновить элемент каталога новой группой, которая была разбита}

FindInfo^.fiiDirEntry := FindInfo^.fiiDirEntry * 2;

end;

{вычислить диапазон записей каталога, указывающих на исходную группу, и диапазон для новой группы}

StartDirEntry := FindInfo^.fiiDirEntry;

while (StartDirEntry >= 0) and

(FDirectory[StartDirEntry] = FindInfo^.fiiBucketNum) do

dec(StartDirEntry);

inc(StartDirEntry);

EndDirEntry := FindInfo^.fiiDirEntry;

while (EndDirEntry < FDirectory.Count) and

(FDirectory[EndDirEntry] = FindInfo^.fiiBucketNum) do inc(EndDirEntry);

dec(EndDirEntry);

NewStartDirEntry := (StartDirEntry + EndDirEntry + 1) div 2;

{увеличить разрядную глубину разбиваемой группы}

inc(FindInfo^.fiiBucket.bkDepth);

{инициализировать новую группу; она будет иметь такую же разрядную глубину, как и разбиваемая группа}

FillChar(NewBucket, sizeof(NewBucket), 0);

NewBucket.bkDepth := FindInfo^.fiiBucket.bkDepth;

{вычислить маску AND, которая будет использоваться для выяснения места помещения хеш-записей}