Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в 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 для индекса и ничего для ячейки;

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