Квадратичное тестирование в хеш-таблицах

Во время задания меня попросили показать, что хеш-таблица размера m (m>3, m — простое число), заполненная менее чем наполовину и использующая квадратичную проверку (hash(k, i) = (h(k) + i^2) mod m), всегда найдет свободное место.

Я проверил и пришел к выводу, что точки, которые будут найдены (когда h(k)=0), это 0 mod m, 1 mod m, 4 mod m, 9 mod m, ...
Моя проблема в том, что я не могу понять способ показать, что он всегда найдет свободное место. Я сам тестировал его с разными значениями m, а также убедился, что если хэш-таблица заполнена более чем наполовину, мы можем никогда не найти свободного места.

Может ли кто-нибудь подсказать мне, как решить эту проблему?

Спасибо!


algorithm hash hashtable
person CS n00b    schedule 03.01.2010    source источник

Ответы (3)


arrow_upward
1
arrow_downward

0, 1, 4, ..., ((m-1)/2) ^ 2 различны по модулю m. Почему?

Предположим, что два числа из этого диапазона, i^2 и j^2, эквивалентны по модулю m.

Тогда i^2 - j^2 = (i-j)(i+j) = 0 (mod m). Поскольку m простое число, m должно делить один из этих множителей. Но оба множителя меньше m, поэтому один из них ((i-j)) равен 0. То есть i = j.

Поскольку мы начинаем с 0, более половины слотов различны. Если вы можете заполнить менее m/2 из них, по крайней мере один останется открытым.

person uncleO    schedule 03.01.2010

arrow_upward
0
arrow_downward

Из Википедии:

Для простого числа m > 2 большинство вариантов выбора c1 и c2 сделают h(k,i) различными для i из [0,(m − 1)/2]. К таким вариантам относятся c1 = c2 = 1/2, c1 = c2 = 1 и c1 = 0,c2 = 1. Поскольку для данного элемента имеется всего около m/2 различных тестов, трудно гарантировать, что вставки будут успешными, когда коэффициент загрузки > 1/2.

См. раздел о квадратичном зондировании в статье Структуры данных и алгоритмы с объектно-ориентированными шаблонами проектирования в C++ для доказательства того, что m/2 элементов различны, когда m — простое число.

person Pedro Silva    schedule 03.01.2010
comment
Спасибо! если бы я только знал, что по-английски это называется "зондирование", а не "тестирование"... :) - person CS n00b; 03.01.2010
comment
К сожалению, приведенное доказательство относится не к m — простой части, а к m — степени двойки. - person CS n00b; 03.01.2010

arrow_upward

arrow_downward

person    schedule
comment
Применяется ли это доказательство только к случаю, когда f(i) = i^2; или оно обобщается на любое квадратное уравнение? На первый взгляд, мне кажется, что наличие вспомогательного термина (например, f(i) = a*i + b*i^2) позволит повторять до M/2 - person Zack; 16.09.2019