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

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

Предположим, что хеш-функция выдает значения в диапазоне от 0 до n-1. Тогда описывается некоторый массив bucket, имеющий размер n и состоящий из узлов заголовков. Элемент bucket (i) указывает на список всех записей, чьи ключи хешируются в i. При поиске записи осуществляется доступ к заголовку списка, который занимает позицию i в массиве узлов. Если запись не найдена, то она вставляется в конец списка.

Алгоритм реализации метода цепочек

i = h(key)

q = nil

р = bucket (i)

while p < >nil do

if k(p) = key

then search = p

return

endif

q = p

p = nxt(p)

endwhile

{ключ не найден, вставляем новую запись}

s = getnode

k(s) = key

nxt(s) = nil

if q = nil

then bucket (i) = s

else nxt(q) = s

endif

search = s

return

Удаление узла из таблицы, которая построена по методу цепочек, заключается просто в исключении узла из связанного списка. Удаленный узел никак не влияет на эффективность алгоритма поиска. Алгоритм будет работать так, как если бы этот узел никогда не вставлялся в таблицу. Отметим, что эти списки могут быть динамически переупорядочены для получения большей эффективности поиска.

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