14

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

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

到目前为止，我认为每个键被返回的概率是 1/n。如果我们尝试获取一个介于 1 到 n 之间的随机值 x，并尝试先按桶排序，然后沿着桶中的链依次找到第 x 个键，则需要 O(m) 才能找到正确的桶通过一个一个桶和 O(L) 时间来获得链中的正确密钥。

4

1 回答 1

23

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

  • 随机选择一个桶。设k为桶中元素的数量。
  • p从 中随机均匀选择1 ... L。如果p <= k则返回p桶中的第 th 个元素。

应该清楚的是，该过程随机均匀地返回一个元素。我们有点将拒绝采样应用于放置在二维数组中的元素。

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

于 2011-12-25T17:29:44.953 回答