从链式散列表中有效地选取一个随机元素？

Question

只是为了实践（而不是作为一个家庭作业），我一直在试图解决这个问题（CLRS，第3版，运动11.2-6）：

在哈希表假设我们有存储N个按键大小为m，其中 通过链接解决了碰撞，并且我们知道每个链的长度，包括最长链的长度L.描述从散列表中的密钥 中随机一致地选择一个密钥并在期望的时间O（L *（1 + m/n））中返回它的过程 。

我到目前为止认为每个密钥返回的概率是1/n。如果我们试图得到1到n之间的一个随机值x，并尝试按照先按桶排序然后沿着桶中的链找到第x个键，然后用O（m）通过去找到正确的桶通过逐个桶和O（L）时间来获得链中的正确密钥。

Answer 1

重复返回下列步骤，直到一个元素：

• 随机选择一个桶。假设k是存储桶中的元素数量。
• 从1 ... L统一随机选择p。如果p <= k则返回桶中的p th元素。

应该清楚的是，该过程随机返回一个元素。我们对排列在二维数组中的元素应用拒绝采样。

每个桶的元素预期数量为n/m。采样尝试成功的概率是(n/m)/L。因此需要查找桶的尝试次数为L * m/n。与从桶中检索元素的O(L)成本一起，预计运行时间为O(L * (1 + m/n))。