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

Второе соглашение состоит в том, что хотя класс будет допускать использование любой функции хеширования, функция должна иметь тип 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 для индекса и ничего для ячейки;

это считается признаком того, что таблица заполнена.) В конце подпрограммы выполняется проверка того, не заполнена ли хеш-таблица более чем на две трети, что, как говорилось ранее, служит хорошим показателем необходимости расширения хеш-таблицы с целью снижения коэффициента загрузки (новая расширенная хеш-таблица должна быть заполнена примерно на одну треть). Метод htlGrowTable выполняет это.

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

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

procedure TtdHashTableLinear.Delete(const aKey : string);

var

Inx : integer;

ItemSlot : pointer;

Slot : PHashSlot;

Key : string;

Item : pointer;

begin

{поиск ключа}

Inx := htlIndexOf(aKey, ItemSlot);

if (Inx = -1) then

htlError(tdeHashTblKeyNotFound, 'Delete');

{удалить элемент и его ключ из данной ячейки}

with PHashSlot (ItemSlot)^ do

begin

if Assigned(FDispose) then

FDispose(hsItem);

{$IFDEF Delphi1}

DisposeStr(hsKey);

{$ELSE}

hsKey := '';

{$ENDIF}

hsInUse := false;

end;

dec(FCount);

{повторно вставить все последующие элементы, предшествующие пустой ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

Slot := PHashSlot(FTable[Inx]);

while Slot^.hsInUse do

begin

{сохранить элемент и ключ; удалить ключ из ячейки}

Item := Slot^.hsItem;

{$IFDEF Delphi1}

Key := Slot^.hsKey^;

DisposeStr(Slot^.hsKey);

{$ELSE}

Key := Slot^.hsKey;

Slot^.hsKey := ''

{$ENDIF}

{пометить ячейку как пустую}

Slot^.hsInUse := false;

dec(FCount);

{повторно вставить элемент и его ключ}

Insert(Key, Item);

{перейти к следующей ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

Slot := PHashSlot(FTable[Inx]);

end;

end;

Как и в предыдущем листинге, мы вызываем метод htlIndexOf, хотя на этот раз ошибка генерируется, если ключ не был найден. В случае обнаружения ключа метод возвращает указатель на ячейку, что позволяет избавиться от элемента (если это необходимо) и ключа. Состояние ячейки определяется как "не используется".

Теперь мы выполняем повторную вставку всех элементов, которые следуют за удаленным и находятся в одном с ним кластере. Из-за необходимости обрабатывать строки ключей в посещаемых ячейках описанная процедура кажется несколько запутанной. Во избежание утечек памяти, необходимо обеспечить освобождение строк ключей. Метод Insert будет перераспределять строки, независимо от выполняемых нами действий.

Метод Clear очень похож на метод Delete. Он используется для удаления всех элементов из хеш-таблицы.

Листинг 7.7. Опустошение хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.Clear;

var

Inx : integer;

begin

for Inx := 0 to pred(FTable.Count) do

begin

with PHashSlot (FTable [Inx])^ do

begin

if hsInUse then begin

if Assigned(FDispose) then

FDispose(hsItem);

{$IFDEF Delphi1}

DisposeStr(hsKey);

{$ELSE}

hsKey := '';

{$ENDIF}

end;

hsInUse := false;

end;

end;

FCount := 0;

end;

Поскольку мы избавляемся от всех элементов в хеш-таблице, состояние всех ячеек можно установить (как только мы избавились от ключей и элементов в тех ячейках, которые используются) как "не используется".

Поиск элемента по его ключу выполняется методом Find уверен, что после ознакомления с методами Insert и Delete читатели догадываются, что это - всего лишь вызовы пресловутого метода htlIndexOf.

Листинг 7.8. Поиск элемента в хеш-таблице по ключу

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

var

Slot : pointer;

begin

if (htlIndexOf (aKey, Slot)o-1) then begin

Result := true;

aItem := PHashSlot(Slot)^.hsItem;

end

else begin

Result := false;

aItem := nil;

end;

end;

Как видите, все достаточно просто.

Методы, которые выполняют увеличение хеш-таблицы, используют еще один, метод - htlAlterTableSize. Код обоих методов выглядит следующим образом.

Листинг 7.9. Изменение размера хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.htlAlterTableSize(aNewTableSize : integer);

var

Inx : integer;

OldTable : TtdRecordList;

begin

{сохранить старую таблицу}

OldTable := FTable;

{распределить память под новую таблицу}

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

try

FTable.Count := aNewTableSize;

{считывать старую таблицу и перенести ключи и элементы}

FCount := 0;

for Inx := 0 to pred(OldTable.Count) do

with PHashSlot (OldTable [ Inx])^ do

if (hsState = hssInUse) then begin

{$IFDEF Delphi1}

Insert(hsKey^, hsItem);

DisposeStr(hsKey);

{$ELSE}

Insert(hsKey, hsItem);

hsKey := '';

{$ENDIF}

end;

except

{при возникновении исключения попытаться очистить хеш-таблицу и оставить ее в непротиворечивом состоянии}

FTable.Free;

FTable :=0ldTable;

raise;

end;

{и, наконец, освободить старую таблицу}

OldTable.Free;

end;

procedure TtdHashTableLinear.htlGrowTable;

begin

{увеличить размер таблицы приблизительно в два раза по сравнению с предыдущим}

htlAlterTableSize(GetClosestPrime(suce(FTable.Count * 2)));