Бакнелл Джулиан М.
Шрифт:
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). Вместо помещения связного списка в каждую ячейку, в нее помещается группа, которая по существу представляет собой массив элементов фиксированного размера. При создании хеш-таблицы необходимо выделить группу для каждой ячейки и пометить все элементы в каждой группе как "пустые".
Чтобы вставить элемент, мы хешируем ключ элемента с целью определения номера ячейки. Затем мы просматриваем все элементы в группе, пока не обнаружим элемент, помеченный как пустой, и присваиваем его элементу, который пытаемся вставить (понятно, что в случае присутствия элемента в группе генерируется ошибка).
Но что делать, если в группе больше нет пустых элементов? В этом случае доступны две возможности. Первая соответствует применению подхода линейного зондирования, а вторая - использованию групп переполнения.