3. Методы разрешения коллизий

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

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

Ниже приведены наиболее известные методы разрешения коллизий.

1. Алгоритм линейных проб

Если элемент массива с индексом i = h(x)уже занят, то последовательно проверяются элементыi+1,i+2и т.д., пока не будет найден свободный. Если свободная позиция не будет найдена до конца хеш-таблицы, следует продолжить поиск от начала таблицы.

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

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

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

2. Алгоритм квадратичных проб

При этом после индекса iрассматриваются неi+1,i+2и т.д., как в предыдущем алгоритме, аi+1,i+4,i+9и т. д., то есть добавляются квадраты натуральных чисел (естественно, по модулюN). Фактически нет необходимости вычислять значения квадратов путем умножения, можно воспользоваться формулами:i := i+d; d := d+2;при начальном значенииd = 1.

Этот алгоритм дает меньшее скучивание. В примере из предыдущего параграфа искомый ключ будет найден уже с третьей попытки. Сохраняется такой недостаток, как трудность удаления записей. Кроме того, данный алгоритм не гарантирует, что при включении будут проверены все свободные места. Однако, если n– простое число, то можно доказать, что будет проверено, по крайней мере,n/2позиций. Этого может не хватить только при большом заполнении таблицы.

3. Алгоритм двойного хеширования

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

Пусть кроме функции h(x)мы умеем вычислять еще одну хеш-функцию, которую будем называтьhh(x). К этой функции предъявляются дополнительные требования: она не должна давать нулевого значения и все ее значения должны быть взаимно просты с размером хеш-таблицыN. На самом деле, еслиN– простое число, то значениеhh(x)может быть любым числом от 1 доN–1; если жеNесть степень двойки, то надо еще потребовать, чтобыhh(x)всегда было нечетным. Для этого можно просто-напросто с помощью дизъюнкции устанавливать младший разряд равным 1.

В случае возникновения коллизии для значения i = h(x)следует вычислить значениеc = hh(x)и искать свободный элемент массива в позицияхi+c,i+2c,i+3cи т.д., а при выходе за конец массива выполнять переход на начало по модулюN.

Требование взаимной простоты Nиhh(x)дает гарантию, что при поиске свободного места будут при необходимости просмотрены все позиции хеш-таблицы.