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

Листинг 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.

Существует разновидность метода связывания для разрешения конфликтов, которая носит название группирования в блоки (bucketing). Вместо помещения связного списка в каждую ячейку, в нее помещается группа, которая по существу представляет собой массив элементов фиксированного размера. При создании хеш-таблицы необходимо выделить группу для каждой ячейки и пометить все элементы в каждой группе как "пустые".