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

Если запись была найдена, метод 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, которая будет использоваться для выяснения места помещения хеш-записей}

Mask := (1 shl NewBucket.bkDepth) - 1;

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

OldValue := ReverseBits (StartDirEntry, FDirectory.Depth) and Mask;

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

OldInx := 0;

NewInx := 0;

with FindInfo^.fiiBucket do

for Inx := 0 to pred(bkCount) do

begin

if (bkHashes [Inx].heHash and Mask) = OldValue then

begin

bkHashes[OldInx] := bkHashes[Inx];

inc(OldInx);

end

else begin

NewBucket.bkHashes[NewInx] := bkHashes[Inx];

inc(NewInx);

end;

end;

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

FindInfo^.fiiBucket.bkCount := OldInx;

NewBucket.bkCount := NewInx;

{добавить новую группу в поток групп, обновить старую группу}

NewBucketNum := FBucketsAdd (NewBucket);

FBuckets.Write(FindInfo^.fiiBucketNum, FindInfo^.fiiBucket);

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

for Inx := NewStartDirEntry to EndDirEntry do

FDirectory[ Inx ] := NewBucketNum;

end;

Прежде всего, выполняется проверка, равна ли разрядная глубина разбиваемой группы разрядной глубине каталога. Если да, то необходимо вдвое увеличить размер каталога и обеспечить обновление отслеживаемого значения записи каталога. Например, если запись FindInfo^.fiitiirEntry имела значение, равное 3, и мы вдвое увеличили размер каталога, то теперь она должна иметь значение, равное 6 (или, если быть точным, 7, поскольку обе новые записи каталога указывают на одну и ту же группу).

Теперь нужно выяснить диапазон записей каталога, которые указывают на разбиваемую группу. В соответствии с рисунком 7.1 (g), если бы пришлось разбивать запись 2?, диапазон был бы 4-7. Разбиваемая группа должна остаться в первой половине этого диапазона, а новая группа, которую предстоит заполнить, будет занимать вторую половину диапазона записей каталога.

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

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

Желательно разработать метод, с помощью которого можно было бы непосредственно определить, в какую группу должно помещаться хеш-значение. Предположим, что имеет место следующая ситуация: разрядная глубина каталога равна 3, но разрядная глубина группы равна 2. Записи 4 и 5 каталога указывают на группу A, которая заполнена, а записи 6 и 7 - на пустую группу B. Куда Должно быть помещено данное хеш-значение? Прежде всего, следует осознать, что группа А содержит только те хеш-значения, последними разрядами которых являются 001, 101, 011 или 111 (чтобы убедиться в этом, проинвертируйте разряды для получения записей 4, 5, 6 и 7 каталога). Если хеш-значение имеет окончание 001 или 101, оно будет помещено в группу A. Если оно имеет окончание 011 или 111, оно будет помещено в группу B. Все еще не понятно, не так ли? Что ж, первые две комбинации заканчиваются разрядами 01, в то время как две вторые комбинации - разрядами 11. Почему учитываются только два разряда? Вспомним, что разрядная глубина группы равна 2. Идея состоит в том, чтобы вычислить запись каталога, соответствующую началу диапазона (которое нам известно), проинвертировать разряды, соответствующие разрядной глубине каталога, и выполнить операцию AND для полученного результата и маски, которая была сгенерирована из значения разрядной глубины группы. Затем эту маску можно использовать для разбиения хеш-значений по категориям. Именно эти действия и выполняются в среднем разделе подпрограммы.

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

Полный код класса TtdHashTableExtendible можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshExt.pas.

Резюме

В этой главе были рассмотрены хеш-таблицы - структуры данных, которые пытаются предоставить максимально быстрый доступ к своим элементам, при этом они подпадают под категорию O(1).

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