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

Теперь пора рассмотреть какой-нибудь код. Общедоступный интерфейс к классу TtdHashTableChained в общих чертах не отличается от такового для класса TtdHashTableLinear. Различия между двумя этими классами проявляются в разделах private и protected.

Листинг 7.11. Класс TtdHashTableChained

type

TtdHashChainUsage = ( {Применение цепочек хеш-таблицы-}

hcuFirst, {..вставка в начало}

hcuLast);

{..вставка в конец}

type

TtdHashTableChained = class

{хеш-таблица, в которой для разрешения конфликтов используется связывание}

private

FChainUsage : TtdHashChainUsage;

FCount : integer;

FDispose : TtdDisposeProc;

FHashFunc : TtdHashFunc;

FName : TtdNameString;

FTable : TList;

FNodeMgr : TtdNodeManager;

FMaxLoadFactor : integer;

protected

procedure htcSetMaxLoadFactor(aMLF : integer);

procedure htcAllocHeads(aTable : TList);

procedure htcAlterTableSize(aNewTableSize : integer);

procedure htcError(aErrorCode : integer;

const aMethodName : TtdNameString);

function htcFindPrim(const aKey : string;

var aInx : integer; var aParent : pointer): boolean;

procedure htcFreeHeads(aTable : TList);

procedure htcGrowTable;

public

constructor Create(aTableSize : integer;

aHashFunc : TtdHashFunc; aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Delete(const aKey : string);

procedure Clear;

function Find(const aKey : string; var aItem : pointer): boolean;

procedure Insert(const aKey : string; aItem : pointer);

property Count : integer read FCount;

property MaxLoadFactor : integer

read FMaxLoadFactor write htcSetMaxLoadFactor;

property Name : TtdNameString read FName write FName;

property ChainUsage : TtdHashChainUsage

read FChainUsage write FChainUsage;

end;

Мы объявили небольшой перечислимый тип TtdHashChainUsage для указания того, выполняется ли вставка элементов в начало или в конец связного списка. Класс содержит свойство ChainUsage, которое указывает, какой метод следует использовать.

---------

Свойство MaxLoadFactor служит для выполнения еще одной настройки. Оно определяет среднюю максимальную длину связных списков, хранящихся в каждой из ячеек. Если средняя длина связных списков становится слишком большой, класс увеличит внутреннюю хеш-таблицу, используемую для хранения элементов, и повторит их вставку.

Использование свойства 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}

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