MIT Lecture WRONG? Анализ открытой адресации в хешировании

Question

В следующей лекции MIT: https://www.youtube.com/watch?v=JZHBa-rLrBA в 1:07:00, профессор научил вычислять количество зондов при безуспешном поиске.

Но мой метод расчета не соответствует его. Мой ответ:

Количество зондов =

м = нет. слотов в хеш-таблице

n = нет. элементы (ключи)

Пояснение:

1. хеш-функция может поразить пустой слот с вероятностью м-н/м.

2. Или он может попасть в предварительно занятый ключевой слот с вероятностью n/m.

3. Теперь в случае 2 нам придется снова вызвать хэш-функцию, и есть две возможности: (i) Мы получаем слот без ключа с вероятностью (m-n)/(m-1). (ii) Мы получаем слот с ключом с вероятностью (n-1)/(m-1).

4.Now повторить случай 3, но с разной вероятностью, как показано на рисунке

Почему я получаю разные ответы. Что с этим не так?

Answer 1

Проблема заключается в том, чтобы найти ожидаемое количество зондов, которые необходимо выполнить в хеш-таблице.

Вы должны сделать это, несмотря ни на что, поэтому у вас есть 1 для начала. Тогда есть вероятность, что вы столкнулись с вероятностью n/m. Вы получили это право в своих объяснениях.

Если у вас есть столкновение, вы должны сделать еще один пробник (и, возможно, даже больше). И так далее, так что ответ является один профессор получает:

1 + (n/m)(1 + ((n - 1)/(m - 1))(1 + ...)) 

Вы не размножаются с вероятностью того, что вы получите пустой слот. Вы умножаете вероятность не получения пустого слота с количеством операций, которые вы должны выполнить, если вы не получите пустой слот (1, потому что в этом случае вам нужно сделать хотя бы еще один пробник).

Не имеет смысла умножать вероятность получения открытого слота с вероятностью не получить его, как вы делаете. Помните, что мы хотим найти ожидаемое количество зондов, которые нам нужно сделать. Таким образом, вы умножаете количество операций (зондов) на каждом шаге с вероятностью того, что вы не получите то, что вы хотели бы получить (пустой слот), потому что если это событие произойдет, тогда нам нужно будет сделать больше операции (пробники), иначе мы закончили.

Это объясняется очень хорошо в лекции, с которой вы связались, если внимательно следить до конца.