2.3 Открытая адресация

При использовании метода открытой адресации все элементы хранятся непосредственно в хеш-таблице, т.е. каждая запись таблицы содержит либо элемент динамического множества, либо значение NULL. При поиске элемента мы систематически проверяем ячейки таблицы до тех пор, пока не найдем искомый элемент или пока не убедимся в его отсутствии в таблице. Здесь, в отличие от метода цепочек, нет ни списков, ни элементов, хранящихся вне таблицы. Таким образом, в методе открытой адресации хеш-таблица может оказаться заполненной, делая невозможной вставку новых элементов; коэффициент заполнения a не может превышать 1.

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

Пусть задана обычная хеш-функция h: U - {0, 1,..., m - 1}. Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию

h(k, i) = (h(k) + i) mod m, (1.1)

где i принимает значения от 0 до m - 1 включительно. Для данного ключа k первой исследуемой ячейкой является T[h(k)], т.е. ячейка, которую дает вспомогательная хеш-функция. Далее мы исследуем ячейку T[h(k) + 1] и далее последовательно все до ячейки T[m - 1], после чего переходим в начало таблицы и последовательно исследуем ячейки T[0], Т[1], и так до ячейки T[h(k) - 1]. Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется m различных последовательностей.

Линейное исследование легко реализуется, однако с ним связана проблема первичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска. Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют i заполненных ячеек, равна (i + 1) / m. Таким образом, это приводит к увеличению среднего времени поиска.

Квадратичное исследование использует хеш-функцию вида

h(k, i) = (h(k) + c₁i + c₂i²) mod m, (1.2)

где h - вспомогательная хеш-функция, c₁ и c₂ != 0 - вспомогательные константы, а i принимает значения от 0 до m - 1 включительно. Начальная исследуемая ячейка - T[h(k)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования i. Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений c₁ c₂ и m. Кроме того, если два ключа имеют одну и то же начальную позицию исследования, то одинаковы и последовательности исследования в целом, так как из h₁(k, 0) = h₂(k, 0) вытекает h₁(k, i) = h₂(k, i). Это свойство приводит к более мягкой вторичной кластеризации. Как и в случае линейного исследования, начальная ячейка определяет всю последовательность, поэтому всего используется m различных последовательностей исследования.

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

h(k, i) = (h1(k) + ih2(k)) mod m, (1.3)

где h1 и h2 - вспомогательные хеш-функции. Начальное исследование выполняется в позиции T[h1(k)], а смещение каждой из последующих исследуемых ячеек относительно предыдущей равно h2(k) по модулю m. Следовательно, в отличие от линейного и квадратичного исследования, в данном случае последовательность исследования зависит от ключа k по двум параметрам - в плане выбора начальной исследуемой ячейки и расстояния между соседними исследуемыми ячейками, так как оба эти параметра зависят от значения ключа.

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