Разрешение коллизий

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

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

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

Стратегии поиска

Последовательный поиск

При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

Линейный поиск

Выбираем шаг [math]q[/math]. При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+(1*q), i+(2*q), i+(3*q)[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. По сути Последовательный поиск - частный случай линейного, где [math]q=1[/math].

Квадратичный поиск

Шаг [math]q[/math] не фиксирован, а изменяется квадратично. В качестве начального значения часто выбирается [math]1[/math]. При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+q, i+q^2, i+q^3[/math] и так далее, пока не найдём свободную ячейку.