在两次选择散列中期望的一对冲突

Question

在两次选择散列（与链接）中，选择两个随机散列函数h1，h2来散列n个键到m个位置。过程如下：

通过评估每个键x，两个散列函数并将键添加到由h1（x），h2（x）索引的较短列表中，顺序插入所有n个键。设Y是对（x，x'）的数目，使它们最终在同一个链表中。 Y（E [Y]）的期望是什么样的？

假设H1，H2的混杂键均匀且独立地

Answer 1

我怀疑有一个干净的解析解决这个问题。

但是，对于大量桶的情况产生数值近似是非常容易处理的。假设x是存储的密钥数量和桶的数量之间的比率。假设​​是桶的预期部分，n键和Fn(x)是桶的预期部分，最多为n键。

然后平凡Fn(x) = f0(x) + f1(x) + ... + fn(x)。而且fn'(x)是用一个关键字添加一个大小为n-1的存储桶将被添加到的概率，减去用关键字添加的大小为n的存储桶的概率。

该大小n的铲斗将到下一个添加的概率是该第一哈希函数选择尺寸n的桶和所述第二选择大小至少n之一，加的概率，所述第一哈希函数的概率选择一个尺寸大于n的桶，第二个选择尺寸为n。选择大于n的桶的概率简单地为1 - Fn(x)。所以这个概率是fn(x)(1 - Fn-1(x)) + (1 - Fn(x))fn(x)。

这使得fn'(x) = fn-1(x)(1 - Fn-2(x)) + (1 - Fn-1(x))fn-1(x) - fn(x)(1 - Fn-1(x)) - (1 - Fn(x))fn(x)。这是一个非常可怕的非线性方程组，并且没有必要期待任何好的解决方案。但它也适用于http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods，并且您不应该需要太多的术语来获得准确的估计值，因为大量填充的桶的下降速度比指数快。 （要知道为什么，说服自己，如果n比x显著较大，那么fn+1'(x)约为fn2(x)。小方面的重复平方意味着从fn(x) < 0.01一个非常急剧下降到fn(x) < 0.00000001）