Рассчитать вероятность отсутствия столкновения при хэшировании двух элементов h(x)=(x^2+1)mod3

Question

Как я могу рассчитать вероятность отсутствия столкновения после вставки 2 элементов. ответ 4/9, но я не вижу, как это 4/9

Answer 1

Я не уверен, что это уместный вопрос, но вот мой шанс на ответ. Это ни в коем случае не законное математическое доказательство, но оно работает.

Для вашей функции h(x) = (x^2+1)mod3 давайте приведем несколько примеров значений.

h (1) = (1 + 1) mod3 = 2mod3 = 2
h (2) = (4 + 1) mod3 = 5mod3 = 2
h (3) = (9 + 1) mod3 = 10mod3 = 1

h (4) = 17mod3 = 2
h (5) = 26мод3 = 2
h (6) = 37mod3 = 1

Этот шаблон будет продолжен из-за характера функции (возведение в квадрат и добавление 1).

Таким образом, у нас есть (2/3) вероятность того, что наша функция оценивается как 2, и (1/3) вероятность того, что она получит 1.

Если мы вставим два элемента, вероятность того, что у нас будет коллизия, - это вероятность того, что оба входа оцениваются в 2 плюс вероятность того, что оба оцениваются в 1. Это:

(2/3)(2/3) + (1/3)(1/3) = 4/9 + 1/9 = 5/9

Таким образом, вероятность того, что любые два входа НЕ БУДУТ столкновения, равна 1 - (5/9)

или 4/9.

Answer 2

Для небольшого понимания того, почему этот шаблон имеет место, рассмотрим все классы эквивалентности mod 3, то есть { 0, 1, 2 }.

Если x mod 3 = 0 затем x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (0 * 0) mod 3 = 0 по распределительной эквивалентности, так x^2 + 1 mod 3 = 1

Если x mod 3 = 1 затем x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (1 * 1) mod 3 = 1, так x^2 + 1 mod 3 = 2

Если x mod 3 = 2 затем x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (2 * 2) mod 3 = 1, так x^2 + 1 mod 3 = 2

Это все еще не на 100% формально, и это неуклюжий пример исчерпания, но это дает вам представление, почему этот шаблон подходит для объединения натуральных чисел { 0 }. Я также хотел бы, чтобы я был более знаком с математическим форматированием в стеке. Предположим, пришло время поднять мета?:)