if not Assigned(aHashFunc) then
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;
Теперь посмотрим, как выполняется вставка нового элемента и его строкового ключа в хеш-таблицу, которая использует связывание.