Эффективный выбор случайного элемента из цепочки хэшей?

Question

Только для практики (а не в качестве домашнего задания) Я пытался решить эту проблему (КСПС, 3-е издание, упражнение 11.2-6):

Предположим, что мы храним п ключей в хэш-таблице размер m, с столкновений, разрешенных цепью, и что мы знаем длину каждой цепи , включая длину L самой длинной цепи. Опишите процедуру , которая произвольно выбирает ключ из числа ключей в хеш-таблице и возвращает его в ожидаемое время O (L * (1 + m/n)).

То, что я думал до сих пор, состоит в том, что вероятность возврата каждой клавиши равна 1/n. Если мы попытаемся получить случайное значение x от 1 до n и попытаемся найти xth ключ в последовательности, сначала отсортированной по ведро, а затем по цепочке в ковше, тогда для поиска правильного ведра потребуется O (m) через ведра один за другим и время O (L), чтобы получить правильный ключ в цепочке.

Answer 1

Повторите следующие шаги, пока элемент возвращается:

• Произвольно выбрать ведро. Пусть k - количество элементов в ковше.
• Выберите p равномерно в случайном порядке от 1 ... L. Если p <= k, то верните p-й элемент в ковше.

Должно быть ясно, что процедура возвращает элемент равномерно случайным образом. Мы как бы применяем выборку отбраковки к элементам, помещенным в 2D-массив.

Ожидаемое количество элементов на ковш n/m. Вероятность успешной попытки выборки - (n/m)/L. Таким образом, ожидаемое количество попыток поиска ковша L * m/n. Вместе с затратами на извлечение элемента из ковша ожидается ожидаемое время работы O(L * (1 + m/n)).