只是为了练习(而不是作业作业),我一直在试图解决这个问题(CLRS,第3版,练习11.2-6)：
Suppose we have stored n keys in a hash table of size m,with
collisions resolved by chaining,and that we know the length of each
chain,including the length L of the longest chain. Describe a
procedure that selects a key uniformly at random from among the keys
in the hash table and returns it in expected time O(L * (1 + m/n)).
到目前为止,我认为每个键的返回概率是1 / n.如果我们尝试得到1到n之间的随机值x,并尝试按顺序首先按桶排序,然后沿着桶中的链排列找到第x个密钥,那么将通过进行O(m)找到合适的桶通过桶逐个和O(L)时间获得链中的正确键.
