Разрешение коллизий - закрытое хэширование

В методе закрытого хэширования, новый ключ, вызывающий коллизию с ранее вставленным ключем, помещают в ближайшую соседнюю свободную ячейку. Такой подход также называют хэш-таблицами с ЛИНЕЙНЫМ ОПРОБИРОВАНИЕМ, или хэш-таблицами с ЛИНЕЙНЫМ РАЗРЕШЕНИЕМ КОЛЛИЗИЙ.

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

В том же самом примере, новый ключ 35, изначально указывает на ячейку с индексом 5, которая уже занята ключом 25. Ближайшая ячейка справа - с индексом 6 - свободна, и конфликтующий новый ключ будет помещен в нее:

Соответственно, для поиска в таблице значения по некоторому ключу xk необходимо:

1. Вычислить значение хэш-кода для ключа: hk=h(xk)=xk%N.
2. Если ячейка по индексуhkзанята:

a. Сравнить хранящийся в ней ключ с xk, и если они равны, вернуть значение yk.

b. Если ключи не равны, двигаться к следующей ячейке и повторить процедуру 2.

c. Если достигнут конец массива, перейти к его началу и продолжить процедуру 2.

1. Если ячейка по индексу hk не занята, искомый ключ в таблице не содержится.

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

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

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

После удаления ключа 25, ячейка 5 должна быть помечена специальным маркером (графически показано желтым цветом заливки). Далее, при поиске ключа 35, изначально попав по ключу в ячейку 5, алгоритм обнаружит, что там ранее находился некоторый удаленный ключ. Из этого будет сделан вывод, что нужно продолжать поиск ключа в следующих ячейках. Сделав шаг к ячейке 6, искомый ключ 35 будет обнаружен.

Если теперь в таблицу вставить новую пару ключ-значение с таким же хэш-кодом, то ее можно помещать на место ранее удаленного элемента, и это не нарушит логику поиска в хэш-таблице::