只是为了练习(而不是作为家庭作业),我一直在尝试解决这个问题(CLRS,第 3 版,练习 11.2-6):
假设我们在大小为 m 的哈希表中存储了 n 个键,通过链接解决冲突,并且我们知道每个链的长度,包括最长链的长度 L。描述一个从哈希表的键中均匀随机选择一个键并在预期时间 O(L * (1 + m/n)) 内返回它的过程。
到目前为止,我认为每个键被返回的概率是 1/n。如果我们尝试获取一个介于 1 到 n 之间的随机值 x,并尝试先按桶排序,然后沿着桶中的链依次找到第 x 个键,则需要 O(m) 才能找到正确的桶通过一个一个桶和 O(L) 时间来获得链中的正确密钥。