Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Метод Clear очень похож на метод Delete, за исключением того, что мы просто стандартным образом удаляем все узлы из каждого связного списка (естественно, за исключением заглавных узлов).
Листинг 7.16. Очистка хеш-таблицы TtdHashTableChained
procedure TtdHashTableChained.Clear;
var
Inx : integer;
Temp, Walker : PHashedItem;
begin
for Inx := 0 to pred(FTable.Count) do
begin
Walker := PHashedItem(FTable.List^[Inx])^.hiNext;
while (Walker <> nil) do
begin
if Assigned(FDispose) then
FDispose(Walker^.hiItem);
{$IFDEF Delphi1}
DisposeStr(Walker^.hiKey);
{$ELSE}
Walker^.hiKey := '';
{$ENDIF}
Temp := Walker;
Walker := Walker^.hiNext;
FNodeMgr.FreeNode(Temp);
end;
PHashedItem(FTable.List^[Inx])^.hiNext := nil;
end;
FCount := 0;
end;
Метод Find
Листинг 7.17. Поиск элемента в хеш-таблице со связыванием
function TtdHashTableChained.Find(const aKey : string; var aItem : pointer): boolean;
var
Inx : integer;
Parent : pointer;
begin
if htcFindPrim(aKey, Inx, Parent) then begin
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
{вычислить хеш-значение для строки}
Inx := FHashFunc(aKey, FTable.Count);
{предположить, что связный список существует в Inx-ой ячейке}
Head := PHashedItem(FTable.List^[Inx]);
{начать просмотр связного списка с целью поиска ключа}
Parent := Head;
Walker := Head^.hiNext;
while (Walker <> nil) do
begin
{$lFDEFDelphi1}
if (Walker^.hiKey^ = aKey) then begin
{$ELSE}
if (Walker^.hiKey = aKey) then begin
{$ENDIF}
if (ChainUsage = hcuFirst) and (Parent = Head) then begin
Parent^.hiNext := Walker^.hiNext;