布谷鸟哈希——数据处理的能手

· · 算法·理论

以前在学习某个数据结构的时候看到了这个哈希算法，一看还挺牛逼的，就打算装进脑子里面。

本文默认读者已经学习过基础的哈希表。

简介

布谷鸟哈希是一种在时间上极为高效的哈希算法，其能够做到：

  1. 均摊 O(1) 插入。
  2. 严格 O(1) 查找和删除。

目前 OI 中比较常用的哈希冲突的处理办法是拉链法和闭散列法。拉链法就是在同一个地址下面存下所有产生冲突的数字，因为哈希表容量很大，所以说平均每个链拉下来的长度都很短，那么操作复杂度都是常数级别的，而且手写表不像 STL 和平板电视容易被卡，毕竟出题人也不知道你的哈希函数到底长什么样。所以拉链法的查插删都是均摊 O(1) 的。闭散列法就是在产生哈希冲突的时候把当前要插入的这个数往后一直挪直到一个空地址上，查找也是从哈希出来的地址上开始往后遍历直到查到目标数为止。均摊下来仍然是 O(1) 的。

布谷鸟哈希的思想和多重哈希的思想其实差不多。

背景及基本思想

首先我们要知道什么是布谷鸟，为什么这个哈希会被叫做布谷鸟哈希。

布谷鸟是自然界中的一种鸟类，它们大多不自己筑巢，而是把鸟蛋下在别的鸟巢之中，自然，鸟蛋就由原鸟巢的母亲抚养，布谷鸟幼崽会先于原鸟蛋孵化，然后幼崽会把剩下的原鸟蛋挤出巢外，独享宠爱。

布谷鸟哈希也是这样的。

在双重哈希中，若哈希函数 f_1(x) 发生冲突，则会使用第二个哈希函数 f_2(x)，若仍产生冲突，则将哈希值变为 i\times f_2(x)，其中 i 是冲突次数，一直重复下去直到没有冲突为止。你也可以自己设计其他的冲突策略。

布谷鸟哈希有很多版本，不过最为经典的还是两个哈希函数和两个哈希桶的版本，也是最容易理解的。

其思想为：先将键值 x 映射为第一个哈希函数 f_1(x)，若不产生冲突则存入，否则映射为第二个哈希函数 f_2(x)，若不产生冲突则存入。若两个哈希函数均产生冲突，则将原 f_1(x) 所对应键值替换为 x，随后原键值变为现在的 x，然后将其映射为 f_2(x)，若不产生冲突则存入，否则将原 f_2(x) 所对应键值替换为 x，随后原键值变为现在的 x，然后再将 x 映射为 f_1(x)。就这么一直重复下去，直到不产生冲突。若循环的次数超过了阈值，那么我们就进行一个叫做 rehash 的活动。不过 rehash 真正启用的时候很少，你也可以就让它一直循环下去。

我们发现，多重哈希就像是一个人一直想找一个酒店住下，但是他发现酒店房间一直都是满的，于是就一直换酒店一直换酒店，最后找到一个有空房间的酒店再住进去。

而布谷鸟哈希就是一个人想找一个酒店住，于是他直接破门而入，然后把住在房间里面的人丢出门外，再把门锁上，将屋子占为己有。而被丢的人就红温了，于是他就继续去其他酒店破门而入，直到每个人都住下来了。

工作过程

我们可以举一个例子，来更好的说明布谷鸟哈希的工作过程：假设我们现在有一组等待哈希映射的键值 \{20,3,13,48,17,32,40,35\}。我们建立两个哈希函数，分别是 f_1(x)=x，f_2(x)=\lfloor \frac{x}{4}\rfloor，单个哈希桶容量为 15，也就是说哈希函数是在模 15 意义下的。

首先我们先插入 20，自然，它会被映射成 5。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  -  -  -  20 -  -  -  -  -  -  -  -  - 
2 -  -  -  -  -  -  -  -  -  -  -  -  -  -  -

随后我们依次插入 3,13，这时候都是不会发生冲突的。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  -  3  -  20 -  -  -  -  -  -  -  13 - 
2 -  -  -  -  -  -  -  -  -  -  -  -  -  -  -

