Эффективный выбор случайного элемента из цепочки хеш-таблицы?
Просто для практики (а не как домашнее задание) я пытался решить эту проблему (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)).
