6.2. Разрешение коллизий и структуры хеш-таблиц

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

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

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

Рис. 24. Хеш-таблица с цепочками коллизий.

Хеш-таблица с открытой адресацией представляет собой массив Т, в который помещаются элементы таблицы по индексу, равному хеш-значению ключа. При возникновении коллизии выполняется поиск другой ячейки массива (зондирование), в которой может разместиться элемент. Эта ячейка должна быть свободной (открытой). Для пометки состояния в ячейки таблицы вводится специальный признак состояния ячейки state. Ячейка хеш-таблицы может быть в одном из трех состояний: свободна (free), занята (busy), свободна после удаления из неё элемента (deleted). Открытой считается ячейка, находящаяся в состоянии free или deleted.

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

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

При линейном зондировании хеш-функция при каждой попытке поиска вычисляет новую ячейку по формуле

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

, где h(k)- обычная хеш-функция, i – номер попытки поиска свободной ячейки.

При работе с ключом k первой выбирается ячейка T[h(k)], а затем перебираются ячейки таблицы подряд: T[h(k)+1], T[h(k)+2], …. После ячейки T[m-1] следует ячейка T[0]. У метода очевидный недостаток: он может привести к образованию кластеров – длинных последовательностей занятых ячеек, идущих подряд. Это удлиняет поиск.

При квадратичном зондировании хеш-функция, задаёт квадратичную последовательность ячеек по формуле:

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

, где c₁≠ 0 и c₂ ≠ 0 – некоторые константы. Пробы начинаются с ячейки T[h(k)], но дальше ячейки просматриваются не подряд. Номер пробуемой ячейки квадратично зависит от номера попытки. Для того, чтобы использовались все ячейки таблицы, c₁ и c₂ нужно тщательно подбирать. Хорошую квадратичную последовательность проб даёт алгоритм, явно не использующий константы c₁ и c₂. Алгоритм продемонстрирован на примере вставки элемента в хеш-таблицу.

Hash_Insert (T, k)

j← h(k)

i← 0

while i ≠ m

do if T[j] = free or deleted

then T[j] = k

return j

i← (i + 1)

j← (j + i) mod m

error “Переполнение хеш-функции”

При квадратичном зондировании тенденция к образованию кластеров частично устраняется. Хотя и остается эффект кластеризации в более мягкой форме – образование вторичных кластеров.

Двойное хеширование – один из лучших методов открытой адресации. Последовательности индексов, возникающие при зондировании с двойным хешированием, близки к равномерному хешированию. При двойном хешировании функция h имеет вид:

h (k, i) = (h(k) + ih₁(k)) mod m

, где h(k) и h₁ (k) – обычные хеш-функции. То есть, последовательность проб при зондировании является арифметической прогрессией по модулю m с первым членом h(k) и шагом h₁(k).

Чтобы последовательность зондируемых ячеек охватывала всю таблицу, значение h₁(k) должно быть взаимно простым с размером хеш-таблицы m. Простой способ добиться этого условия – выбрать в качестве m степень двойки, а функцию h₁(k) взять такую, чтобы она принимала только нечетные значения. В другом варианте, если m – простое число, значения h₁(k) - целые положительные числа, меньшие m. Например, если используется модульное хеширование, в котором размер хеш-таблицы выбирается, как простое число, то можно положить:

h (k) = k mod m

h₁(k) = 1 + (k mod m₁),

, где m₁ чуть меньше, чем m (m₁= m-1 или m-2).