从链式哈希表中有效地选择随机元素？

Question

只是为了练习(而不是作为作业作业)，我一直试图解决这个问题(CLRS，第三版，练习11.2-6)：

假设我们将n个密钥存储在一个m大小的哈希表中，通过链来解决冲突，并且我们知道每个链的长度，包括最长链的长度L。描述一个从哈希表中的键中随机选择一个键并在预期时间O(L * (1 + m/n))返回它的过程。

到目前为止，我认为每个密钥被返回的概率是1/ n，如果我们试图在1到n之间得到一个随机值x，然后尝试先按桶排序，然后沿着桶中的链排序，则需要O(m)逐个遍历桶找到正确的桶，O(L)时间才能在链中得到正确的密钥。

Answer 1

重复以下步骤，直到返回元素为止：

• 随机选择一个桶。设k是桶中的元素数。
• 从1 ... L中随机一致地选择p。如果是p <= k，则返回桶中的pth元素.

应该清楚的是，该过程随机一致地返回一个元素。我们对放置在二维数组中的元素进行拒绝采样。

每个桶的预期元素数是n / m。抽样尝试成功的概率是(n / m) / L。因此，查找桶所需的预期次数是L * m / n。加上从桶中检索元素的O(L)成本，预期的运行时间是O(L * (1 + m / n))。