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

Просто для практики (а не как домашнее задание) я пытался решить эту проблему (CLRS, 3-е издание, упражнение 11.2-6):

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

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

Ответ 1

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

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

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

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