Result := true;
aItem := PHashedItem(Parent)^.hiNext^.hiItem;
end
else begin
Result := false;
aItem := nil;
end;
end;
Единственная небольшая сложность состоит в том, что метод htcFindPrim возвращает родительский узел действительно интересующего нас узла.
Увеличение хеш-таблицы - вовсе не то, что требуется, поскольку при этом необходимо выполнить очень много операций по перемещению данных. Однако класс содержит автоматическую операцию увеличения таблицы. Свойство MaxLoadFactor управляет тем, когда это происходит, вызывая метод htcGrowTable в случае вставки слишком большого количества элементов.
Листинг 7.18. Увеличение хеш-таблицы со связыванием
procedure TtdHashTableChained.htcGrowTable;
begin
{увеличить размер таблицы примерно в два раза по сравнению с предыдущим размером}
htcAlterTableSize(TDGetClosestPrime(succ(FTable.Count * 2)));
end;
procedure TtdHashTableChained.htcAlterTableSize(aNewTableSize : integer);
var
Inx : integer;
OldTable : TList;
Walker, Temp : PHashedItem;
begin
{сохранить старую таблицу}
OldTable := FTable;
{распределить новую таблицу}
FTable := TList.Create;
try
FTable.Count := aNewTableSize;
htcAllocHeads(FTable);
{считывать старую таблицу и перенести ключи и элементы в новую таблицу посредством их вставки}
FCount := 0;
for Inx := 0 to pred(OldTable.Count) do
begin
Walker := PHashedItem(OldTable.List^[Inx])^.hiNext;
while (Walker <> nil) do
begin
{$IFDEF Delphi1}
Insert(Walker^.hiKey^, Walker^.hiItem);
{$ELSE}
Insert(Walker^.hiKey, Walker^.hiItem);
{$ENDIF}
Walker := Walker^.hiNext;
end;
end;
except
{предпринять попытку очистки и сохранения хеш-таблицы в непротиворечивом состоянии в случае возникновения исключения}
Clear;
htcFreeHeads(FTable);
FTable.Free;
FTable := OldTable;
raise;
end;
{теперь новая таблица полностью заполнена всеми элементами и их ключами, поэтому необходимо уничтожить старую таблицу и ее связные списки}
for Inx := 0 to pred(01dTable.Count) do
begin
Walker := PHashedItem(OldTable.List^[Inx])^.hiNext;
while (Walker <> nil) do
begin
{$IFDEF Delphi1}
DisposeStr(Walker^.hiKey);
{$ELSE}
Walker^.hiKey := '';
{$ENDIF}
Temp := Walker;
Walker := Walker^.hiNext;
FNodeMgr.FreeNode(Temp);
end;
PHashedItem(OldTable.List^[Inx])^.hiNext := nil;
end;
htcFreeHeads(OldTable);
OldTable.Free;
end;
В этом классе реализация метода htcAlterTableSize оказывается значительно сложнее, нежели в классе с линейным зондированием. Чтобы обеспечить корректное восстановление после возникновения исключительных состояний, возникающих при увеличении таблицы, увеличение выполняется в два этапа. Вначале элементы и их ключи копируются в новую таблицу большего размера. Затем, сразу по завершении первого этапа, мы избавляемся от узлов в меньшей таблице.
В заключение рассмотрим основной метод, используемый многими методами класса хеш-таблицы - htcFindPrim (листинг 7.19).
Листинг 7.19. Примитив для поиска элемента в хеш-таблице со связыванием
function TtdHashTableChained.htcFindPrim( const aKey : string;
var aInx : integer;
var aParent : pointer): boolean;
var
Inx : integer;
Head, Walker, Parent : PHashedItem;
begin
