В листинге 7.3 приведен код интерфейса для хеш-таблицы с линейным зондированием (полный исходный код этого класса можно найти на \¥еЬ-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл ТШзЬЪпР.раз). По поводу этой реализации следует привести ряд замечаний. Во-первых, мы принимаем соглашение, что ключом элемента является строка, отдельная от самого элемента. Это существенно упрощает как понимание кода, так и разработку и использование хеш-таблицы. В подавляющем большинстве случаев ключи все равно будут строками, а преобразование других типов данных в строки обычно не представляет особой сложности.

Второе соглашение состоит в том, что хотя класс будет допускать использование любой функции хеширования, функция должна иметь тип тесШазЬРшс.

type TtdHashFunc = function ( const aKey : string;
aTableSize : integer) : integer;

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

Листинг 7.3. Хеш-таблица линейного зондирования TtdHashTableLinear

type TtdHashTableLinear = class
{хеш-таблица, в которой для разрешения конфликтов используется линейное зондирование} private FCount : integer;
FDispose: TtdDisposeProc;
FHashFunc : TtdHashFunc;
FName : TtdNameString;
FTable : TtdRecordList;
protected
procedure htlAlterTableSize(aNewTableSize : integer);
procedure htlError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure htlGrowTable;
function htllndexOf ( const aKey : string;
var aSlot : pointer) : integer;
public

constructor Create (aTableSize : integer;
aHashFunc : TtdHashFunc;
aDispose : TtdDisposeProc);
destructor Destroy;
override; procedure Delete (const aKey : string);
procedure Empty;
function Find (const aKey : string;

var altem : pointer) : boolean; procedure Insert (const aKey : string; altem : pointer); property Count : integer

read FCount; property Name : TtdNameString

read FName write FName;
end;

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

Как видите, для хранения самой хеш-таблицы будет использоваться экземпляр TtdRecordList. Интерфейс класса не дает никакого представления о структуре элементов хеш-таблицы, т.е. ячеек. Эта информация скрыта в разделе реализации модуля.

type PHashSlot = ATHashSlot;
THashSlot = packed record

{$IFDEF Delphi 1}
hsKey : PString;

{$ELSE]

hsKey : string; {$ENDIF)
hsltem : pointer;
hsInUse: boolean;
end;

Ячейка представляет собой запись с тремя полями: ключом, собственно элементом и состоянием ячейки (независимо от того, используется оно или нет). В Delphi 1 ключ - это указатель строки, в то время как в последующих версиях он является длинной строкой (которая, естественно, представляет собой замаскированный указатель).

Конструктор Create выделяет экземпляр списка записей, а деструктор Destroy освобождает его.

Листинг 7.4. Конструктор и деструктор класса TtdHashTableLinear

constructor TtdHashTableLinear.Create ( aTableSize : integer;
aHashFunc : TtdHashFunc;
aDispose : TtdDisposeProc ) ;
begin
inherited Create;
FDispose := aDispose;
if not Assigned (aHashFunc) then
htlError(tdeHashTblNoHashFunc, 1 Create1);
FHashFunc := aHashFunc;
FTable := TtdRecordList.Create(sizeof(THashSlot));
FTable.Name := ClassName + 1 : hash table1 ; FTable.Count : = TDGetClosestPrime(aTableSize);
end;
destructor TtdHashTableLinear. Destroy;
begin
if (FTableonil) then begin Clear;
FTable.Destroy;
end;
inherited Destroy;
end;

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

Рассмотрим вставку нового элемента. Метод Insert принимает ключ элемента и сам элемент и добавляет их в хеш-таблицу.

Листинг 7.5. Вставка элемента в хеш-таблицу с линейным зондированием