随后我们插入 48，就发现问题了，因为 f_1(3)\equiv f_1(48) \pmod {15}，我们就直接把 3 踢出去，把 48 放进去，被踢出来的 3 被 f_2(x) 映射为了 0，放在了第二个哈希表的 0 地址下。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  -  48 -  20 -  -  -  -  -  -  -  13 - 
2 3  -  -  -  -  -  -  -  -  -  -  -  -  -  -

接着我们插入 17,32，这两个键值会在第一个哈希桶中产生冲突，自然，后插入的 32 就把 17 给踢到了第二个哈希桶里面，映射为 4。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  32 48 -  20 -  -  -  -  -  -  -  13 - 
2 3  -  -  -  17 -  -  -  -  -  -  -  -  -  -

随后我们插入 40，无事发生。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  32 48 -  20 -  -  -  -  40 -  -  13 - 
2 3  -  -  -  17 -  -  -  -  -  -  -  -  -  -

插入 35，与 20 产生冲突，我们把 20 踢掉，换到第二个哈希桶中，其被映射为 5。

\ 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
1 -  -  32 48 -  35 -  -  -  -  40 -  -  13 - 
2 3  -  -  -  17 20 -  -  -  -  -  -  -  -  -

至此，所有数字映射完毕，哈希结束。

更进一步

当然我们希望有更为极端的情况出现。于是我们设 f_2(x)=x\times2，然后构造同余键值 \{15,30,45\}，你就会发现他们三个进入了死循环，互相踢（当然，这只是举例子，正常写题中采用如此简单的哈希函数包被卡炸的）。这个时候我们就需要 rehash，或者调整哈希函数。如果是在 OI 赛制中，我推荐使用 rehash。rehash 的思路和 STL 差不多，只需要拉伸一下哈希表，给它扩容一下即可。如果是在 IOI 赛制中，我推荐重新设置哈希函数，就不多说了。

布谷鸟哈希还有其他的拓展写法，比如设置第三个哈希函数 f_3(x)，降低冲突率，但是空间占用也会显著提高。

复杂度

插入时间复杂度：均摊 O(1)，在负载因子为 0.5 及以下的情况下效率极高。

删除时间复杂度：O(1)，因为一个数只可能存在于 f_1(x) 和 f_2(x) 对应的地址下。

查询时间复杂度：O(1)，同上。

不过大家更关心的肯定是这个插入时间的具体分析，我们就来说明一下。

关于插入的几种情况的具体分析

下面我们设目前待插入的键值为 x，其余的已经在哈希表中的键值为 x_1,x_2,x_3,\dots。

情况一很好说，就是 O(1)。

现在我们来证明每次插入操作所引发的扩容操作的均摊时间成本为 O(1)。

设我们的哈希表大小为 r，当前已经插入数据规模为 n，则我们规定有 r\ge(1+\epsilon)\times n，其中 \epsilon 是常数，理由很简单不再赘述。因此当 r<(1+\epsilon)\times n 时，我们进行必要的哈希表扩容操作。每次扩容，我们将 r\leftarrow 2r，即扩大到原来的两倍。我们易知进行一次扩容操作的时间复杂度为 O(n)。

在所有数据全部哈希完成之后，易知容操作总执行次数为 O(\log n)。期望的扩容时间占用为 O(n+n/2+n/4+\dots+n/2^{O(\log n)})。这个式子是个很明显的等比数列，推出来它就是个 O(n)。数据规模为 O(n)，均摊时间成本为 O(1)。

我们继续深入。

双哈希函数的布谷鸟哈希表可以用一张有向图来描述：点表示一个地址 u，u\rightarrow v 边表示键值存于 u 地址下可以通往的备用地址 v。可以得到这样一张图：

其中方框表示地址，圆表示键值，方框中含圆表示该地址已有键值存储，方框中无圆表示该地址为空，圆不在方框内表示待插入。

我们即将插入 x，优先把 x 插到 x_1 那里去。所以会变成这样：（注意 x_1 肯定会选择从备用地址进入，也就是踢出 x_2。）

我同时对边进行了染色处理，红色边表示这条边经过了反转，绿色表示我们即将沿着这条边存储进一个位置。

随后是 x_2 踢出 x_3，重复下去：

最后，在踢出 x_7 后，你会发现经过了插入过程的地址所对应的边全部反转了一遍，局面是这样的：

随后 x_2 被踢出，实际上 x_2 并不会重新进入插入循环，因为它的备用地址指向了 x_1 而并非环中。

