Фундаментальные алгоритмы и структуры данных в 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;