Поиск в таблице - часть 15

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

Закрытые методы разрешения коллизий более сложные. Их основная идея — при возникновении коллизии попытаться отыскать в хэш-таблице свободную ячейку. Процедуру поиска свободной ячейки называют пробитом, или рехэшировани-ем (вторичным хэшированием). При возникновении коллизии к первоначальному хэш-адресу А(К) добавляется некоторое значение р, и вычисляется выражение (2.5). Если новый хэш-адрес А(К) опять вызывает коллизию, то (2.5) вычисляется при р2, и так далее:

А(К) = (A(K)+Pi)mod М (I = 0..М). (2.5)

push ds popes

lea si .buf.len_in

mov cl .buf .lenjn

inccx :длину тоже нужно захватить

add di .lenjd repmovsb

jmp ml displ: :выводим идентификатор, вызвавший коллизию, на экран

рехэширование

;ищем место для идентификатора, вызвавшего коллизию в таблице, путем линейного рехэширования i nc bx mov ax.bx jmp m5

Квадратичное рехэширование

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

Pi = а,2+Ь,+с. (2.6)

Хотя значения а, Ь, с можно задавать любыми, велика вероятность быстрого зацикливания значений р(. Поэтому в качестве рекомендации опишем один из вариантов реализации процедуры квадратичного рехэширования, позволяющий осуществить перебор всех элементов хэш-таблицы [32]. Для этого значения в формуле (2.6) положим равными: а=1,Ь = с = 0. Размер таблицы желательно задавать равным простому числу, которое определяется формулой М = 4п+3, где п — целое число. Для вычисления значений р> используют одно из соотношений: