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