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

Однако необходимо учитывать еще одно соображение. При каждом зондировании выполняется сравнение искомого ключа с ключом элемента в хеш-таблице. Если сравнение занимает длительное время, как при поиске длинной строки, значение 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}

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. ЕстестЁенно, если ключ был найден, метод генерирует ошибку. В противном случае мы выделяем новый узел, устанавливаем элемент и ключ, а затем вставляем элемент непосредственно за данным узлом.