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

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

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

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

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

Класс хеш-таблиц с линейным зондированием

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

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

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 htlIndexOf( 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 aItem : pointer): boolean;

procedure Insert(const aKey : string; aItem : pointer);

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

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

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

type

PHashSlot = ^THashSlot;

THashSlot = packed record

{$IFDEF Delphi1}

hsKey : PString;

{$ELSE}

hsKey : string;

{$ENDIF}

hsItem : pointer;

hsInUse: boolean;

end;