布谷鸟哈希

布谷鸟哈希学习笔记。

布谷鸟哈希综述

由生日悖论可知，往大小为 $m$ 的哈希表中插入 $O\left(\sqrt{m}\right)$ 级别个哈希键值，冲突就几乎无法避免了，无法再往哈希表中插入元素。而布谷鸟哈希（Cuckoo Hash）是一种可以减少冲突可能性的哈希，它可以将大小为 $m$ 的哈希表空间利用率提高到 $m/2$ 以上，即插入 $m/2$ 个哈希键值或更多都不会产生无法插入的情况。

在布谷鸟哈希中，每个元素 $v$ 有两个不同的哈希函数 $h_1(v),h_2(v)$。将 $v$ 插入哈希表时，我们分别检查哈希表中的 $h_1(v),h_2(v)$ 位置是否为空，如果有至少一个为空，则直接选一个位置插入；如果都非空，则任意选取一个位置，将原来这个位置中的值踢出，将 $v$ 插入到这个位置中，然后对踢出的那个值再进行插入过程，不断执行如上过程，直到所有值都被安放好。

但不是在所有的时候都可以安放好的，如果替换关系成环（即一开始插入的值又在同一个地方被踢出去），那么将所有元素都安放好是不可能的。这时候我们选取新的哈希函数 $h_1',h_2'$，然后再将哈希表中的值重新插入一遍，这个便是布谷鸟哈希的 rehash 操作。值得注意的是，rehash 操作可也能嵌套。在具体实现中，为了方便，我们通常不去判断是否成环，而是设定一个阈值 $K$，如果插入时的替换次数超过了 $K$，我们就认为插入失败，转而开始执行 rehash 操作。

布谷鸟哈希的删除和查找操作比较简单，只需要查询对应两个哈希值位置有无值即可。

小知识：此算法名称来源于布谷鸟的行为：新出生的布谷鸟会本能地将巢穴里的其他蛋踢开，推出鸟巢，以确保自己在鸟巢里可以独享宠爱。插入时的「踢出」行为与布谷鸟的行为相似。当然被踢出的值比被踢开的蛋待遇要好得多，至少它可以「活下来」。

算法的伪代码

设 $\mathcal U$ 为元素集合。而 $T$ 为整个哈希表，有编号为 $1,2,\ldots,|T|$ 的格子。$h_1,h_2$ 为两个哈希函数。

查找与删除操作的伪代码非常简单：

看代码就可以显然的看出查找与删除操作的时间复杂度都是 $O(1)$ 的。

插入操作最为特殊：

接下来我们重点分析插入操作的时间复杂度。

哈希函数组的假设

因为插入操作的复杂度依赖于哈希函数，所以我们要对哈希函数做一些限制（不然可以设计极端好或者极端差的哈希函数从而使得算法的复杂度失去意义）。

定义（$k$-Universal）：我们称一个哈希函数（哈希函数指的是这样的映射：$h:\mathcal U\to [T]$）组 $\mathcal H$ 是 $k$-Universal 的当且仅当：对于任意的 $k$ 个不同的 $x_1,x_2,\ldots,x_k\in \mathcal U$，以及任意的 $k$ 个值 $y_1,y_2\ldots,y_k\in [T]$，都有：

$\Pr_{h\in \mathcal H}[h(x_1)=y_1\wedge h(x_2)=y_2\wedge \ldots\wedge h(x_k)=y_k]\le \dfrac 1{|T|^k}$

在下面的分析中我们都假设我们选取的哈希函数是 $2K$-Universal 的，并且 $h_1,h_2$ 的选取是独立的。

装载参数与表扩容

设哈希表中目前填入了 $n$ 个元素，定义装载参数为：

$\alpha=\dfrac{n}{|T|}$

我们在进行整个过程的时候，我们要一直保持：

$\alpha< \dfrac 1{2+\delta}$

即一直保持：

$|T|> (2+\delta)n$

如果插入了一个元素后上述条件不满足了，我们就将哈希表的大小扩大为原来的两倍，重新选取哈希函数，然后把原来在表里的元素重新插入进去，这个操作被称为表扩容。

插入时产生的迭代序列

往哈希表里插入一个元素 $x$，则伪代码中第 $5$ 到 $14$ 行会产生一系列的「$x$」。这样产生的一个序列为迭代序列，并设这个序列具体为：$x_1=x,x_2,x_3,\ldots$，值得注意的是这样的序列长度最多为 $2K$，因为循环了 $K$ 轮，每轮产生两个元素，之后就会进入 ReHash。

如果先不管序列长度的限制，让其一直迭代下去，我们可以把序列分为三类：

1. 序列中的每个值都不同，这也蕴含着迭代会终止。
2. 序列中存在相同的元素，但是迭代会终止。
3. 序列中存在相同的元素，并且迭代不会终止。

第一种情况最好分析，直接放一张图解释。

第二种情况，我们假设序列中相同的两个元素是 $x_i,x_j\,(i<j)$，如果有多个这样的 $(i,j)$，取字典序最小的那个数对。可以注意到必然有 $x_{j+1}=x_{i-1},x_{j+2}=x_{i-2},\ldots,x_{j+i-1}=x_1=x$，即又绕了一圈回来。之后再迭代下去，知道在 $l$ 处碰到了一个空位置，插入进去。看下图可以辅助理解。

第三种情况与第二种类似，但是不同就是再度回到 $x$ 后，不断迭代下去还是找不到空的位置，最后又第三次碰到 $x$。那么这时候就开始循环了，$x$ 永远不可能找到一个位置可以安放。可以看下图辅助理解。

我们称一个序列 $x_1=x,x_2,\ldots,x_l$ 是坏的，当且仅当这个序列已经开始循环了，否则则称它是好的。那么有如下重要引理：

引理 $1$：插入迭代到第 $l$ 时，产生了一个迭代序列 $x_1=x,x_2,\ldots,x_l$。如果这个序列当前是好的，则必定存在一个长度 $p\ge l/3$ 的连续子序列 $x_q,x_{q+1},\ldots,x_{q+p-1}$，这个连续子序列满足内部元素两两不同且 $x_q=x_1=x$。

证明：如果 $x_1,\ldots,x_l$ 两两不同，则序列本身就是满足要求的连续子序列。

如果 $x_i=x_j\,(i<j)$（有多个 $(i,j)$ 则取字典序最小的），那分两种情况讨论：

若 $l<i+j$，则 $x_1=x,\ldots,x_{j-1}$ 两两不同，且 $x_1=x$。又有：$j-1\ge (i+j-1)/2\ge l/2> l/3$。所以这个就是满足要求的连续子序列。

而若 $l\ge i+j$，我们考虑两个连续子序列：$x_1,\ldots,x_{j-1}$ 与 $x_{i+j-1},\ldots,x_l$。由前文对迭代序列第二种情况的分析知这两个序列内部值都是两两不同的，且有 $x_1=x_{i+j-1}=x$。接下来我们证明至少有一个序列长度不小于 $l/3$。

两个子序列长度分别为 $j-1,l-i-j+2$，注意到 $l=(j-1)+(i-1)+(l-i-j+2)$。又因为有 $j-1>i-1$，所以若 $j-1>l-i-j+2$，则有 $3(j-1)>l$；反之若有 $j-1\le l-i-j+2$，则有 $3(l-i-j+2)\le l$。故至少有一个不小于 $l/3$。

得证。$\Box$

插入操作时间复杂度分析

有了这样一个引理的准备，我们可以着手开始分析插入操作的期望时间复杂度。先写出期望时间复杂度的表达式：

$\mathbb E_n(\text{Insert})=O\left(\sum_{i=1}^{2K}\Pr[|x|=i]\cdot i \right)+{\Pr}_n[\text{Insert Fail}]\cdot (\mathbb E_n(\text{ReHash})+\mathbb E_n(\text{Insert})),\\ \mathbb E_n(\text{ReHash})=\sum_{i=0}^{n-1}\mathbb E_i(\text{Insert})\le n\cdot \mathbb E_n(\text{Insert})$

其中 $n$ 表示当前哈希表中的元素个数（不算正在插入的这个元素）；而 $\mathbb E_n(\text{Insert}),\mathbb E_n(\text{ReHash}),{\Pr}_n[\text{Insert Fail}]$，分别表示当哈希表中的元素个数为 $n$ 时，插入操作的期望时间复杂度，ReHash 操作期望的时间复杂度，和插入操作失败的概率（即经过伪代码第 $5$ 行的 for 还没能插入的概率）；$|x|$ 表示迭代序列 $x$ 的长度。

显然 $\mathbb E_i(\text{Insert})$ 是递增的，所以有第二个式子的放缩。

可以发现把第二个式子直接代入第一个式子，就变成了只关于 $\mathbb E_n(\text{Insert})$ 的不等式。我们现在剩下的工作就是要分析大 $O$ 那一项与 ${\Pr}_n[\text{Insert Fail}]$。

迭代序列期望长度

我们先来分析大 $O$ 那一项，可以发现此项描述的就是迭代序列的期望长度。注意到：

$\sum_{i=1}^{2K}\Pr[|x|=i]\cdot i=\sum_{i=1}^{2K}\Pr[|x|\ge i]$

所以我们去考虑分析 $\Pr[|x|\ge i]$ 的上界。设 $V=$「$|x|\ge i$」，事件 $X=$「$x_1,\ldots,x_i$ 是好的」，事件 $Y=$「$x_1,\ldots,x_i$ 是坏的」。则：

$\Pr[V]=\Pr[V\wedge X]+\Pr[V\wedge Y]$

又注意到 $V\cap X=X,V\cap Y=Y$，故：

$\Pr[V]=\Pr[X]+\Pr[Y]$

接下来我们分别分析 $\Pr[X]$ 与 $\Pr[Y]$。

迭代序列是好的概率

我们先来分析 $\Pr[X]$。由引理 $1$ 知，好的迭代序列必然存在一个长度不小于 $i/3$ 的连续子序列 $b_1=x,b_2,\ldots,b_{i/3}$，且序列内部值两两不同。

如果 $b_1$ 是 $x$ 的第一次出现，则有：

$h_1(b_1)=h_1(b_2),h_2(b_2)=h_2(b_3),h_1(b_3)=h_1(b_4), \ldots \tag{1}$

而若 $b_1$ 是 $x$ 的第二次出现，则有：

$h_2(b_1)=h_2(b_2),h_1(b_2)=h_1(b_3),h_2(b_3)=h_2(b_4), \ldots \tag{2}$

$b$ 序列取值方式的上界为：

$1\cdot (n-1)\cdots (n-i/3+1)\le n^{i/3-1}$

选定了 $b$ 序列后，我们分析这个序列满足条件 $(1)$ 的概率。我们假设 $h_1,h_2$ 都是 $2K$-Universal 的，则显然 $h_1,h_2$ 也是 $i/3$-Universal 的。为了分析方便起见，我们令 $h_1$ 的值域为 $[1,|T|/2]$，$h_2$ 的值域为 $[|T|/2+1,|T|]$。则这个概率为：

$\Pr[h_1(b_1)=h_1(b_2)\wedge h_2(b_2)=h_2(b_3) \wedge \ldots]\\ =\sum_{y_1,y_3,y_3,\ldots\in[1,|T|/2]}\Pr[h_1(b_1)=h_1(b_2)=y_1\wedge h_1(b_3)=h_1(b_4)=y_3 \wedge \ldots]\cdot \\ \sum_{y_2,y_4,y_6,\ldots\in[|T|/2+1,|T|]}\Pr[h_2(b_2)=h_2(b_3)=y_2\wedge h_2(b_4)=h_2(b_5)=y_4 \wedge \ldots] \\ \le \dfrac{(|T|/2)^{i/3-1}}{(|T|/2)^{i/3-1}(|T|/2)^{i/3-1}}=\dfrac 1{(|T|/2)^{i/3-1}}$

同理 $b$ 序列满足条件 $(2)$ 的概率也是这个。那么有：

$\Pr[X]\le \Pr[\text{序列 }x\text{ 中存在引理 }1\text{ 描述的那样的连续子序列}] \\ \le \dfrac {2n^{i/3-1}}{(|T|/2)^{i/3-1}}< \dfrac 2{(1+\delta/2)^{i/3-1}}$

注意最后一步用了条件：$|T|>(2+\delta)n$。

迭代序列是坏的概率

设 $v$ 为 $x_1,\ldots,x_i$ 中不同值的个数。我们分析这个序列恰有 $v$ 个不同值的概率的上界。

因为这个序列已经是坏的了，所以一定存在三个下标 $j,k,w$，满足 $x_i=x_j=x_w\,(1\le j<k<j+k\le w\le i)$。

为了方便分析，我们把前文中对第三种情况的解释图再搬下来。可以发现的是 $(j,k,w)$ 把这 $v$ 个不同的数分成了四部分。这四个部分分别是下图中右边和左边的绿色部分、与左边的红色部分剪掉左边绿色部分、右边的红色部分剪掉右边绿色部分。所以 $(j,k,w)$ 的方案数就是把长度为 $v$ 的序列分为三部分的方案数，也就是 $\dbinom v 3\le v^3$。

对于这 $v$ 个不同的值，我们有不超过 $n^{v-1}$ 种取值方式（有一个确定是 $x$ 了）。又有不超过 $(|T|/2)^{v-1}$ 种方式把这些值安放到桶里面（$x$ 是正在插入的数，没有对应的位置）。并且，因为 $h_1,h_2$ 都是 $2K$-Universal 的，且两个哈希函数是独立的，所以有不超过 $(|T|/2)^{-2v}$ 的概率哈希函数映射的是对的（即哈希函数确实把对应元素映射到其所在的桶）。所以「这个序列恰有 $v$ 个不同值」的概率不超过 $n^{v-1}(|T|/2)^{v-1}v^3(|T|/2)^{-2v}$。

那么我们可以写出 $\Pr[Y]$ 的表达式：

$\Pr[Y]\le \sum_{v=3}^i n^{v-1}(|T|/2)^{v-1}v^3(|T|/2)^{-2v}\\ \le \dfrac 2{|T|n}\sum_{v=3}^\infty v^3\left(\dfrac{2n}{|T|} \right)^v< \dfrac 2{|T|n}\sum_{v=3}^\infty v^3(1+\delta/2)^{-v}=O(1/n^2)$

注意上述推导中用到了条件：$|T|> (2+\delta)n,|T|=\Omega(n)$。

插入失败概率分析

我们接下来去分析 ${\Pr}_n[\text{Insert Fail}]$。插入失败有两种情况，第一种情况是这个长度为 $2K$ 的序列已经是坏的了，由以上分析知这一部分概率级别为 $O(1/n^2)$；第二种情况是这个序列是好的，但就是太长了，由以上分析知这个概率至多为 $(1+\delta/2)^{-2K/3+1}$。

我们令 $K=\lceil 3\log_{1+\delta/2}|T| \rceil$，则：

$(1+\delta/2)^{-2\lceil 3\log_{1+\delta/2}|T| \rceil/3+1}=O(1/n^2)$

所以 ${\Pr}_n[\text{Insert Fail}]=O(1/n^2)$。

三项统合起来

首先有：

$\begin{aligned} \sum_{i=1}^{2K}\Pr[|x|\ge i] & \le 1+\sum_{i=2}^{2K}\left(\dfrac 2{(1+\delta/2)^{i/3-1}} +O(1/n^2) \right) \\ & \le 1+O\left(\dfrac{2K}{n^2} \right)+2\sum_{i=0}^\infty \dfrac{1}{(1+\delta/2)^{i/3-1}} \\ & =O(1) \end{aligned}$

注意在以上推导种我们已经令 $K=\lceil 3\log_{1+\delta/2}|T| \rceil$。

于是可以得到：

$\mathbb E_n(\text{Insert})\le O(1)+O(1/n^2)\cdot (n+1)\cdot \mathbb E_n(\text{Insert})\\ \Rightarrow \mathbb E_n(\text{Insert})=O(1),\mathbb E_n(\text{ReHash})=O(n)$

综上我们得出插入操作的期望时间复杂度是常数级别的。

表扩容时间复杂度分析

假设已经插入了 $n$ 个数，那么执行表扩容次数的级别为 $O(\log n)$，每次扩容的时候表的大小分别不超过 $n,n/2,n/4,\ldots$。由上文分析，对一个大小为 $S$ 的表进行 ReHash 的期望时间复杂度是 $O(S)$ 的，所以插入 $n$ 个数时表扩容的总期望时间复杂度为 $O(n+n/2+\ldots)=O(n)$，所以均摊到每一次插入中就是期望 $O(1)$ 的。

参考文献

[1] Cuckoo Hashing and Cuckoo Filters. Noah Fleming, 2018. From Toronto University,
site: https://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf.

[2] Cuckoo Hashing. From Standford University,
site: https://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/13/Small13.pdf.

[3] An Overview of Cuckoo Hashing. Charles Chen. From Standford University,
site: https://cs.stanford.edu/~rishig/courses/ref/l13a.pdf.