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;