htcError(tdeHashTblNoHashFunc, 'Create');
FHashFunc := aHashFunc;
FTable := TList.Create;
FTable.Count := TDGetClosestPrime(aTableSize);
FNodeMgr := TtdNodeManager.Create(sizeof(THashedItem));
htcAllocHeads(FTable);
FMaxLoadFactor := 5;
end;
destructor TtdHashTableChained.Destroy;
begin
if (FTable <> nil) then begin
Clear;
htcFreeHeads(FTable);
FTable.Destroy;
end;
FNodeMgr.Free;
inherited Destroy;
end;
Созданный нами диспетчер узлов предназначен для работы с узлами THashItem. Он определяет структуру записей этого типа. Эта структура во многом аналогична структуре записей класса TtdHashLinear, за исключением того, что требуется связное поле и не требуется поле "используется" (все элементы в связном списке "используются" по определению;
удаленные из хеш-таблицы элементы в связном списке отсутствуют).
type
PHashedItem = ^THashedItem;
THashedItem = packed record
hiNext : PHashedItem;
hiItem : pointer;
{$IFDEF Delphi1}
hiKey : PString;
{$ELSE}
hiKey : string;
{$ENDIF}
end;
Конструктор вызывает метод htcAllocHeads для создания первоначально пустой хеш-таблицы. Вот что должно при этом происходить. Каждая ячейка в хеш-таблице будет содержать указатель на односвязный список (поскольку каждая ячейка содержит только указатель, для хранения хеш-таблицы можно воспользоваться TList). Для упрощения вставки и удаления элементов мы выделяем заглавные узлы для каждого возможного связного списка, как было описано в главе 3. Естественно, деструктор должен освобождать эти заглавные узлы - данная операция выполняется при помощи метода htcFreeHeads.
Листинг 7.13. Выделение и освобождение заглавных узлов связных списков
procedure TtdHashTableChained.htcAllocHeads(aTable : TList);
var
Inx : integer;
begin
for Inx := 0 to pred(aTable.Count) do
aTable.List^[Inx] := FNodeMgr.AllocNodeClear;
end;
procedure TtdHashTableChained.htcFreeHeads(aTable : TList);
var
Inx : integer;
begin
for Inx := 0 to pred(aTable.Count) do
FNodeMgr.FreeNode(aTable.List^[Inx]);
end;
Теперь посмотрим, как выполняется вставка нового элемента и его строкового ключа в хеш-таблицу, которая использует связывание.
Листинг 7.14. Вставка нового элемента в хеш-таблицу со связыванием
procedure TtdHashTableChained.Insert(const aKey : string; aItem : pointer );
var
Inx : integer;
Parent : pointer;
NewNode : PHashedItem;
begin
if htcFindPrim(aKey, Inx, Parent) then
htcError(tdeHashTblKeyExists, 'Insert');
NewNode := FNodeMgr.AllocNodeClear;
{$IFDEF Delphi1}
NewNode^.hiKey := NewStr(aKey);
{$ELSE}
NewNode^.hiKey := aKey;
{$ENDIF}
NewNode^.hi Item := aItem;
NewNode^.hiNext := PHashedItem(Parent)^.hiNext;
PHashedItem(Parent)^.hiNext := NewNode;
inc(FCount);
{увеличить таблицу, если значение коэффициента загрузки превышает максимальное значение}
if (FCount > (FMaxLoadFactor * FTable.Count)) then
htcGrowTable;
end;
Прежде всего, мы вызываем подпрограмму htcFindPrim. Она выполняет такую же операцию, как и htllIndexOf, при использовании линейного зондирования: предпринимает попытку найти ключ и возвращает индекс ячейки, в которой он был найден. Однако этот метод создан с учетом применения связных списков. Если поиск ключа выполняется успешно, метод возвращает значение "истина", а также индекс ячейки хеш-таблицы и указатель на родительский узел элемента в связном списке. Почему родительский? Что ж, если вспомнить сказанное в главе 3, основные операции с односвязным списком предполагают вставку и удаление узла за данным узлом. Следовательно, целесообразнее, чтобы метод htcFindPrim возвращал родительский узел узла, в который выполняется вставка.
Если ключ не найден, метод htcFindPrlm возвращает значение "ложь" и индекс ячейки, в которую нужно вставить элемент, и родительский узел, за которым его можно успешно вставить.
Итак, вернемся к методу Insert. ЕстестЁенно, если ключ был найден, метод генерирует ошибку. В противном случае мы выделяем новый узел, устанавливаем элемент и ключ, а затем вставляем элемент непосредственно за данным узлом.
Если при этом коэффициент загрузки хеш-таблицы достигает максимального значения, мы расширяем хеш-таблицу.
Как легко догадаться, метод 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 в случае вставки слишком большого количества элементов.
