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

Если при этом коэффициент загрузки хеш-таблицы достигает максимального значения, мы расширяем хеш-таблицу.

Как легко догадаться, метод 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

{предпринять попытку очистки и сохранения хеш-таблицы в непротиворечивом состоянии в случае возникновения исключения}

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;

Walker^.hiNext := Head^.hiNext;

Head^.hiNext := Walker;

Parent := Head;

end;

aInx := Inx;

aParent := Parent;

Result := true;

Exit;

end;

Parent := Walker;

Walker := Walker^.hiNext;

end;

{достижение этой точки свидетельствует о том, что ключ не найден}

aInx := Inx;

if ChainUsage = hcuLast then

aParent := Parent else

aParent := Head;

Result := false;

end;

Работа метода начинается с хеширования переданного ему ключа. В результате мы получаем индекс ячейки, в которой найден заголовок связного списка. Мы перемещаемся вниз по связному списку до тех пор, пока не найдем искомый элемент или не встретим указатель nil, обозначающий конец списка. В ходе этого мы поддерживаем родительскую переменную, поскольку вызывающему методу нужно вернуть этот узел, а не указатель на узел элемента.

Если ключ не был найден, мы возвращаем узел в конце списка или заглавный узел - это определяется свойством ChainUsage. Если его значение установлено равным hcuLast, мы возвращаем последний узел, если оно установлено равным hcuFirst - заглавный узел. Таким образом, если вызывающим методом был метод Insert, можно быть уверенным, что новый элемент будет вставлен в требуемое место. Метод возвращает также индекс ячейки.

Если ключ был найден и значением свойства ChainUsage является hcuFirst, необходимо воспользоваться методологией "перемещения в начало" и переместить найденный элемент в первую позицию связного списка. Конечно, в случае использования односвязного списка эта операция проста и эффективна. И, наконец, мы возвращаем родительский узел и индекс ячейки.

Полный исходный код класса TtdHashTableChained можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshChn.pas.