Методы разрешения коллизий

Разрешение коллизий "открытой адресацией" состоит в том, чтобы полностью отказаться от ссылок и просто просматривать один за другим различные элементы таблицы, пока не будут найдены ключ K или свободная позиция. Не плохо было бы иметь правило, согласно которому каждый ключ K определяет последовательность проб, т.е. последовательность позиций в таблице, которые нужно просматривать всякий раз при вставке или поиске K. Если мы, используя определяемую K последовательность проб, натолкнемся на свободную позицию, то можно сделать вывод, что K нет в таблице, так как та же последовательность проб выполняется каждый раз при обработке данного ключа. Этот общий класс методов У. Петерсон назвал открытой адресацией.(метод случайного зондирования, метод линейного зондирования, метод квадратичного зондирования)

. Метод цепочек. В процессе хеширования возможно появление одинаковых адресов для различных ключей. Способ разрешения таких коллизий состоит в поддерживании М связанных списков по одному на каждый возможный хеш-адрес. Все связи должны содержать поля связей и нужно образовать массив ссылок, которые будут являться головами списков HEAD[i], где i÷1→М. После хеширования ключа выполняется последовательный поиск в списке с номером h(k).

Метод раздельных цепочек

Ключ k one two three four five six seven

Адрес h(k) 3 1 4 1 5 9

Метод по рассеянной таблицей со сросшимися цепочками. Этот алгоритм позволяет отыскать в таблице из N элементов ключ k. Если ключа нет и таблица не полная, то ключ k вставляется в неё. Элементы таблицы TABLE[i], где 0≤і≤М. Эти элементы могут быть 2-х типов: заняты и свободны. Занятый узел содержит ключевое поле KEY[i], поле связи LINK[i] и т.д.

Поиск по сайту: