插入多少次发生哈希冲突：拉马努金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 函数为一个和式，定义为 $Q(N) = \sum\limits_{k=1}\limits^{N}\frac{N!}{(N-k)!N^{k}}$，该和式中的被加项为关于 k 和 N 的二元函数 $f(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$ 对以上和式的增长速度都很重要。例如，考虑 $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 也对其进行了研究。该分布的公式为 $f(k, N) = \frac{N!}{(N-k)!N^{k}}$。

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

$$Q(N) = \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}})$$

证明

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

$$\begin{align} \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{align}$$

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

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

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

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

$$\begin{align} \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{align}$$

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

$$\begin{align} \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{align}$$

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

• (1) $O(f + g) = O(f) + O(g)$
• (2) $f(x) = 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})$ 也是不充分的，比如取 $k = 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 较小的情况，也就是 $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}}) \\$$

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

另一方面，$x \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 增加而减小，因此有 $k \geq k_{1}$ 时，有：

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

另一方面 $k \geq k_{1}$ 时，$e^{-\frac{k^{2}}{2N}}$ 也是指数级的（这里需要 $k > \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 分布 $f(k, N) = \frac{N!}{(N-k)!N^{k}}$ 的二元渐进性的分析，再结合使用拉普拉斯方法对和式的估计过程，可以得到拉马努金 Q 函数 $Q(N) = \sum\limits_{k=1}\limits^{N}f(k, N)$ 的渐近估阶。

在后续介绍拉普拉斯方法的文章中再来详细展开这一步的推导过程，这里我们直接给出结果：$N\rightarrow \infty$ 时，$Q(N) = \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$ 表示第一次冲突前已插入的数据条数。上述概率给出的正是 $P(X \geq N)$，由于数组长度为 $M$，因此当 $k > M$ 时，$P(X \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)!}$$

而拉马努金 Q 函数为 $Q(M) = \sum\limits_{k=1}\limits^{M}\frac{M!}{M^{k}(M-k)!}$，与上式相比仅求和范围少了 $k=0$，因此结果就是 $C_{M} = 1 + Q(M)$。

由拉马努金 Q 函数的渐近估阶得到最终结果：

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

总结

本文我们解决了第一次发生哈希冲突时，平均插入了多少数据的问题。其结果正是拉马努金 Q 函数 $Q(N)$。

$Q(N)$ 是一个和式，具体为 $Q(N) = \sum\limits_{k=1}\limits^{\infty}f(k, N)$，本文我们详细推导了 $f(k, N)$ 的渐近估阶，其推导过程是处理二元渐进性非常有代表性的操作，有了这个例子，以后再遇到二元渐近分析的问题，思路可以仿照本例。

在此前解决冒泡排序平均扫描趟数的问题中，我们接触过拉马努金 Q 函数 $Q(N)$，当时我们直接使用了 $Q(N)$ 的渐近估阶的结论。本文我们前进了一步，完成了 $Q(N)$ 中的被加项 $f(k, N)$ 的二元渐近分析。

至此拉马努金 Q 函数 $Q(N)$ 的渐近估阶就完成了一半，后续的分析用到了拉普拉斯方法，这也是渐近分析的一个经典手法，后续再跟大家探讨。

---