procedure TtdHashTableLinear. Insert (const aKey : string;
altem : pointer);
var
Slot : pointer;
begin
if (htllndexOf (aKey, Slot)o-1) then
htlError(tdeHashTblKeyExists, 'Insert1);
if (Slot = nil) then
htlError(tdeHashTbllsFull, 'Insert'); with PHashSlot (Slot)л do begin
{$IFDEF Delphi 1}
hsKey := NewStr(aKey);
{$ELSE)
hsKey := aKey; {$ENDIF} hsltem := altem;
hslnüse := true;
end;
inc(FCount);
{увеличить таблицу, если она заполнена более чем на 2/3} if ((FCount * 3) > (FTable.Count * 2)) then htlGrowTable;
end;

В данном случае защищенные вспомогательные методы выполняют несколько задач. Первый из них - htllndexOf. Этот метод предпринимает попытку найти ключ в хеш-таблице и в случае успеха возвращает его индекс и указатель на ячейку, которая содержит элемент (метод Insert воспринимает это как ошибку). Если ключ не был найден, метод возвращает значение -1, на этот раз с указателем на ячейку, в которую можно поместить элемент, что, собственно, и выполняется на следующем шаге. (Существует также третья возможность: метод htllndexOf возвращает значение -1 для индекса и ничего для ячейки; это считается признаком того, что таблица заполнена.) В конце подпрограммы выполняется проверка того, не заполнена ли хеш-таблица более чем на две трети, что, как говорилось ранее, служит хорошим показателем необходимости расширения хеш-таблицы с целью снижения коэффициента загрузки (новая расширенная хеш-таблица должна быть заполнена примерно на одну треть). Метод htlGrowTable выполняет это.

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

Листинг 7.6. Удаление элемента из хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.Delete(const aKey : string); var
Inx : integer;
ItemSlot : pointer;
Slot : PHashSlot;
Key : string;
Item : pointer;
begin
{поиск ключа}
Inx := htllndexOf(aKey, ItemSlot);
if (Inx = -1) then
htlError(tdeHashTblKeyNotFound, 'Delete'); {удалить элемент и его ключ из данной ячейки} with PHashSlot (ItemSlot)А do begin
if Assigned(FDispose) then FDispose(hsltem);
{$IFDEF Delphil)
Disposestr(hsKey);
{$ELSE}
hsKey : = 1 1 ;
{$ENDIF}
hsInUse := false;
end;
dec(FCount);
{повторно вставить все последующие элементы, предшествующие пустой ячейке} inc(Inx);
if (Inx = FTable.Count) then
Inx := 0; Slot := PHashSlot(FTable[Inx]); while SlotA .hsInUse do begin
{сохранить элемент и ключ; удалить ключ из ячейки}, Item := SlotA.hsltem;
{$IFDEF Delphil}
Key := SlotA.hsKeyA;
DisposeStr(SlotA.hsKey);
{$ELSE}
Key := SlotA.hsKey;
SlotA.hsKey := {$ENDIF}
{пометить ячейку как пустую} SlotA.hsInUse := false;
dec(FCount);
{повторно вставить элемент и его ключ) Insert(Key, Item); {перейти к следующей ячейке} inc(Inx);
if (Inx = FTable.Count) then
Inx := 0; Slot := PHashSlot(FTable[Inx]);
end;
end;

Как и в предыдущем листинге, мы вызываем метод htllndexOf, хотя на этот раз ошибка генерируется, если ключ не был найден. В случае обнаружения ключа метод возвращает указатель на ячейку, что позволяет избавиться от элемента (если это необходимо) и ключа. Состояние ячейки определяется как "не используется".

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

Метод Clear очень похож на метод Delete. Он используется для удаления всех элементов из хеш-таблицы.

Листинг 7.7. Опустошение хеш-таблицы с линейным зондированием

procedure TtdHashTableLinear.Clear;
var
Inx : integer;
begin
for Inx : = 0 to pred(FTable.Count) do begin with PHashSlot (FTable [Inx])л do begin if hsInUse then begin if Assigned(FDispose) then
FDispose(hsltem); {$IFDEF Delphi 1} DisposeStr(hsKey); {$ELSE} hsKey : = " " ; {$ENDIF} end;
hsInUse := false;
end;
end;
FCount := 0;
end;

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

Поиск элемента по его ключу выполняется методом Find Уверен, что после ознакомления с методами insert и Delete читатели догадываются, что это - всего лишь вызовы пресловутого метода htllndexOf.

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

function TtdHashTableLinear. Find ( const aKey : string;
var altem : pointer) : boolean;
var
Slot : pointer;
begin
if (htllndexOf (aKey, Slot)o-1) then begin Result : = true;
altem := PHashSlot(Slot)A.hsltem;
end
else begin
Result := false;
altem := 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 Delphi 1} Insert(hsKeyA, hsltem);
DisposeStr(hsKey); {$ELSE)
Insert(hsKey, hsltem);
hsKey := 1 ' {$ENDIF) end;
except
{при возникновении исключения попытаться очистить хеш-таблицу и оставить ее в непротиворечивом состоянии) FTable.Free;
FTable :=01dTable;
raise;
end;
{и, наконец, освободить старую таблицу) OldTable. Freer-end;
procedure TtdHashTableLinear. htlGrowTable ; begin
{увеличить размер таблицы приблизительно в два раза по сравнению с предыдущим)
htlAlterTableSize(GetClosestPrime(suce(FTable.Count * 2)));
end;

Метод hltAlterTableSize содержит код выполнения этих операций. Он работает, сохраняя текущую хеш-таблицу (т.е. экземпляр списка записей), распределяя память под новую таблицу и, затем, просматривая все элементы в старой таблице (которые находятся в ячейках, помеченных как "используемые") и вставляя их в новую таблицу. В заключение, метод освобождает старую таблицу. Обратите внимание, что блок Try. .except предпринимает попытку сохранить непротиворечивое состояние хеш-таблицы в случае возникновения исключения. Естественно, при этом предполагается, что в момент вызова метода хеш-таблица находилась в именно таком состоянии.

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

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

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

function TtdHashTableLinear .htllndexOf (const aKey : string;
var aSlot : pointer) : integer;
var
Inx : integer;
CurSlot : PHashSlot;
FirstInx : integer;
begin
{вычислить хеш-значение строки, запомнить его, чтобы можно было установить, когда будет (если вообще будет) выполнен просмотр всех записей таблицы} Inx : = FHashFunc(aKey, FTable.Count);
Firstlnx := 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 Delphi 1}
if (hsKeyA = aKey) then begin
{$ELSE)
if (hsKey = aKey) then begin {$ENDIF)
aSlot := CurSlot;
Result := Inx;
Expend;
end;
end;
{на этот раз ключ или пустая ячейка не были найдены, поэтому необходимо увеличить значение индекса (при необходимости выполнив циклический возврат) и осуществить выход в случае возврата к начальной ячейке}
inc(Inx);
if (Inx = FTable.Count) then
Inx := 0; if (Inx = First Inx) then begin
aSlot :=nil; {это сигнализирует о том, что таблица заполнена}
Result := -1;
Expend;
end; {бесконечный цикл} end;

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

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

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

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

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

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

Удаление элементов из хеш-таблицы с линейным зондированием || Оглавление || Другие схемы открытой адресации


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



Новости за месяц

  • Апрель
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс