Теперь пора рассмотреть какой-нибудь код. Общедоступный интерфейс к классу TtdHashTableChained в общих чертах не отличается от такового для класса TtdHashTableLinear. Различия между двумя этими классами проявляются в разделах private и protected.

Листинг 7.11. Класс TtdHashTableChained

type TtdHashChainUsage = ( {Применение цепочек хеш-таблицы-) hcuFirst, {..вставка в начало) hcuLast) ; {..вставка в конец) type TtdHashTableChained = class

{хеш-таблица, в которой для разрешения конфликтов используется связывание)
private FChainUsage : TtdHashChainUsage;
FCount : integer;
FDispose : TtdDisposeProc;
FHashFunc : TtdHashFunc;
FName : TtdNameString;
FTable : TList;
FNodeMgr : TtdNodeManager;
FMaxLoadFactor : integer;
protected
procedure htcSetMaxLoadFactor(aMLF : integer);
procedure htcAllocHeads(aTable : TList);
procedure htcAlterTableSize(aNewTableSize : integer);
procedure htcError(aErrorCode : integers-const aMethodName : TtdNameString);
function htcFindPrim(const aKey : string;
var alnx : integer;
var aParent : pointer) : boolean;
procedure htcFreeHeads (aTable : TList) ; procedure htcGrowTable;
public

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

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

read FCount; property MaxLoadFactor : integer

read FMaxLoadFactor write htcSetMaxLoadFactor; property Name : TtdNameString

read FName write FName; property ChainUsage : TtdHashChainUsage

read FChainUsage write FChainUsage;
end;

Мы объявили небольшой перечислимый тип TtdHashChainUsage для указания того, выполняется ли вставка элементов в начало или в конец связного списка. Класс содержит свойство ChainUsage, которое указывает, какой метод следует использовать.

ттшттштттттттттштшттшттшттт^

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

Использование свойства MaxLoadFactor может оказаться затруднительным. Какое значение оно должно иметь? Вспомните, что его можно считать равным средней длине связных списков, хранящихся в каждой из ячеек. Если придерживаться правила, применяемого для линейного зондирования, в соответствии с которым коэффициент загрузки выбирается так, чтобы для обнаружения промаха при поиске требовалось в среднем пять зондирований, то значение MaxLoadFactor должно быть равно пяти.

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

Если внимательно присмотреться к коду, то мы увидим, что в нем используется хорошо известный нам класс TtdNodeManager (как именно - будет показано вскоре). Конструктор Create, как и TList, будет выделять один экземпляр этого класса. Деструктор Destroy будет освобождать оба эти экземпляра.

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

constructor TtdHashTableChained.Create(aTableSize : integer;
aHashFunc : TtdHashFunc;
aDispose : TtdDisposeProc) ;
begin inherited Create;
FDispose := aDispose;
if not Assigned (aHashFunc) then
htcError(tdeHashTblNoHashFunc, 1 Create1);
FHashFunc := aHashFunc;
FTable := TList.Create;
FTable.Count := TDGetClosestPrime(aTableSize);
FNodeMgr : = TtdNodeManager.Create(sizeof(THashedltem)) ; htcAllocHeads(FTable);
FMaxLoadFactor : = 5 ;
end;
destructor TtdHashTableChained. Destroy;
begin
if (FTableonil) then begin Clear;
htcFreeHeads(FTable);
FTable.Destroy;
end;
FNodeMgr.Free;
inherited Destroy;
end;

Созданный нами диспетчер узлов предназначен для работы с узлами THashltem. Он определяет структуру записей этого типа. Эта структура во многом аналогична структуре записей класса TtdHashLinear, за исключением того, что требуется связное поле и не требуется поле "используется" (все элементы в связном списке "используются" по определению; удаленные из хеш-таблицы элементы в связном списке отсутствуют).

type PHashedltem = ATHashedItem;
THashedltem = packed record
hiNext : PHashedltem;
hiItem : pointer; {$IFDEF Delphil} hiKey : PString; {$ELSE}
hiKey : string; {$ENDIF} end;

Конструктор вызывает метод htcAllocHeads для создания первоначально пустой хеш-таблицы. Вот что должно при этом происходить. Каждая ячейка в хеш-таблице будет содержать указатель на односвязный список (поскольку каждая ячейка содержит только указатель, для хранения хеш-таблицы можно воспользоваться TList). Для упрощения вставки и удаления элементов мы выделяем заглавные узлы для каждого возможного связного списка, как было описано в главе 3. Естественно, деструктор должен освобождать эти заглавные узлы - данная операция выполняется при помощи метода htcFreeHeads.

Листинг 7.13. Выделение и освобождение заглавных узлов связных списков

procedure TtdHashTableChained.htcAllocHeads(aTable : TList); var
Inx : integer;
begin
for Inx := 0 to pred(aTable.Count) do aTable.ListA[Inx] := FNodeMgr.AllоcNodeClear;
end;
procedure TtdHashTableChained.htcFreeHeads(aTable : TList); var
Inx : integer;
begin
for Inx := 0 to pred(aTable.Count) do FNodeMgr.FreeNode(aTable.ListA[Inx]);
end;

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

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

