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

Самым простым методом разрешения коллизий при хешировании является помещение данной записи в следующую свободную позицию в массиве. Например, запись с ключом 0596397 помещается в ячейку 398, которая пока свободна, поскольку 397 уже занята. Когда эта запись будет вставлена, другая запись, которая хешируется в позицию 397 (с таким ключом, как 8764397) или в позицию 398 (с таким ключом, как 2194398), вставляется в следующую свободную позицию, которая в данном случае равна 400.

Этот метод еще называется методом линейных проб, он является примером некоторого общего метода разрешения коллизий при хешировании, который называется повторным хешированием.

В общем случае функция повторного хеширования rh воспринимает один индекс в массиве и выдает другой индекс.

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

Алгоритмы метода открытой адресации

Function h(key) – хеш- функция

h = key mod n

return

Function rh(i) - функция повторного хеширования

rh = i+1 mod n

return

Procedure insert(key) – процедура вставки ключа в хеш-таблицу

i = h(key) {хешируем ключ}

while ((k(i)< >key) and (k(i)< > nullkey)) do

i = rh(i) { повторное хеширование}

if k(i) = nullkey then {вставляем ключ в пустую позицию}

k(i) = key

endwhile

return