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

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