Разрешение коллизий при хешировании методом открытой адресации

Вернемся к вопросу возникшей коллизии при вставке записи с ключом 0596396 в имеющийся массив записей и с хеш-функцией mod(key, 1000).

Самым простым способом разрешения возникшей коллизии является помещение записи 0596396 в следующую свободную позицию в массиве. Например, если ячейка свободна, то можно поместить запись туда. Этот метод называется линейным опробованием, и он является примером некоторого общего метода разрешения коллизий при хешировании, который называется повторным хешированием или открытой адресацией. В общем случае функция повторного хеширования rh воспринимает один индекс в массиве и выдает другой индекс. Если ячейка массива h(key)уже занята некоторой записью с другим ключом, то функция rhприменяется к значению h(key)для того, чтобы найти другую ячейку, куда может быть помещена эта запись. Если ячейка rh(h(key)) также занята, то хеширование выполняется еще раз и проверяется ячейка rh(rh(h(key))). Этот процесс продолжается до тех пор, пока не будет найдена пустая ячейка [3].

Например, если h(key) = mod(key,1000), то в качестве rhфункции можно взять функцию mod(i+1,1000), т.е. повторное хеширование какого-либо индекса есть следующая последовательная позиция в данном массиве, за исключением того случая, что повторное хеширование 999 дает 0.

Любая функция rh(i) = mod(i+c, m), где с— константа, такая что cи mявляются взаимно простыми числами (т.е. они одновременно не могут делиться нацело ни на какое число, кроме 1), выдает последовательные значения, которые распространяются на всю таблицу.

Рассмотрим ситуацию, возникающую при повторном хешировании, которая называется скучиванием.

Рис. 4.8

Обратимся к Рис. 4.8, из которого видно, что помещение записи в позицию 994 в пять раз вероятнее, чем в позицию 401. Это происходит из-за того, что любая запись, чей ключ хешируется в позиции 990–994 будет помещена в 994, а в позицию 401 будет помещена только та запись, чей ключ хешируется в эту позицию. Это явление, при котором два ключа конкурируют друг с другом при повторных хешированиях называется скучиванием.

Одним из способов исключения скучивания является использование двойного хеширования, которое состоит в использовании двух хеш-функций: h₁(key) и h₂(key). Функция h₁(key), называемая первичной хеш-функцией, используется первой при определении позиции, в которую должна быть помещена запись. Если эта позиция занята, то последовательно используется функция повторного хеширования

rh(i) = mod(i+ h₂(key), m)

до тех пор, пока не будет найдена пустая позиция. Записи с ключами key₁ и key₂ не будут соревноваться за одну и ту же позицию, если h₂(key₁) ¹ h₂(key₂).

Другой метод разрешения коллизий при хешировании называется методом цепочек. Он представляет собой организацию связанного списка из всех записей, чьи ключи хешируются в одну и ту же позицию. Предположим, что хеш-функция выдает значения в диапазоне от 0 до m-1. Тогда описывается некоторый массив, например, bucket, размера m. Элемент bucket(i) указывает на список всех записей, чьи ключи хешируются в i. При поиске записи осуществляется доступ к указателю списка, который занимает позицию i в массиве bucket. Если запись не найдена, то она вставляется в конец списка. Обратимся к Рис. 4.9, на котором показан метод цепочек. Предположим, что имеются 14 элементов, хеш-функция равна mod(key, 10). Ключи представлены в таком порядке:

75 66 42 192 91 40 49 87 67 16 417 130 372 227

Рис. 4.9. Разрешение коллизий при хешировании методом цепочек