Хеширование в структурах данных

Question

Рассмотрим хеш-таблицу с n сегментами, где внешняя (переполненная) цепочка используется для разрешения коллизий. Хеш-функция такова, что вероятность того, что значение ключа хешируется в конкретный сегмент, равна 1 / n. Первоначально хеш-таблица пуста, и в нее вставлено K различных значений.

1. Какова вероятность того, что корзина номер 1 пуста после K-й вставки?
2. Какова вероятность того, что ни в одном из К не произошло столкновения? Вставки?
3. Какова вероятность того, что первое столкновение произойдет в K-й вставке?

Answer 1

1. Вероятность того, что корзина 1 пуста после ОДНОЙ вставки, равна (n−1)/n. Это вероятность того, что первый элемент не хэшируется в корзину 1. Событие того, что он пустой после ДВУХ вставок, определяется как «первый элемент пропущенный сегмент 1» И «2-й элемент пропущенный сегмент один», равный (n - 1) * (n - 1) / n * n. С этим, я надеюсь, вы сможете вычислить вероятность того, что корзина опустеет после K вставок.

2. Для K = 1 это 1. Для K = 2 второй предмет должен пропустить ведро первого предмета. Так что у него есть n − 1 мест, куда он может безопасно отправиться. Следовательно, вероятность успеха составляет (n − 1) / n. А как насчет третьего пункта? У него есть только 1014 мест, куда он может пойти. Таким образом, вероятность для K = 3 равна (n − 1) * (n - 2) / n * n. Вы можете обобщить. Будьте осторожны с делом K > n.

3. Как только вы проработаете детали первых двух частей, вы, вероятно, сможете добиться прогресса и в этой.

   Подсказка: первое столкновение происходит на k -ой вставке, если (i) первые k−1 вставки не сталкивались (см. 2) и (ii) k -ая вставка вызывает столкновение (см. дополнение 2).

Дайте мне знать, если вы сможете выяснить все три ответа. В противном случае я добавлю более подробную информацию.