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

Question

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

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

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

Answer 1

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

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

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

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