Здравствуйте. Не могу разобраться в схеме выбора шага в квадратичном зондировании при работе с хеш-таблицей с открытой адресацией.
Хеш-функция выглядит следующим образом:
cpp Код:
h'(k, j) = (h(k) + c1*j + c2*j*j)%m
h(k) -- функция мультипликативного хеширования, с1 и с2 -- некоторые коэффициенты, подбираемые таким образом, чтобы просмотреть все ячейки таблицы.
При каждой новой пробе шаг меняется на некоторую, в свою очередь тоже меняющуюся, величину. Возможно, что при некоторых соотношениях h(k) и c1 c2 мы получим последовательность, которая будет бить в одни и те же ячейки таблицы (размер мой таблицы -- степень двойки). Как избегать таких ситуаций? Можно ли положить, что такое хеширование просто дает неудачный результат в некоторых случаях (при условии, что c1 и c2 обеспечивают теоретически верную трудоемкость), или следует обрабатывать такие ситуации, искусственно меняя шаг? Если следует, то как своевременно распознать такую ситуацию?