问是否有一个简单的公式来计算密码散列函数中有多少输入产生相同的输出，即输入大于输入？

EN

产生相同输出的平均输入数显然是输入数除以输出数，即数量。

在这种情况下。为了进一步澄清，如在注释中，这里的“平均”是在集合(2^{128})^(2^{384})可能的函数从384-bit位字符串到128位位字符串，因为假设是我们一致地绘制这些函数之一随机。

由于一个好的哈希函数可以建模为一个随机映射，我们可以说更多关于这一点，基于垃圾桶-球范式。

要开始，请参阅维基百科获得更多细节这里。在他们的定义中，我们将有m=2^{384}和n=2^{128}.，例如，一旦m>n \ln n，所有的输出都被一些输入方法1所达到的概率。这就是所谓的优惠券收集器问题，请查一下。我们也可以用大多数的球、最少的球等来估计垃圾箱的负荷。拉布在网上有一篇论文，标题是“垃圾箱中的球:一个严密的分析”，上面有更多的技术细节。

在注释中，输入数的分布导致一个固定的散列输出值，可以使用泊松近似，然后用平均\mu=2^{256}和标准差\sigma=2^{128}.的高斯近似。

请注意，这只是一个模型，虽然通常非常精确，因为任何给定的哈希函数都是确定性的。

编辑：

Raab和Steger available 这里的论文中也有关于有多少输入映射到最流行的哈希输出的结果。这里有m=n^3和n=2^{128}.，因此我们在定理1的最后一个例子中，m比n大，即m\geq c n (\ln n)^3. (事实上，自从\log_2(\ln 2^{128})^3 \approx 19.4.以来，甚至m>2^{148}也会把我们放到这个情况中)。

应用这一结果，我们可以看到，最大载荷的概率很高，等于

在那里，o(1)很快就会变成零。快速计算

作为bin中期望的最大负载(即固定哈希输出)。有趣的是，与Ilmari在评论中给出的近似值相比，这个值大约在2^{3.5} \sigma \approx 11.3 \sigma。