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

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

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

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

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

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

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

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

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