Квадратичное зондирование - Quadratic probing

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

Пример последовательности с использованием квадратичного зондирования:

${\displaystyle H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}}$

Квадратичное зондирование может быть более эффективным алгоритмом в открытая адресация table, так как он лучше позволяет избежать проблемы кластеризации, которая может возникнуть с линейное зондирование, хотя это не застраховано. Он также обеспечивает хорошее кэширование памяти, поскольку сохраняет некоторые местонахождение ссылки; однако линейное зондирование имеет большую локальность и, следовательно, лучшую производительность кеша.^{[сомнительный ][нужна цитата ]}

Квадратичная функция

Позволять час(k) быть хэш-функция который отображает элемент k до целого числа в [0,м−1], где м это размер таблицы. Пусть я^th положение датчика для значения k быть заданным функцией

${\displaystyle h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod {m}}}$

куда c₂ ≠ 0. (Если c₂ = 0, то час(k,я) деградирует до линейный зонд. Для данного хеш-таблица, значения c₁ и c₂ Остаются неизменными.

Примеры:

• Если ${\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}$, то последовательность зонда будет ${\displaystyle h(k),h(k)+2,h(k)+6,...}$
• За м = 2^п, хорошим выбором для констант являются c₁ = c₂ = 1/2, так как значения час(k,я) за я в [0,м−1] все различны. Это приводит к пробной последовательности ${\displaystyle h(k),h(k)+1,h(k)+3,h(k)+6,...}$ (в треугольные числа ), где значения увеличиваются на 1, 2, 3, ...
• Для премьер м > 2, большинство вариантов c₁ и c₂ сделаю час(k,я) отличное для я в [0, (м−1) / 2]. Такие варианты включают c₁ = c₂ = 1/2, c₁ = c₂ = 1 и c₁ = 0, c₂ = 1. Однако есть только м/ 2 различных зонда для данного элемента, требующие других методов, чтобы гарантировать успешность вставки, когда коэффициент нагрузки превышает 1/2.

Ограничения

Однако при использовании квадратичного измерения (за исключением треугольное число случаи для хеш-таблицы размера ${\displaystyle 2^{n}}$),^[1] нет гарантии нахождения пустой ячейки, когда таблица заполнится более чем наполовину, или даже раньше, если размер таблицы составной,^[2] потому что коллизии необходимо разрешать с использованием не более половины таблицы.

Обратное этому можно доказать как таковое: предположим, что хеш-таблица имеет размер ${\displaystyle p}$ (простое число больше 3) с начальным местоположением ${\displaystyle h(k)}$ и два альтернативных места ${\displaystyle h(k)+x^{2}{\pmod {p}}}$ и ${\displaystyle h(k)+y^{2}{\pmod {p}}}$ (куда ${\displaystyle 0\leq x}$ и ${\displaystyle y\leq p/2}$Если эти два местоположения указывают на одно и то же ключевое пространство, но ${\displaystyle x\neq y}$, тогда

${\displaystyle h(k)+x^{2}=h(k)+y^{2}{\pmod {p}}}$

${\displaystyle x^{2}=y^{2}{\pmod {p}}}$

${\displaystyle x^{2}-y^{2}=0{\pmod {p}}}$

${\displaystyle (x-y)(x+y)=0{\pmod {p}}}$.

В качестве ${\displaystyle p}$ простое число, либо ${\displaystyle (x-y)}$ или же ${\displaystyle (x+y)}$ должен делиться на ${\displaystyle p}$.С ${\displaystyle x}$ и ${\displaystyle y}$ разные (по модулю ${\displaystyle p}$), ${\displaystyle (x-y)\neq 0}$, и поскольку обе переменные больше нуля, ${\displaystyle (x+y)\neq 0}$. Таким образом, от противного, первый ${\displaystyle p/2}$ альтернативные места после ${\displaystyle h(k)}$ должен быть уникальным, и, следовательно, всегда можно найти пустое место, пока не более ${\displaystyle p/2}$ места заполнены (т.е. хеш-таблица заполнена не более чем наполовину).

Чередование знаков

Если знак смещения меняется (например, +1, −4, +9, −16 и т. Д.), И если количество сегментов является простым числом ${\displaystyle p}$ конгруэнтно 3 по модулю 4 (например, 3, 7, 11, 19, 23, 31 и т. д.), то первый ${\displaystyle p}$ смещения будут уникальными (по модулю ${\displaystyle p}$).^{[требуется дальнейшее объяснение ]} Другими словами, перестановка 0 через ${\displaystyle p-1}$ получается, и, следовательно, всегда будет найдена свободная корзина, пока существует хотя бы одна.

Рекомендации

1. Hopgood, F. Robert A .; Давенпорт, Джеймс Х. (Ноябрь 1972 г.). «Метод квадратичного хеширования, когда размер таблицы является степенью двойки». Компьютерный журнал. 15 (4): 314–5. Дои:10.1093 / comjnl / 15.4.314. Получено 2020-02-07.
2. Вайс, Марк Аллен (2009). «§5.4.2 Квадратичное зондирование». Структуры данных и анализ алгоритмов в C ++. Pearson Education. ISBN  978-81-317-1474-4.

внешняя ссылка

• Учебное пособие / квадратичное зондирование