Двойное хэширование
Для обеспечения равномерного распределения ключей в хэш-таблице при наличии коллизий можно применять метод двойного хэширования. Он состоит в том, что если при включении или поиска ключа в хэш-таблице возникает коллизия, то к ключу (или к комбинации ключа и текущего индекса массива) применяется вторичная хэш-функция, значение которой указывает циклическое смещение в массиве от текущего индекса к элементу, в который следует включать или в котором следует искать требуемую запись (рисунки 4.21, 4.22).
Рис. 4.21.
Поскольку метод двойного хэширования в полной форме приводит к слишком большим накладным расходам, на практике часто используется упрощенная форма этого метода, не гарантирующая равномерности записей в массиве, но обеспечивающая лучшие результаты, чем линейное зондирование. Один из способов состоит в использовании квадратичной функции при вычислении индекса следующей пробы. В этом случае последовательность вычисления индексов проб при включении или поиске записи является следующей: h0 = H(K) ........ hi = (h0 + i^2) MOD N (i>0)
Основным недостатком метода квадратичных проб является то, что для включаемой записи может не найтись свободного элемента массива даже в том случае, когда реально около половины элементов являются свободными.
Рис. 4.22.
