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

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. Разбиваемая группа должна остаться в первой половине этого диапазона, а новая группа, которую предстоит заполнить, будет занимать вторую половину диапазона записей каталога.

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