Квадратичный зонд

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

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

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

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

Квадратичное зондирование впервые было введено Уордом Дугласом Маурером в 1968 году. ^[3]

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

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

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

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

Примеры:

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

uint64_t roundUp2 ( uint64_t v ){ v -- ; v |= v >> 1 ; v |= v >> 2 ; v |= v >> 4 ; v |= v >> 8 ; v |= v >> 16 ; v |= v >> 32 ; в ++ ; вернуть v ; }                           

Ограничения

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

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

Ссылки

1. Кормен, Томас Х.; Лейзерсон, Чарльз Эрик; Ривест, Рональд Линн; Штейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс, Лондон, Англия: MIT Press. ISBN 978-0-262-53305-8.
2. Рихтер, Стефан; Альварес, Виктор; Диттрих, Йенс (2015). «Семимерный анализ методов хеширования и его влияние на обработку запросов». Труды VLDB Endowment . 9 (3): 96–107. doi :10.14778/2850583.2850585. ISSN  2150-8097.
3. Maurer, WD (1968). «Техника программирования: улучшенный хэш-код для разбросанного хранения». Communications of the ACM . 11 (1): 35–38. doi : 10.1145/362851.362880 . ISSN  0001-0782.
4. Искусство информатики Том 3 Сортировка и поиск, Глава 6.4, упражнение 20, Дональд Кнут

Внешние ссылки

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