Поиск элемента по его ключу выполняется методом Find уверен, что после ознакомления с методами Insert и Delete читатели догадываются, что это - всего лишь вызовы пресловутого метода htlIndexOf.
Листинг 7.8. Поиск элемента в хеш-таблице по ключу
function TtdHashTableLinear.Find(const aKey : string; var aItem : pointer): boolean;
var
Slot : pointer;
begin
if (htlIndexOf (aKey, Slot)o-1) then begin
Result := true;
aItem := PHashSlot(Slot)^.hsItem;
end
else begin
Result := false;
aItem := nil;
end;
end;
Как видите, все достаточно просто.
Методы, которые выполняют увеличение хеш-таблицы, используют еще один, метод - htlAlterTableSize. Код обоих методов выглядит следующим образом.
Листинг 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
