Алгоритм квадратичных проб

При этом после индекса i рассматриваются не i+1, i+2 и т.д., как в предыдущем алгоритме, а i+1, i+4, i+9 и т. д., то есть добавляются квадраты натуральных чисел (естественно, по модулю N). Фактически нет необходимости вычислять значения квадратов путем умножения, можно воспользоваться формулами: i:= i+d; d:= d+2; при начальном значении d = 1.

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

Алгоритм двойного хеширования

Идея этого алгоритма в том, чтобы при поиске свободной позиции в массиве прибавлять к вычисленному индексу не 1, как при линейных пробах, и не квадрат номера попытки, как при квадратичных пробах, а некоторое число, зависящее от хешируемого ключа. Поскольку при этом для разных ключей будут просматриваться разные позиции, будет больше шансов избавиться от нежелательного скучивания.

Пусть кроме функции h(x) мы умеем вычислять еще одну хеш-функцию, которую будем называть hh(x). К этой функции предъявляются дополнительные требования: она не должна давать нулевого значения и все ее значения должны быть взаимно просты с размером хеш-таблицы N. На самом деле, если N – простое число, то значение hh(x) может быть любым числом от 1 до N–1; если же N есть степень двойки, то надо еще потребовать, чтобы hh(x) всегда было нечетным. Для этого можно просто-напросто с помощью дизъюнкции устанавливать младший разряд равным 1.

В случае возникновения коллизии для значения i = h(x) следует вычислить значение c = hh(x) и искать свободный элемент массива в позициях i+c, i+2c, i+3c и т.д., а при выходе за конец массива выполнять переход на начало по модулю N.

Требование взаимной простоты N и hh(x) дает гарантию, что при поиске свободного места будут при необходимости просмотрены все позиции хеш-таблицы.