procedure TtdHashTableChained. Insert (const aKey : string;
altem : pointer );
var
Inx : integer;
Parent : pointer;
NewNode : PHashedltem;
begin
if htcFindPrim(aKey, Inx, Parent) then htcError(tdeHashTblKeyExists, 1 Insert1);
NewNode : = FNodeMgr.AllocNodeClear; {$IFDEF Delphi 1} NewNodeA.hiKey := NewStr(aKey); {$ELSE)
NewNodeA.hiKey := aKey; {$ENDIF)
NewNode A .hi I tern := altem;
NewNodeA.hiNext : = PHashedltem(Parent)A.hiNext;
PHashedltem(Parent)A.hiNext : = NewNode;
inc(FCount);
{увеличить таблицу, если значение коэффициента загрузки превышает максимальное значение) if (FCount > (FMaxLoadFactor * FTable. Count)) then htcGrowTable;
end;

Прежде всего, мы вызываем подпрограмму htcFindPrim. Она выполняет такую же операцию, как и htlllndexOf, при использовании линейного зондирования: предпринимает попытку найти ключ й возвращает индекс ячейки, в которой он был найден. Однако этот метод создан с учетом применения связных списков. Если поиск ключа выполняется успешно, метод возвращает значение "истина", а также индекс ячейки хеш-таблицы и указатель на родительский узел элемента в связном списке. Почему родительский? Что ж, если вспомнить сказанное в главе 3, основные операции с односвязным списком предполагают вставку и удаление узла за данным узлом. Следовательно, целесообразнее, чтобы метод htcFindPrim возвращал родительский узел узла, в который выполняется вставка.

Если ключ не найден, метод htcFindPrlm возвращает значение "ложь" и индекс ячейки, в которую нужно вставить элемент, и родительский узел, за которым его можно успешно вставить.

Итак, вернемся к методу Insert. ЕстестЁенно, если ключ был найден, метод генерирует ошибку. В противном случае мы выделяем новый узел, устанавливаем элемент и ключ, а затем вставляем элемент непосредственно за данным узлом.

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

Как легко догадаться, метод Delete работает аналогично.

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

