Использование свойства MaxLoadFactor может оказаться затруднительным. Какое значение оно должно иметь? Вспомните, что его можно считать равным средней длине связных списков, хранящихся в каждой из ячеек. Если придерживаться правила, применяемого для линейного зондирования, в соответствии с которым коэффициент загрузки выбирается так, чтобы для обнаружения промаха при поиске требовалось в среднем пять зондирований, то значение MaxLoadFactor должно быть равно пяти.
---------
Однако необходимо учитывать еще одно соображение. При каждом зондировании выполняется сравнение искомого ключа с ключом элемента в хеш-таблице. Если сравнение занимает длительное время, как при поиске длинной строки, значение MaxLoadFactor должно быть меньше. Если сравнение выполняется значительно быстрее (например, в случае поиска короткой строки или целого числа), значение MaxLoadFactor может быть больше. Как и в случае любых настроек, чтобы добиться наилучших результатов, потребуется провести некоторый объем экспериментов.
Если внимательно присмотреться к коду, то мы увидим, что в нем используется хорошо известный нам класс TtdNodeManager (как именно - будет показано вскоре). Конструктор Create, как и TList, будет выделять один экземпляр этого класса. Деструктор Destroy будет освобождать оба эти экземпляра.
Листинг 7.12. Конструктор и деструктор класса TtdHashTableChained
constructor TtdHashTableChained.Create(aTableSize : integer;
aHashFunc : TtdHashFunc;
aDispose : TtdDisposeProc);
begin
inherited Create;
FDispose := aDispose;
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;
Теперь посмотрим, как выполняется вставка нового элемента и его строкового ключа в хеш-таблицу, которая использует связывание.
Листинг 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}
