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

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