Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Рассмотрим вставку нового элемента. Метод 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);
{увеличить
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. Код обоих методов выглядит следующим образом.