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

В листинге 7.3 приведен код интерфейса для хеш-таблицы с линейным зондированием (полный исходный код этого класса можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshLnP.pas). По поводу этой реализации следует привести ряд замечаний. Во-первых, мы принимаем соглашение, что ключом элемента является строка, отдельная от самого элемента. Это существенно упрощает как понимание кода, так и разработку и использование хеш-таблицы. В подавляющем большинстве случаев ключи все равно будут строками, а преобразование других типов данных в строки обычно не представляет особой сложности.

Второе соглашение состоит в том, что хотя класс будет допускать использование любой функции хеширования, функция должна иметь тип TtdHashFunc.

type

TtdHashFunc = function ( const aKey : string;

aTableSize : integer): integer;

Если вы еще раз взглянете на листинги 7.1 и 7.2, то убедитесь, что в обоих случаях функции имеют этот тип.

Листинг 7.3. Хеш-таблица линейного зондирования TtdHashTableLinear

type

TtdHashTableLinear = class

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

private

FCount : integer;

FDispose: TtdDisposeProc;

FHashFunc : TtdHashFunc;

FName : TtdNameString;

FTable : TtdRecordList;

protected

procedure htlAlterTableSize(aNewTableSize : integer);

procedure htlError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure htlGrowTable;

function htlIndexOf( const aKey : string; var aSlot : pointer): integer;

public

constructor Create(aTableSize : integer;

aHashFunc : TtdHashFunc;

aDispose : TtdDisposeProc);

destructor Destroy; override;

procedure Delete(const aKey : string);

procedure Empty;

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

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

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

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

Как видите, для хранения самой хеш-таблицы будет использоваться экземпляр TtdRecordList. Интерфейс класса не дает никакого представления о структуре элементов хеш-таблицы, т.е. ячеек. Эта информация скрыта в разделе реализации модуля.

type

PHashSlot = ^THashSlot;

THashSlot = packed record

{$IFDEF Delphi1}

hsKey : PString;

{$ELSE}

hsKey : string;

{$ENDIF}

hsItem : pointer;

hsInUse: boolean;

end;

Ячейка представляет собой запись с тремя полями: ключом, собственно элементом и состоянием ячейки (независимо от того, используется оно или нет). В Delphi1 ключ - это указатель строки, в то время как в последующих версиях он является длинной строкой (которая, естественно, представляет собой замаскированный указатель).

Конструктор Create выделяет экземпляр списка записей, а деструктор Destroy освобождает его.

Листинг 7.4. Конструктор и деструктор класса TtdHashTableLinear

constructor TtdHashTableLinear.Create( aTableSize : integer;

aHashFunc : TtdHashFunc;

aDispose : TtdDisposeProc );

begin

inherited Create;

FDispose := aDispose;

if not Assigned(aHashFunc) then

htlError(tdeHashTblNoHashFunc, 'Create');

FHashFunc := aHashFunc;

FTable := TtdRecordList.Create(sizeof(THashSlot));

FTable.Name := ClassName + 1 : hash table1;

FTable.Count := TDGetClosestPrime(aTableSize);

end;

destructor TtdHashTableLinear.Destroy;

begin

if (FTable <> nil) then begin

Clear;

FTable.Destroy;

end;

inherited Destroy;

end;

Конструктор обеспечивает присвоение функции хеширования. Применение хеш-таблицы без функции хеширования бессмысленно. Экземпляр FTable определяется таким образом, чтобы количество содержащихся в нем элементов было равно простому числу, ближайшему к значению, переданному в переменной TableSize. Деструктор обеспечивает освобождение хеш-таблицы (возможно, вначале придется удалить содержащиеся в ней элементы) перед освобождением экземпляра FTable.

Рассмотрим вставку нового элемента. Метод Insert принимает ключ элемента и сам элемент и добавляет их в хеш-таблицу.

Листинг 7.5. Вставка элемента в хеш-таблицу с линейным зондированием

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

var

Slot : pointer;

begin

if (htlIndexOf (aKey, Slot) <> -1) then

htlError(tdeHashTblKeyExists, 'Insert');

if (Slot = nil) then

htlError(tdeHashTbllsFull, 'Insert');

with PHashSlot (Slot)^ do

begin

{$IFDEF Delphi1}

hsKey := NewStr(aKey);

{$ELSE}

hsKey := aKey;

{$ENDIF}

hsItem := aItem;

hslnuse := true;

end;

inc(FCount);

{увеличить таблицу, если она заполнена более чем на 2/3}

if ((FCount * 3) > (FTable.Count * 2)) then

htlGrowTable;

end;

В данном случае защищенные вспомогательные методы выполняют несколько задач. Первый из них - htlIndexOf. Этот метод предпринимает попытку найти ключ в хеш-таблице и в случае успеха возвращает его индекс и указатель на ячейку, которая содержит элемент (метод Insert воспринимает это как ошибку). Если ключ не был найден, метод возвращает значение -1, на этот раз с указателем на ячейку, в которую можно поместить элемент, что, собственно, и выполняется на следующем шаге. (Существует также третья возможность: метод htlIndexOf возвращает значение -1 для индекса и ничего для ячейки;