看，我们将 x_2 的原边标回了黑色，很容易看出在整个插入过程结束后，x_3\sim x_7 这一个环中的边一定会发生一次反转，同时容易看出该规律具有普遍性。最终结果应该是这样的：

我们把这个插入冲突过程用序列来表示就是 \{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_2,x_1,x,x_8\}。你会发现，当 x_2 产生第二次冲突后，插入序列会自动进行回溯，一直返回到原始的地址，随后开始了一段新的插入序列（此后我们把这种同一个元素产生多次冲突，且使用图来表示序列后出现环的情况简称为“有环”）。

放到一般情况下来讲，一段完整的有环的插入冲突序列形如 \{x_1,x_2,x_3,\dots,x_j,\dots,x_3,x_2,x_1,\dots,x_l\}，所以必定有 x_i=x_j(i<j)。当出现 x_i=x_j 之后，序列就会产生回溯，于是出现 x_{i-k}=x_{j+k}，直至回溯至 x_1，那么有 x_1=x_{j+i-1}。在这里，我们可以定义 (i,j) 是字典序最小的满足 x_i=x_j\land i\not=j 的有序对。随后便会开启一段全新的插入冲突子序列 \{x_{j+i},x_{j+i+1},\dots,x_l\}，容易发现 l\ge j+i-1，为何可以取等，因为 x_1 的备用地址可以直接是空的，所以序列回溯到 x_1 以后就不会继续冲突。接着，若出现 x_l=x_k(k<l)，说明我们又与之前的键值产生了冲突，显然，我们又会进入一遍之前已经冲突过的冲突序列（为什么？若 1\le k\le i，这一段键值的地址经历了两次冲突，那么它们会回归原始状态，进入冲突后显然会与之前的情况一模一样，后半段类似，若 i<k<j，即在环中，因为当前插入的 x_k 向外连了一条边，那么环转完一圈以后就会向外跑出去，接着就会开始沿着冲突序列又倒回去，倒到 x_j 后再次入环，进入无限循环）。

分析时间复杂度之前，还有两个东西要提一嘴。

插入环引理：

设当前插入键值 x 构成冲突序列 x_1=x,x_2,x_3,\dots,x_p 且不构成死循环情况，则其中存在一个长度为 l\ge \frac{p}{3} 的连续子序列 x_q,x_{q+1},x_{q+2},\dots,x_{q+l-1} 满足其中元素互异且 x_q=x_1=x。 :::info[证明]{open}

若无环，引理显然成立。若 p\le i+j-1，则元素 x_1,x_2,\dots,x_{j-1} 显然互异。因为 j>i，所以有 j-1\ge \frac{i+j-1}{2}\ge \frac{p}{2}。引理成立。若 p>i+j-1，那么满足这种条件且可能最长的子序列有两个，一个是 x_1,x_2,\dots,x_j-1，另一个是 x_{i+j-1},x_{i+j},\dots,x_p。一个的长度是 j-1，另一个的长度是 p-(i+j-1)+1=p-i-j+2。中间夹着的子序列的长度为 i-1，因为有 j>i 所以有 j-1>i-1。若 j-1>p-i-j+2 显然 3(j-1)>p，否则有 3(p-i-j+2)\ge p。\blacksquare

:::

:::info[全域哈希]{open}

若你的哈希函数是固定的，设哈希表大小为 m，我们期望的哈希冲突概率会是 \frac{1}{m}，然而在你的代码可见的情况下，hacker 总能构造一组方案让你的哈希表直接废掉，哈希冲突率达到 100\%，完全救不了你的那种。我们定义一个哈希函数集合 S=\{h_1,h_2,h_3,\dots,h_{|S|}\}。构造哈希表时，我们等概率随机选取一个哈希函数即可，但是我如果使用一组 hack 数据卡掉你其中的一个或多个函数，这样就不能达到我们期望的冲突概率 \frac{1}{m} 了。所以单单一个毫无性质的集合 S 并不能保证安全性。

全域哈希还保证了一个性质，即对于任意两个键值 x,y 有 h(x)=h(y) 的数量不超过 \frac{|S|}{m} 个。显然，这个时候我们的最坏冲突概率就是 \frac{|S|}{m}\times \frac{1}{|S|}=\frac{1}{m} 了。

