Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
end;
{и, наконец, освободить старую таблицу}
OldTable.Free;
end;
procedure TtdHashTableLinear.htlGrowTable;
begin
{увеличить размер таблицы приблизительно в два раза по сравнению с предыдущим}
htlAlterTableSize(GetClosestPrime(suce(FTable.Count * 2)));
end;
Метод hltAlterTableSize содержит код выполнения этих операций. Он работает, сохраняя текущую хеш-таблицу (т.е. экземпляр списка записей), распределяя память под новую таблицу и, затем, просматривая все элементы в старой таблице (которые находятся в ячейках, помеченных как "используемые") и вставляя их в новую таблицу. В заключение, метод освобождает старую таблицу. Обратите внимание, что блок Try..except предпринимает попытку сохранить непротиворечивое состояние хеш-таблицы в случае возникновения исключения. Естественно, при этом предполагается, что в момент вызова метода хеш-таблица находилась в именно таком состоянии.
Излишне говорить, что расширение хеш-таблицы - довольно-таки трудоемкая операция (которая требует очень большого дополнительного объема свободной памяти - вдвое больше того, который уже был выделен). Всегда желательно приблизительно оценить общее количество строк, которые нужно вставить В хеш-таблицу, и добавить, скажем, еще половину этого количества строк. Результирующее значение можно использовать в качестве расчетного размера хеш-таблицы при ее создании. Такая оценка обеспечит нам определенную свободу действий при использовании хеш-таблицы.
Теперь пора разобраться с последним фрагментом головоломки: рассмотреть "закулисный" метод 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.
Другие схемы открытой адресации
Хотя описанный класс хеш-таблиц был разработан для решения основной проблемы, возникающей при использовании схемы с открытой адресацией линейного зондирования (тенденции к кластеризации занятых ячеек), мы кратко рассмотрим несколько других схем с открытой адресацией.
Квадратичное зондирование
Первая из таких схем - квадратичное зондирование (quadratic probing). При использовании этого алгоритма контроль и предотвращение создания кластеров осуществляется путем проверки не следующей по порядку ячейки, а ячеек, которые расположены все дальше от исходной. Если первое зондирование оказывается безрезультатным, мы проверяем следующую ячейку. В случае неудачи этой попытки мы проверяем ячейку, которая расположена через четыре ячейки. Если и эта попытка неудачна, мы проверяем ячейку, расположенную через девять ячеек - и т.д., причем последующие зондирования выполняются для ячеек, расположенных через 16, 25, 36 и так далее ячеек. Этот алгоритм позволяет предотвратить образование кластеров, которые могут появляться в результате применения линейного зондирования, однако он может приводить и к ряду нежелательных проблем. Во-первых, если для многих ключей хеширование генерирует один и тот же индекс, все их последовательности зондирования должны будут выполняться вдоль одного и того же пути. В результате они образуют кластер, но такой, который кажется распределенным по хеш-таблице. Однако вторая проблема значительно серьезнее: квадратичное зондирование не гарантирует посещение всех ячеек. Максимум в чем можно быть уверенным, если размер таблицы равен простому числу, это в том, что квадратичное зондирование обеспечит посещение, по меньшей мере, половины ячеек хеш-таблицы. Таким образом, образом, можно говорить о выполнении задачи-минимум, но не задачи-максимум.
В этом легко убедиться. Начнем квадратичное зондирование с 0-й ячейки хеш-таблицы, содержащей 11 ячеек, и посмотрим, какие ячейки будут посещены при этом. Последовательность посещений выглядит следующим образом: 0, 1, 5, 3, 8, после чего зондирование снова начинается с ячейки 0. Мы никогда не посещаем ячейки 2, 4, 7, 9. По-моему, одной этой проблемы достаточно, чтобы в любом случае избегать применения квадратичного зондирования, хотя ее можно было бы избегнуть, не позволяя хеш-таблице заполняться более чем на половину.
Псевдослучайное зондирование
Следующая возможность - применение псевдослучайного зондирования (pseudorandom probing). Этот алгоритм требует использования генератора случайных чисел, который можно сбрасывать в определенный момент. Применительно к рассматриваемому алгоритму, из числа рассмотренных в 6 главе генераторов наиболее подошел бы минимальный стандартный генератор случайных чисел, поскольку его состояние однозначно определяется одним характеристическим значением - начальным числом. Алгоритм определяет следующую последовательность действий. Выполните хеширование ключа для получения хеш-значения, но не выполняйте деление по модулю на размер таблицы. Установите начальное значение генератора равным этому хеш-значению. Сгенерируйте первое случайное число с плавающей точкой (в диапазоне от 0 до 1) и умножьте его на размер таблицы для получения целочисленного значения в диапазоне от 0 до размера таблицы минус 1. Эта точка будет точкой первого зондирования. Если ячейка занята, сгенерируйте следующее случайное число, умножьте его на размер таблицы и снова выполните зондирование. Продолжайте выполнять упомянутые действия до тех пор, пока не найдете свободную ячейку. Поскольку при одном и том же заданном начальном значении генератор случайных чисел будет генерировать одни и те же случайные числа в одной и той же последовательности, для одного и того же хеш-значения всегда будет создаваться одна и та же последовательность зондирования.
