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

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

{$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.

Другие схемы открытой адресации

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

Квадратичное зондирование

Первая из таких схем - квадратичное зондирование (quadratic probing). При использовании этого алгоритма контроль и предотвращение создания кластеров осуществляется путем проверки не следующей по порядку ячейки, а ячеек, которые расположены все дальше от исходной. Если первое зондирование оказывается безрезультатным, мы проверяем следующую ячейку. В случае неудачи этой попытки мы проверяем ячейку, которая расположена через четыре ячейки. Если и эта попытка неудачна, мы проверяем ячейку, расположенную через девять ячеек - и т.д., причем последующие зондирования выполняются для ячеек, расположенных через 16, 25, 36 и так далее ячеек. Этот алгоритм позволяет предотвратить образование кластеров, которые могут появляться в результате применения линейного зондирования, однако он может приводить и к ряду нежелательных проблем. Во-первых, если для многих ключей хеширование генерирует один и тот же индекс, все их последовательности зондирования должны будут выполняться вдоль одного и того же пути. В результате они образуют кластер, но такой, который кажется распределенным по хеш-таблице. Однако вторая проблема значительно серьезнее: квадратичное зондирование не гарантирует посещение всех ячеек. Максимум в чем можно быть уверенным, если размер таблицы равен простому числу, это в том, что квадратичное зондирование обеспечит посещение, по меньшей мере, половины ячеек хеш-таблицы. Таким образом, образом, можно говорить о выполнении задачи-минимум, но не задачи-максимум.