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);