2. Разрешение коллизий методом цепочек

Имеется несколько причин, почему повторное хеширование может быть неадекватным методом для обработки коллизий при хешировании. Во-первых, оно предполагает фиксированный размер таблицы. Если число записей превысит этот размер, то невозможно выполнять вставки без выделения таблицы большего размера и повторного вычисления значений хеширования для ключей всех записей, находящихся уже в таблице, используя новую хеш-функцию. Более того, из такой таблицы трудно удалить запись. Например, предположим, что в позиции рosInd находится запись Rec1. При добавлении некоторой записи Rec2, чей ключ k2 хешируется в рosInd, эта запись должна быть вставлена в первую свободную позицию rh(рosInd), rh(rh(рosInd)), .... Предположим, что Rec1 затем удаляется, так что ячейка с индексом рosInd становится свободной. Поиск записи Rec2 начинается с позиции h(k2), что равно рosInd. Но поскольку эта позиция уже свободна, процесс поиска может ошибочно сделать вывод, что записи Rec2 нет в таблице.

Одно возможное решение этой проблемы состоит в маркировании удаленной записи как «удаленная» (логическое удаление), а не «свободная», и продолжении поиска, когда встречается такая «удаленная» позиция. Но это реально, если только выполняется небольшое число удалений. В противном случае при неудачном поиске придется организовать поиск по всей таблице, потому что большинство позиций будет отмечено как «удаленные», а не «свободные».

Другой метод разрешения коллизий при хешировании называется методом цепочек или методом, использующим связывание (chaining). Он представляет собой организацию связанного списка (цепочки) из всех записей, чьи ключи хешируются в одно и то же значение. Предположим, что хеш-функция выдает значения в диапазоне от 0 до N-1. Тогда описывается некоторый массив arrHeader, имеющий размер N и состоящий из узлов заголовков. Элемент arrHeader[i] указывает на список всех записей, чьи ключи хешируются в i.

Вставка c помощью хеширования осуществляет доступ к заголовку списка arrHeader[k], где k = h(Key). Затем производится вставка элемента с ключом Key в k-ый список. На рисунке 12.2 показан метод цепочек. Предполагается, что имеется массив заголовков из 10 элементов и что хеш-функция равна Key Mod 10. Предполагается также, что включение очередного элемента производится в конец списка. На рисунке представлен пример поступления ключей в таком порядке:

75, 66, 42, 192, 91, 40, 49, 87, 67, 16, 417, 130, 372, 227

Рисунок 12.2  Разрешение коллизий методом цепочек

Удаление узла из таблицы, которая построена по методу цепочек, заключается просто в исключении узла из связанного списка. Удаленный узел никак не влияет на эффективность алгоритма поиска. Алгоритм будет работать так, как если бы этот узел никогда не вставлялся в таблицу. Отметим, что эти списки могут быть динамически переупорядочены для получения большей эффективности поиска.

Поиск выполняется очень просто: сначала аргумент поиска ArgSearch хешируется в некоторый индекс, допустим в индекс k, а затем в k-ом списке осуществляется поиск ключа, равного значению ArgSearch.

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