在二选散列(带链接)中，选择两个随机散列函数 h1，h2 将 n 个键散列到 m 个位置。过程是这样的:
依次插入所有 n 个键，通过对每个键 x、两个哈希函数求值，并将键添加到由 h1(x)、h2(x) 索引的较短列表中。设 Y 为 (x, x') 对的数量，使得它们最终出现在同一个链表中。 Y(E[Y]) 的期望值是多少？
统一独立地假设h1,h2散列键
最佳答案
我怀疑这个问题是否有一个干净的解析解。
但是对于大量桶的情况，生成数值近似值是非常容易处理的。令 x 为存储的键数与桶数之间的比率。假设 f<sub>n</sub>(x) 是具有 n 个键的桶的预期部分，F<sub>n</sub>(x) 是具有最多 n 个键的桶的预期部分。
然后是简单的 F<sub>n</sub>(x) = f<sub>0</sub>(x) + f<sub>1</sub>(x) + ... + f<sub>n</sub>(x) 。并且 f<sub>n</sub>'(x) 是使用键添加一个大小为 n-1 的桶将被添加到的概率，减去使用键添加一个大小为 n 的桶将被添加到的概率。
将大小为 n 的桶添加到下一个的概率是第一个哈希函数选择大小为 n 的桶且第二个选择大小至少为 n 的桶的概率加上第一个哈希函数选择大小的概率一个大小大于 n 的桶，第二个选择一个大小为 n 的桶。选择大小大于 n 的桶的概率只是 1 - F<sub>n</sub>(x) 。所以这个概率是 f<sub>n</sub>(x)(1 - F<sub>n-1</sub>(x)) + (1 - F<sub>n</sub>(x))f<sub>n</sub>(x) 。
这就是 f<sub>n</sub>'(x) = f<sub>n-1</sub>(x)(1 - F<sub>n-2</sub>(x)) + (1 - F<sub>n-1</sub>(x))f<sub>n-1</sub>(x) - f<sub>n</sub>(x)(1 - F<sub>n-1</sub>(x)) - (1 - F<sub>n</sub>(x))f<sub>n</sub>(x) 。这是一个可怕的非线性方程组，没有必要期待任何好的解决方案。但它也适用于 http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods 并且您不需要太多的项来获得准确的估计，因为装满桶的部分比指数下降得更快。 (要了解原因，请说服自己，如果 n 明显大于 x，则 f<sub>n+1</sub>'(x) 大约为 f<sub>n</sub><sup>2</sup>(x)。小项的重复平方意味着从 f<sub>n</sub>(x) < 0.01 到 f<sub>n</sub>(x) < 0.00000001 有非常急剧的衰减。)
关于algorithm - 两种选择哈希中的预期碰撞对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27304912/