Квадратичное зондирование: (f (k) + a * j + b * j ^ 2)% M, как выбрать a и b?

Question

Если M простое число, как выбрать a и b, чтобы минимизировать коллизии?

Также в книгах написано, что, чтобы найти пустую ячейку при квадратичном зондировании в (f (k) + j ^ 2)% M, хеш-таблица должна быть как минимум наполовину пустой? Может ли кто-нибудь предоставить мне доказательство этого?

Answer 1

Есть несколько значений для выбора a и b в wikipedia :

Для простых M> 2 большинство вариантов a и b приведут к тому, что f (k, j) будут различны для j в [0, (M - 1) / 2]. Такие варианты выбора включают a = b = 1/2, a = b = 1 и a = 0, b = 1. Поскольку существует только около M / 2 различных зондов для данного элемента, трудно гарантировать, что вставки будут успешными когда коэффициент нагрузки> 1 / 2.

Подтверждением гарантии нахождения пустых слотов является здесь или здесь .