procedure TtdHashTableChained. Delete (const aKey : string); var
Inx : integer;
Parent : pointer;
Temp : PHashedltem;
begin
{поиск ключа}
if not htcFindPrim(aKey, Inx, Parent) then
htcError(tdeHashTblKeyNotFound, 'Delete1); {удалить элемент и ключ из данного узла) Temp : = PHashedltem(Parent)А.hiNext;
if Assigned(FDispose) then
FDispose(TempA.hiItem); {$IFDEF Delphi 1} Disposestr(TempA.hiKey); {$ELSE}
TempA.hiKey : = 11 ; {$ENDIF}
{разорвать связь с узлом и освободить его} PHashedltem(Parent)А.hiNext : = TempA.hiNext;
FNodeMgr.FreeNode(Temp);
dec(FCount);
end;

Мы предпринимаем попытку найти ключ (если он не найден, метод генерирует ошибку), а затем избавляемся от содержимого возвращенного элемента и удаляем его из связного списка. Обратите внимание на простоту кода обеих методов, Insert и Delete, обусловленную наличием заглавного узла в каждом связном списке. Не нужно беспокоиться о том, является ли родительский узел нулевым. Метод htcFindPrlm всегда будет возвращать допустимый родительский узел.

Метод Clear очень похож на метод Delete, за исключением того, что мы просто стандартным образом удаляем все узлы из каждого связного списка (естественно, за исключением заглавных узлов).

Листинг 7.16. Очистка хеш-таблицы TtdHashTableChained

procedure TtdHashTableChained.Clear;
var
Inx : integer;
Temp, Walker : PHashedl tern;
begin
for Inx : = 0 to pred(FTable.Count) do begin Walker := PHashedltern(FTable.ListA[Inx])A.hiNext;
while (Walkeronil) do begin if As signed (FDispose) then
FDispose(Walker*.hiltem); {$IFDEF Delphi 1} DisposeStr(WalkerA.hiKey); {$ELSE)
WalkerA.hiKey := w; {$ENDIF) Temp := Walker;
Walker : = WalkerA.hiNext;
FNodeMgr.FreeNode(Temp);
end;
PHashedltern(FTable.ListA[Inx])A.hiNext := nil;
end;
FCount := 0;
end;

Метод Find прост, поскольку основная часть работы выполняется вездесущим методом htcFindPrim.

Листинг 7.17. Поиск элемента в хеш-таблице со связыванием

function TtdHashTableChained. Find (const aKey : string;
var altern : pointer) : boolean;
var
Inx : integer;
Parent : pointer;
begin
if htcFindPrim(aKey, Inx, Parent) then begin Result := true;
altem := PHashedl tern (Parent)A .hiNextA .hi I tern;
end
else begin
Result := false;
altem := nil;
end;
end;

Единственная небольшая сложность состоит в том, что метод htcFindPrim возвращает родительский узел действительно интересующего нас узла.

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

Листинг 7.18. Увеличение хеш-таблицы со связыванием

procedure TtdHashTableChained. htcGrowTable;
begin
{увеличить размер таблицы примерно в два раза по сравнению с предыдущим размером}
htcAlterTableSize(TDGetClosestPrime(succ(FTable.Count * 2)));
end;

procedure TtdHashTableChained.htcAlterTableSize(aNewTableSize : integer); var Inx : integer; OldTable : TList; Walker, Temp : PHashedltem; begin {сохранить старую таблицу} OldTable : = FTable; {распределить новую таблицу} FTable := TList.Create; try

FTable.Count : = aNewTableSize;
htcAllocHeads(FTable);
{считывать старую таблицу и перенести ключи и элементы в новую таблицу посредством их вставки} FCount := 0;
for Inx : = 0 to pred(OldTable.Count) do begin Walker : = PHashedltem(OldTable.ListA[Inx])A.hiNext;
while (Walkeronil) do begin
{$IFDEF Delphi 1}
Insert (WalkerA .hiKeyA, WalkerA .hiltem) ; {$ELSE}
Insert(WalkerA.hiKey, WalkerA.hiltem); {$ENDIF}
Walker : = WalkerA.hiNext;
end;
end;
except
{предпринять попытку очистки и сохранения хеш-таблицы в непротиворечивом состоянии в случае возникновения исключения} Clear;
htcFreeHeads(FTable);
FTable.Free;
FTable := OldTable;
raise;
end;
{шелерь новая таблица полностью заполнена всеми элементами и их ключами, поэтому необходимо уничтожить старую таблицу и ее связные списки} for Inx := 0 to pred(01dTable.Count) do begin Walker := PHashedltem(OldTable.ListA[Inx])Л.hiNext;
while (Walkeronil) do begin {$IFDEF Delphi 1} DisposeStr(WalkerA.hiKey); {$ELSE}
WalkerA.hiKey := ' »; {$ENDIF} Temp := Walker;
Walker := WalkerA.hiNext;
FNodeMgr.FreeNode(Temp);
end;
PHashedltern(OldTable.ListA[Inx])A.hiNext := nib-end;
htcFreeHeads(OldTable);
OldTable.Free;
end;

В этом классе реализация метода htcAlterTableSize оказывается значительно сложнее, нежели в классе с линейным зондированием. Чтобы обеспечить коррект ное восстановление после возникновения исключительных состояний, возникаю щих при увеличении таблицы, увеличение выполняется в два этапа. Вначале эле менты и их ключи копируются в новую таблицу большего размера. Затем, сраз; по завершении первого этапа, мы избавляемся от узлов в меньшей таблице.

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

Листинг 7.19. Примитив для поиска элемента в хеш-таблице со связыванием

function TtdHashTableChained. htcFindPrim( const aKey : string;
var alnx : integer;
var aParent : pointer) : boolean;
var
Inx : integer;
Head, Walker, Parent : PHashedltern;
begin
{вычислить хеш-значение для строки} Inx := FHashFunc(aKey, FTable.Count);
{предположить, что связный список существует в Inx-ой ячейке}
Head := PHashedltem(FTable.ListA[Inx]);
{начать просмотр связного списка с целью поиска ключа}
Parent := Head;
Walker := HeadA.hiNext;
while (Walkeronil) do begin {$lFDEFDelphil}
if (WalkerA.hiKeyA = aKey) then begin {$ELSE)
if (Walker A.hiKey = aKey) then begin {$ENDIF}
if (ChainUsage «
hcuFirst) and (Parent Head) then begin
ParentA.hiNext : = WalkerA.hiNext;
WalkerA.hiNext : - HeadA.hiNext;
HeadA.hiNext : = Walker;
Parent := Head;
end;
alnx := Inx;
aParent :== Parents-Result :»
true; Exit;
end.-Parent := Walkers-Walker := WalkerA.hiNext;
end;
{достижение этой точки свидетельствует о том, что ключ не найден) alnx := Inx;

if ChainUsage = hcuLast then aParent := Parent else aParent ^Heads-Result := false; ends-Работа метода начинается с хеширования переданного ему ключа. В результате мы получаем индекс ячейки, в которой найден заголовок связного списка. Мы перемещаемся вниз по связному списку до тех пор, пока не найдем искомый элемент или не встретим указатель nil, обозначающий конец списка. В ходе этого мы поддерживаем родительскую переменную, поскольку вызывающему методу нужно вернуть этот узел, а не указатель на узел элемента.

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

Если ключ был найден и значением свойства ChainUsage является hcuFirst, необходимо воспользоваться методологией "перемещения в начало" и переместить найденный элемент в первую позицию связного списка. Конечно, в случае использования односвязного списка эта операция проста и эффективна. И, наконец, мы возвращаем родительский узел и индекс ячейки.

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

Преимущества и недостатки связывания || Оглавление || Разрешение конфликтов посредством группирования


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



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

  • Июнь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс