插入多少次发生哈希冲突：拉马努金Q分布与二元渐近分析

本文主要是介绍插入多少次发生哈希冲突：拉马努金Q分布与二元渐近分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

摘要: 拉马努金 Q 函数及其在算法分析中的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们继续讨论算法分析中的问题。

在哈希算法的分析中，哈希冲突是最受关注的问题。考虑有一个长度为 $M$ 的数组作为哈希表存放数据的容器，然后一个一个地往里插入数据，假设哈希函数将每条数据随机地映射到 $[1.. M]$ ，问：在第一次哈希冲突发生之前，已经插入了多少条数据，记已插入数据的期望为 $C_{M}$ 。

首先给出结论，当 $M\rightarrow\infty$ 时，有：

$C_{M} = \sqrt{\frac{\pi M}{2}} + O(1)$

为了推导以上结论，需要用到拉马努金Q函数的相关结论。在上一篇文章冒泡排序平均需要跑多少趟：拉马努金Q函数初探中，我们接触到了拉马努金 Q 函数，但是并没有关注而是直接引用了相关结论。本文我们深入探讨一下。

拉马努金 Q 函数为一个和式，定义为 $\sum\limits_{k=1}\limits^{N}\frac{N!}{(N-k)!N^{k}}$ ，该和式中的被加项为关于 k 和 N 的二元函数 $\frac{N!}{(N-k)!N^{k}}$ 。 $Q (N)$ 的渐近分析结论的推导非常冗长，本文我们完成第一步，也就是对 $f (k, N)$ 的渐近分析。

由于渐近分析的对象 $f (k, N)$ 是个二元函数，因此我们处理的是二元渐进性的问题，而拉马努金 Q 分布是算法分析中处理二元渐进性的非常有代表性的例子，因此推导过程非常经典。以后遇到其它二元渐近分析的问题时，解决方案的框架类似。

有了 $f (k, N)$ 的二元渐近分析结果， $Q (N)$ 的渐近分析可以通过拉普拉斯方法得到，这一步的推导过程我们在以后介绍拉普拉斯方法的文章中再来完成，本文我们直接给出结果。然后基于该结果，立即就可以得到前面提到的关于哈希冲突问题的结论。

二元渐进性

在逼近和式的时候，经常会出现被加数既依赖于求和下标 $k$ ，又依赖于渐近增长的大小参数 $N$ 的情况，也就是被加数是一个 $k$ 和 $N$ 的二元函数，类似于下面这样的和式：

$\sum\limits_{k=0}\limits^{N}f(k, N)$

$f$ 中的 $k$ 和 $N$ 对以上和式的增长速度都很重要。例如，考虑 $\frac{k^{N}}{k!}$ ，当固定 $k$ 时 $f (k, N)$ 在 $N\rightarrow\infty$ 时以指数量级增大，当固定 $N$ 时， $f (k, N)$ 在 $k\rightarrow\infty$ 时以指数量级减小。这种情况下 $N\rightarrow\infty$ 时以上和式的渐近估阶就不容易了。

二项式系数 $\binom{N}{k}$ 和拉马努金 Q 函数是在算法分析中最常见的二元函数，这两个函数的二元渐进性关系到很多算法的分析。本文我们看拉马努金 Q 函数的二元渐进性问题，二项式系数的二元渐进性问题以后我们再来看。

拉马努金 Q 分布

拉马努金 Q 分布最早由拉马努金研究，后来由于该分布在算法分析中有很多应用，Knuth 由对其进行了研究。该分布的公式为 $\frac{N!}{(N-k)!N^{k}}$ 。

将以上分布对 $k=0,1,\cdots,N$ 求和，就是拉马努金 Q 函数：

$\sum\limits_{k=1}\limits^{N}\frac{N!}{(N-k)!N^{k}}$

在概率论中，该函数也是我们熟知的生日函数：要找到具有相同生日的两个人， $Q (365) + 1$ 即为我们所需的期望试验次数。

为了估计 $Q (N)$ ，首先要做的是在当 $N\rightarrow \infty$ 时，对所有 $k$ 精确地估计出 $f (N, k)$ 的值。首先给出定理结论如下，然后我们完整证明该定理，从证明过程中我们可以看到涉及到 $k$ 和 $N$ 两个变量的二元渐进性问题的讨论方式，这也是本文的核心内容。

定理(Ramanujan Q-分布)

当 $N\rightarrow\infty$ 时，对于 $k = o(N^{2/3})$ 有相对误差界：
$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}}(1 + O(\frac{k}{N}) + O(\frac{k^{3}}{N^{2}}))$
对于所有的 $k$ ，有绝对误差界：
$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}} + O(\frac{1}{\sqrt{N}})$

证明

首先处理 $\frac{N!}{(N-k)!N^{k}}$ ：

$\begin{aligned} \frac{N!}{(N-k)!N^{k}} &= \frac{N(N-1)(N-2)\cdot\cdot\cdot(N-k+1)}{N^{k}} \\ &= 1\cdot(1 - \frac{1}{N})(1 - \frac{2}{N})\cdot\cdot\cdot(1 - \frac{N-(k-1)}{N}) \\ &= \exp(\ln(1 - \frac{1}{N})(1 - \frac{2}{N})\cdot\cdot\cdot(1 - \frac{N-(k-1)}{N})) \\ &= \exp(\sum\limits_{j=1}\limits^{k-1}\ln(1 - \frac{j}{N})) \\ \end{aligned}$

然后对于 $k$ 与 $N$ 不同的关系，分别分析。

对于 $k = o (N)$ ，取 $-\frac{j}{N}, 1 \leq j < k$ ，有 $\rightarrow 0$ ，因此由 $\ln(1 + x)$ 在 $x = 0$ 的泰勒展开有：

$ln(1 + x) = x + O(x^{2})$

对 $1,2,\cdots,k-1$ 求和，并应用自然数幂和公式后，得：

$\begin{aligned} \frac{N!}{(N-k)!N^{k}} &= \exp(\sum\limits_{j=1}\limits^{k-1}\ln(1 - \frac{j}{N})) \\ &= \exp(\sum\limits_{j=1}\limits^{k-1}(-\frac{j}{N} + O(\frac{j^{2}}{N^{2}}))) \\ &= \exp(-\frac{k(k-1)}{2N} + O(\frac{k^{3}}{N^{2}})) \end{aligned}$

进一步地，对于 $k = o(N^{2/3})$ ，有 $\frac{k}{2N} + O(\frac{k^{3}}{N^{2}}) \rightarrow 0$ ，因此由 $e^{y}$ 在 $y = 0$ 的泰勒展开，得：

$\begin{aligned} \frac{N!}{(N-k)!N^{k}} &= \exp(-\frac{k(k-1)}{2N} + O(\frac{k^{3}}{N^{2}})) \\ &= \exp(-\frac{k^{2}}{2N})\exp(\frac{k}{2N} + O(\frac{k^{3}}{N^{2}})) \\ &= e^{-\frac{k^{2}}{2N}}(1 + O(\frac{k}{2N} + O(\frac{k^{3}}{N^{2}})) \\ &= e^{-\frac{k^{2}}{2N}}(1 + O(\frac{k}{2N}) + O(\frac{k^{3}}{N^{2}})) \\ \end{aligned}$

其中最后一步用到大 O 符号的以下两条运算性质（参考潘承洞《阶的估计基础》）：

(1) $O (f + g) = O (f) + O (g)$
(2) $O(\phi), \phi = O(\psi) \Rightarrow f(x) = O(\psi)$

于是就得到的定理的第一条关于相对误差界结论，当 $k = o(N^{2/3})$ 时有：

$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}}(1 + O(\frac{k}{N}) + O(\frac{k^{3}}{N^{2}})) \\$

这里需要注意，上式中两个大 O 项都应该保留，以便覆盖 k 值的范围。原因在于大 O 符号中同时有 k 和 N，对于 k 和 N 不同的关系，这两个大 $O$ 哪个的阶更大是不知道的，例如：

仅有 $O(\frac{k^{3}}{N^{2}})$ 是不充分的，比如取 $k = O (1)$ ， $O(\frac{k^{3}}{N^{2}})$ 的结果等于 $O(\frac{1}{N^{2}})$ ，但 $O(\frac{k}{N})$ 的结果是 $O(\frac{1}{N})$ ，更大。
仅有 $O(\frac{k}{N})$ 也是不充分的，比如取 $O(N^{\frac{3}{5}})$ ， $O(\frac{k}{N})$ 的结果等于 $O(\frac{1}{N^{2/5}})$ ，但 $O(\frac{k^{3}}{N^{2}})$ 的结果是 $O(\frac{1}{N^{1/5}})$ ，更大。

通过这个定理的推导，以及结果公式中两个大 O 项在 k 与 N 不同关系下谁的阶更大的讨论，我们认识到对于二元渐进性，必须要仔细处理。

下面推导定理的第二条关于绝对误差界的结论。

首先考虑 k 较小的情况，也就是 $\leq k_{0}$ ，其中 $k_{0}$ 稍小于 $O(N^{2/3})$ ，不妨取 $k_{0} = N^{3/5}$ 。这样就有 $k = o(N^{2/3})$ ，前面推导的相对误差界的结论可以用，因此有：

$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}} + e^{-\frac{k^{2}}{2N}}O(\frac{k}{N}) + e^{-\frac{k^{2}}{2N}}O(\frac{k^{3}}{N^{2}}) \\$

记 $\frac{k}{\sqrt{2N}}$ ，于是上式第二项可以写为 $e^{-x^{2}}O(\frac{1}{\sqrt{N}})$ ，第三项可以写为 $x^{3}e^{-x^{2}}O(\frac{1}{\sqrt{N}})$ 。

另一方面， $\geq 0$ 时， $xe^{-x^{2}}$ 以及 $x^{3}e^{-x^{2}}$ 均有界，因此 $xe^{-x^{2}} = O(1)$ 、 $x^{3}e^{-x^{2}} = O(1)$ 。

$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}} + O(\frac{1}{\sqrt{N}})$

当 k 比较大时，即 $k > k_{1}$ ，其中 $k_{1}$ 稍大于 $\sqrt{N}$ 即可，还是不妨设 $k_{1} = N^{3/5}$ 。当 $k = k_{1}$ 时，前面的结论仍然有效：

$\frac{N!}{(N-k_{1})!N^{k_{1}}} = e^{-\frac{N^{1/5}}{2}} + O(\frac{1}{\sqrt{N}})$

上式中， $e^{-\frac{N^{1/5}}{2}}$ 是指数级的，且其系数随着 k 增加而减小，因此有 $\geq k_{1}$ 时，有：

$\frac{N!}{(N-k)!N^{k}} = O(\frac{1}{\sqrt{N}})$

另一方面 $\geq k_{1}$ 时， $e^{-\frac{k^{2}}{2N}}$ 也是指数级的（这里需要 $\sqrt{N}$ ），于是上式可以写为：

$\frac{N!}{(N-k)!N^{k}} = e^{-\frac{k^{2}}{2N}} + O(\frac{1}{\sqrt{N}})$

综合上述 k 较小和 k 很大两方面，定理中第二部分的绝对误差界成立，即上式。

上述分析中，我们取了 $k_{0} = k_{1} = N^{3/5}$ ，这里的 $k_{0} = N^{3/5}$ 的取值并不重要，它只需要足够小，使得相对误差界对 $k < k_{0}$ 成立；同样地， $k_{1} = N^{3/5}$ 的具体取值也不重要，它只需要足够大，使得对 $k > k_{1}$ 时， $e^{-\frac{k^{2}}{2N}}$ 为指数级的即可。

$\Box$

有了上述拉马努金 Q 分布 $\frac{N!}{(N-k)!N^{k}}$ 的二元渐进性的分析，再结合使用拉普拉斯方法对和式的估计过程，可以得到拉马努金 Q 函数 $\sum\limits_{k=1}\limits^{N}f(k, N)$ 的渐近估阶。

在后续介绍拉普拉斯方法的文章中再来详细展开这一步的推导过程，这里我们直接给出结果： $N\rightarrow \infty$ 时， $\sqrt{\frac{\pi N}{2}} + O(1)$ 。

哈希冲突前平均已插入数据量

回到文章开头的问题。考虑有一个长度为 $M$ 的数组作为哈希表存放数据的容器，然后一个一个地往里插入数据，假设哈希函数将每条数据随机地映射到 $[1.. M]$ ，问：在第一次哈希冲突发生之前，已经插入了多少条数据，记已插入数据的期望为 $C_{M}$ 。

第 1 次插入可以在 $M$ 个位置中随便选，肯定不会发生冲突；第 2 次插入就有可能发生冲突了，冲突概率 $\frac{1}{M}$ ；第 3 次插入时，数组中已有 2 哥位置被占了，此时插入，冲突的概率就变成了 $\frac{2}{M}$ 。

以此类推，在第 $N$ 次插入时，数组中已有 $N - 1$ 个位置被占，此时插入，冲突的概率就是 $\frac{N-1}{M}$ 。因此前 $N$ 次插入均未发生冲突的概率为：

$\prod\limits_{k=1}\limits^{N}(1 - \frac{k-1}{M}) = \frac{N!}{M^{N}}\binom{M}{N}$

记 $X$ 表示第一次冲突前已插入的数据条数。上述概率给出的正是 $\geq N)$ ，由于数组长度为 $M$ ，因此当 $k > M$ 时， $\geq k) = 0$ ，再由数学期望的性质，有：

$C_{M} = E(X) = \sum\limits_{k=0}\limits^{\infty}P(X \geq k) = \sum\limits_{k=0}\limits^{M}\frac{k!}{M^{k}}\binom{M}{k} = \sum\limits_{k=0}\limits^{M}\frac{M!}{M^{k}(M-k)!}$