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

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

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

$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 — размер таблицы. Пусть я ^й положение датчика для значения k задается функцией

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

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

Примеры:

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

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++;
	return v;
}

Ограничения [ править ]

Чередование знаков [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] Кормен, Томас Х.; Лейзерсон, Чарльз Эрик; Ривест, Рональд Линн; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс, Лондон, Англия: MIT Press. ISBN 978-0-262-53305-8 .

[2] Рихтер, Стефан; Альварес, Виктор; Диттрих, Йенс (2015). «Семимерный анализ методов хеширования и его влияние на обработку запросов» . Труды Фонда VLDB . 9 (3): 96–107. дои : 10.14778/2850583.2850585 . ISSN 2150-8097 .

[3] Маурер, WD (1968). «Техника программирования: улучшенный хэш-код для разбросанного хранилища» . Коммуникации АКМ . 11 (1): 35–38. дои : 10.1145/362851.362880 . ISSN 0001-0782 .

[4] Искусство информатики, том 3, сортировка и поиск, глава 6.4, упражнение 20, Дональд Кнут

[1]

[2]

[3]

[4]