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

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

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

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

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

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

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

Примеры:

  • Если , то последовательность зонда будет
  • За м = 2п, хорошим выбором для констант являются c1 = c2 = 1/2, так как значения час(k,я) за я в [0,м−1] все различны. Это приводит к пробной последовательности треугольные числа ), где значения увеличиваются на 1, 2, 3, ...
  • Для премьер м > 2, большинство вариантов c1 и c2 сделаю час(k,я) отличное для я в [0, (м−1) / 2]. Такие варианты включают c1 = c2 = 1/2, c1 = c2 = 1 и c1 = 0, c2 = 1. Однако есть только м/ 2 различных зонда для данного элемента, требующие других методов, чтобы гарантировать успешность вставки, когда коэффициент нагрузки превышает 1/2.

Ограничения

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

Обратное этому можно доказать как таковое: предположим, что хеш-таблица имеет размер (простое число больше 3) с начальным местоположением и два альтернативных места и (куда и Если эти два местоположения указывают на одно и то же ключевое пространство, но , тогда

.

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

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

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

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

  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.

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