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}