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

Бакнелл Джулиан М.

Преимущества и недостатки связывания

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

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

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

Стоит отметить еще ряд обстоятельств. При использовании алгоритма разрешения конфликтов линейного зондирования мы сознательно старались минимизировать количество выполняемых зондирований, расширяя хеш-таблицу, когда ее коэффициент загрузки начинал превышать две третьих. Как следует из результатов анализа, в этой ситуации для успешного поиска должно в среднем требоваться два зондирования, а для безрезультатного - пять. Подумайте, что означает зондирование. По существу, это сравнение ключей. Весь смысл применения хеш-таблицы заключался в уменьшении количества сравнений ключей до одного или двух. В противном случае вполне можно было бы выполнить бинарный поиск в отсортированном массиве строк. Что ж, при использовании связывания для разрешения конфликтов каждый раз, когда мы спускаемся по связному списку, пытаясь найти конкретный ключ, для этого мы используем сравнение. Если прибегнуть к терминологии метода с открытой адресацией, то каждое сравнение можно сравнить с "зондированием". Так сколько же зондирований в среднем требуется для успешного поиска при использовании связывания? Для алгоритма связывания коэффициент загрузки по-прежнему вычисляется как число элементов, деленное на число ячеек (хотя на этот раз оно может иметь значение больше 1.0), и его можно представить средней длиной связных списков, присоединенных к ячейкам хеш-таблицы. Если коэффициент загрузки равен F, то среднее число зондирований для успешного поиска составит F/2. Для безрезультатного поиска среднее число зондирований равно F. (Эти результаты справедливы для несортированных связных списков. Если бы связные списки были отсортированы, значения были бы меньше - исходя из теории, оба значения нужно разделить на log(_2_)(F))

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

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

Класс связных хеш-таблиц

Теперь пора рассмотреть какой-нибудь код. Общедоступный интерфейс к классу 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 : integer;

const aMethodName : TtdNameString);

function htcFindPrim(const aKey : string;

var aInx : 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 aItem : pointer): boolean;

procedure Insert(const aKey : string; aItem : 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);