:::

我们在设定循环阈值 MAX 后（即插入次数超过 MAX 就进行 rehash），我们肯定会产生一个长度为 k\le2MAX 的冲突序列（因为我们有两个哈希函数，一次循环处理两次插入）。

对此，有两种情况：

  1. 不出现环：概率上界为 \displaystyle 2(1+\epsilon)^{-\frac{k-1}{3}+1}，其中这个 \epsilon 就是我们在之前所定下的哈希表大小 r\ge(1+\epsilon)\times n 中的常数。

  2. 出现环：概率上界为 \displaystyle O(\frac{1}{n^2})。

注意，这两个情况不是互斥的。

至于我们是怎么把这两个概率上界给定出来的呢。

::::info[不出现环的情况]

由插入环引理，我们得知：一个长度为 k 的插入冲突序列，一定有一段长度 v=\lceil k/3\rceil 的序列，其中的元素互不相同。我们将其提取出来为 b_1,b_2,b_3,\dots,b_v。不妨设 b_1=x，根据我们的哈希策略，这个序列在 h_1,h_2 两个哈希函数中具有以下性质。

h_1(b_1)=h_1(b_2),h_2(b_2)=h_2(b_3),h_1(b_3)=h_1(b_4),\dots

因为可以采用全域哈希，那么我们就可以假设，h_1,h_2 都是能够均匀且随机地把数值映射到 \{0,1,\dots,r-1\} 的。所以我们肯定有不多于 n^{v-1} 种冲突序列。而又因为每次哈希冲突的概率应该是 1/r，所以产生这种情况的概率是 r^{-(v-1)}。

那么，存在 b_1,b_2,b_3,\dots,b_v 的概率上界即为：

2n^{v-1}r^{-(v-1)}=2(r/n)^{-(v-1)}\le2(1+\epsilon)^{-k/3+1}

:::info[中间那个不等关系怎么来的？]

r&\ge(1+\epsilon)\times n \\ r/n&\ge1+\epsilon\\ (r/n)^{-(v-1)}&\le (1+\epsilon)^{-(v-1)}\\ &\le (1+\epsilon)^{-k/3+1} \end{aligned}

:::

::::

:::info[出现环的情况]

我们令 v\le k 表示互不相同的键值数量，其中有一个待插入键值 x。则我们将它们映射到这个哈希表中的方式有 r^{v-1} 种。

在环中我们定义过 (i,j)，以及 x_l，粗略估计这三个变量总共会有 v^3 种取值。因为环长可以达到 2v，所以上述情况发生的概率就是 r^{-2v}。

那么求和一下。

\sum_{v=3}^k n^{v-1}r^{v-1}v^3r^{-2v}\le\frac{1}{nr}\sum_{v=3}^\infty v^3(1+\epsilon)^{-v}=\frac{1}{nr}O(1)=O(\frac{1}{n^2})

因为 r\ge(1+\epsilon)\times n，所以 r=O(n)。

:::

那么，我们可以计算循环插入中产生的序列预期长度为：

1+\sum_{k=2}^{2MAX}[2(1+\epsilon)^{-\frac{k}{3}+1}+O(1/n^2)]\le 1+O(MAX/n^2)+2\sum_{i=0}^{\infty}(1+\epsilon)^{-\frac{k}{3}}=O(1)+\frac{O(1)}{1-(1+\epsilon)^{-1/3}}=O(1)

也就是说，冲突次数是 O(1) 的，故插入复杂度为均摊 O(1)。

证完力！

上述文章还有一个点没有讲到：凭什么进行一次扩容操作的时间复杂度为 O(n)。

接下来我们再证：扩容操作的时间复杂度是均摊 O(n)。

我们得知：进入死循环的概率是 O(\displaystyle\frac{1}{n^2})。此外，插入过程未进入死循环环的概率上界为 2(1+\epsilon)^{-\frac{k}{3}+1}。我们让插入冲突序列的长度 k=2MAX 时就开始扩容操作。我们设 MAX=\lceil3\log_{1+\epsilon} r\rceil。那么我们没有进入死循环，但是长度达到限制的概率则为：

2(1+\epsilon)^{-\frac{k}{3}+1}=O(2(1+\epsilon)^{-2\log_{1+\epsilon r}})=O(1/r^2)=O(1/n^2)

因此，一次插入操作导致扩容的概率为 O(\displaystyle \frac{1}{n^2})。

在扩容操作时，我们会执行 n 次插入，每次插入的复杂度为 O(1)，失败导致扩容的概率为 O(\displaystyle \frac{1}{n^2})，则扩容成功的概率为 1-O(\displaystyle\frac{1}{n})，只要 n 够大即可。因此，我们可以在均摊 O(n) 的时间内完成扩容。

证完力！

code

至此，理论部分全部完工，接下来是代码部分：

因为这是运用于 OI 之中，而非工程，所以我阉割掉了动态扩容的操作，也就是静态空间，以及全域哈希。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define X first
#define Y second
using namespace std;
mt19937 myrand(time(0));
char buf[1<<23],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ull read() {
    ull x=0;
    char ch=gc();
    while(!isdigit(ch))ch=gc();
    while(isdigit(ch)) x=x*10+(ch^48),ch=gc();
    return x;
}
ull ans;
namespace ARONA{
    const int SIZE=9e6;
    const int Null=-1;
    const int MAXLOOP=30;
    struct HashTable{
        pair<ull,ull>a[SIZE+5],b[SIZE+5],c[SIZE+5];
        inline ull h1(const ull &x){
            return (x*0x9e3779b97f4a7c15)%SIZE;
        }
        inline ull h2(const ull &x){
            return (x/213)%SIZE;
        }
        inline ull h3(const ull &x){
            return ((x^(x<<23))*0x1919810ddd)%SIZE;
        }//三个哈希函数，两个太容易被卡了
        HashTable(){for(int i=0;i<=SIZE;i++)a[i].X=a[i].Y=b[i].X=b[i].Y=c[i].X=c[i].Y=Null;}
        inline void clear(){for(int i=0;i<=SIZE;i++)a[i].X=a[i].Y=b[i].X=b[i].Y=c[i].X=c[i].Y=Null;}//清零
        inline ull find(const ull &x){//查询函数
            if(a[h1(x)].X==x)return a[h1(x)].Y;
            if(b[h2(x)].X==x)return b[h2(x)].Y;
            if(c[h3(x)].X==x)return c[h3(x)].Y;
            return Null;
        }
        void erase(const ull &x){//删除函数
            if(a[h1(x)].X==x){a[h1(x)]={-1,-1};return;}
            if(b[h2(x)].X==x){b[h2(x)]={-1,-1};return;}
            if(c[h3(x)].X==x){c[h3(x)]={-1,-1};return;}
        }
    //重点！插入函数！
        void insert(const ull &key,const ull &value){
            if(find(key)!=Null)return;
            pair<ull,ull>now={key,value};
            if(a[h1(key)].X==Null){
                a[h1(key)]=now;
                return;
            }
            if(b[h2(key)].X==Null){
                b[h2(key)]=now;
                return;
            }
            if(c[h3(key)].X==Null){
                c[h3(key)]=now;
                return;
            }//先尝试插进三个哈希表中的对应空位
            for(int i=1;;i++){//没有扩容，自然没有循环上限
                if(a[h1(now.X)].X==Null){
                    a[h1(now.X)]=now;
                    return;
                }
                if(b[h2(now.X)].X==Null){
                    b[h2(now.X)]=now;
                    return;
                }
                if(c[h3(now.X)].X==Null){
                    c[h3(now.X)]=now;
                    return;
                }
                if(now.X==-1)return;
                if(i%3==0)swap(a[h1(now.X)],now);
                else if(i%3==1)swap(b[h2(now.X)],now);
                else swap(c[h3(now.X)],now);//这里就是替换操作了
            }
            assert(0);
        }
    };
}
using namespace ARONA;
HashTable mp;
int n;
ull x,y;
int main(){ 
    cin>>n;
    for(int i=1;i<=n;i++){
        x=read();
        y=read();
        ull tmp=mp.find(x);
        if(tmp==-1)tmp=0;
        ans+=i*1ll*tmp;
        mp.erase(x);
        mp.insert(x,y);
    }
    cout<<ans;
    return 0;
}

题目为 P11615。在题解区我写了一篇简短一些的题解。

参考资料

https://cs.stanford.edu/~rishig/courses/ref/l13a.pdf

https://en.wikipedia.org/wiki/Universal_hashing