Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Листинг 7.9. Изменение размера хеш-таблицы с линейным зондированием
procedure TtdHashTableLinear.htlAlterTableSize(aNewTableSize : integer);
var
Inx : integer;
OldTable : TtdRecordList;
begin
{сохранить старую таблицу}
OldTable := FTable;
{распределить память под новую таблицу}
FTable := TtdRecordList.Create(sizeof(THashSlot));
try
FTable.Count := aNewTableSize;
{считывать старую таблицу и перенести ключи и элементы}
FCount := 0;
for Inx := 0 to pred(OldTable.Count) do
with PHashSlot (OldTable [ Inx])^ do
if (hsState = hssInUse) then begin
{$IFDEF Delphi1}
Insert(hsKey^, hsItem);
DisposeStr(hsKey);
{$ELSE}
Insert(hsKey, hsItem);
hsKey := '';
{$ENDIF}
end;
except
{при
FTable.Free;
FTable :=0ldTable;
raise;
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 увеличивается, гарантируя циклический возврат и повторное выполнение цикла.
Обратите внимание, что проверка того, была ли посещена каждая отдельная ячейка, является несколько излишней. Хеш-таблица является динамической, и значение коэффициента загрузки будет поддерживаться между одной шестой и одной третей. То есть, в таблице всегда должны существовать ячейки, которые не используются. Однако, выполнение проверки - хорошая практика программирования, которая учитывает возможность изменения хеш-таблицы в будущем и того, что какой-либо код может привести к возникновению подобной ситуации.