Бакнелл Джулиан М.
Шрифт:
Как легко догадаться, метод Delete работает аналогично.
Листинг 7.15. Удаление элемента из хеш-таблицы со связыванием
procedure TtdHashTableChained.Delete(const aKey : string);
var
Inx : integer;
Parent : pointer;
Temp : PHashedItem;
begin
{поиск ключа}
if not htcFindPrim(aKey, Inx, Parent) then
htcError(tdeHashTblKeyNotFound, 'Delete');
{удалить элемент и ключ из данного узла}
Temp := PHashedItem(Parent)^.hiNext;
if Assigned(FDispose) then
FDispose(Temp^.hiItem);
{$IFDEF Delphi1}
DisposeStr(Temp^.hiKey);
{$ELSE}
Temp^.hiKey := '';
{$ENDIF}
{разорвать связь с узлом и освободить его}
PHashedItem(Parent)^.hiNext := Temp^.hiNext;
FNodeMgr.FreeNode(Temp);
dec(FCount);
end;
Мы предпринимаем попытку найти ключ (если он не найден, метод генерирует ошибку), а затем избавляемся от содержимого возвращенного элемента и удаляем его из связного списка. Обратите внимание на простоту кода обеих методов, Insert и Delete, обусловленную наличием заглавного узла в каждом связном списке. Не нужно беспокоиться о том, является ли родительский узел нулевым. Метод htcFindPrlm всегда будет возвращать допустимый родительский узел.
Метод 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 прост, поскольку основная часть работы выполняется вездесущим методом htcFindPrim.
Листинг 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
{предпринять попытку очистки и сохранения хеш-таблицы в непротиворечивом состоянии в случае возникновения исключения}