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

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

Теперь пора разобраться с последним фрагментом головоломки: рассмотреть "закулисный" метод htlIndexOf - примитив, используемый методами Insert, Delete и Find.

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

function TtdHashTableLinear.htlIndexOf(const aKey : string; var aSlot : pointer): integer;

var

Inx : integer;

CurSlot : PHashSlot;

FirstInx : integer;

begin

{вычислить хеш-значение строки, запомнить его, чтобы можно было установить, когда будет (если вообще будет) выполнен просмотр всех записей таблицы}

Inx := FHashFunc(aKey, FTable.Count);

FirstInx := Inx;

{выполнить без каких-либо ограничений — при необходимости, выход из цикла можно будет осуществить всегда}

while true do

begin {для текущей ячейки}

CurSlot := PHashSlot(FTable[Inx]);

with CurSlot^ do

begin

if not hsInUse then begin

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

aSlot := CurSlot;

Result := -1;

Exit;

end

else begin

{ ячейка "используется"; необходимо проверить, совпадает ли она с искомым ключом. Если да, то необходимо осуществить выход, возвращая индекс и ячейку}

{$IFDEF Delphi1}

if (hsKey^ = aKey) then begin

{$ELSE}

if (hsKey = aKey) then begin

{$ENDIF}

aSlot := CurSlot;

Result := Inx;

Exit;

end;

end;

end;

{на этот раз ключ или пустая ячейка не были найдены, поэтому необходимо увеличить значение индекса (при необходимости выполнив циклический возврат) и осуществить выход в случае возврата к начальной ячейке}

inc(Inx);

if (Inx = FTable.Count) then

Inx := 0;

if (Inx = First Inx) then begin

aSlot :=nil;

{это сигнализирует о том, что таблица заполнена}

Result := -1;

Exit;

end;

end;

{бесконечный цикл}

end;

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

Метод определяет указатель на начальную ячейку. Мы просматриваем ячейку и выполняем различные операции, зависящие от состояния ячейки. Первый случай - когда ячейка пуста. Достижение этой точки означает, что ключ не был найден, поэтому метод возвращает указатель именно на эту ячейку. Естественно, в этом случае возвращаемое значение функции равно -1, что означает "ключ не найден".

Второй случай - когда ячейка используется. Для выяснения того, совпадают ли ключи, мы сравниваем ключ, хранящийся в ячейке, с ключом, переданным методу (обратите внимание, что мы выполняем поиск точного совпадения, т.е. сравнение с учетом регистра; если хотите выполнить сравнение без учета регистра, нужно использовать ключи, преобразованные в прописные буквы). Совпадение ключей свидетельствует об обнаружении искомого элемента. Поэтому программа возвращает указатель ячейки и устанавливает результат функции равным индексу ячейки.

Если в результате выполнения описанных операций сравнения выход из метода не был осуществлен, необходимо проверить следующую ячейку. Поэтому значение индекса Inx увеличивается, гарантируя циклический возврат и повторное выполнение цикла.

Обратите внимание, что проверка того, была ли посещена каждая отдельная ячейка, является несколько излишней. Хеш-таблица является динамической, и значение коэффициента загрузки будет поддерживаться между одной шестой и одной третей. То есть, в таблице всегда должны существовать ячейки, которые не используются. Однако, выполнение проверки - хорошая практика программирования, которая учитывает возможность изменения хеш-таблицы в будущем и того, что какой-либо код может привести к возникновению подобной ситуации.

Полный вариант кода класса TtdHashTableLinear можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshLnP.pas.

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