真让我找到有关布谷鸟哈希的题了

· · 题解

布谷鸟哈希是一种用于哈希表的哈希策略，其主要特点是建立两个或更多哈希桶，在哈希冲突时踢出原键值，在冲突地址插入新键值，原键值插入另一个桶中。我写了一篇文章以详细介绍：点击跳转。

要想做这道题，就得先理清布谷鸟哈希的工作流程。

双哈希函数的布谷鸟哈希表可以用一张有向图来描述：点表示一个地址 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 的原边标回了黑色，因为它经历两次反转之后转回去了。最终结果应该是这样的：

那么这对我们要做的这道题有什么帮助？

没错，我们可以建图！

按理来说，不同的哈希冲突策略都可以建图，但是布谷鸟哈希建出来的图有一个很明显的性质：哈希成功的情况当且仅当对于图中每一个极大的联通块都有边数不大于点数。

必要性显然，下证充分性。

:::info[证明]

设有哈希函数 h_1,h_2，我们要插入的键值为 x。设 h_1(x)=a,h_2(x)=b，图中有 m 条边，n 个点，注意点不代表元素。同时对于空哈希表，显然属于哈希成功的情况。我们现在即将在图中增加一条 a\rightarrow b 的边。若不产生哈希冲突，图上一定会加入 a,b 中的至少一个点，则插入后仍有 n\ge m。若产生哈希冲突，所有元素会沿着边移动一定步数，若哈希成功，则一定是有一个元素移动到了空地址，此时新增一条边，不增加点数，但有空地址说明此前一定有一次哈希新增加了两个点与一条边（比如空联通块插入新元素），故不破坏 n\ge m 的情况。归纳完毕。

:::

因为我们不模拟哈希冲突，所以建无向图就够了。

代码环节。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937 myrand(time(0));
inline ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    static int sta[40];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top)putchar(sta[--top]+'0');
}
const int N=1e4+5;
int n,m,cnt1,cnt2;
bitset<N>vis1,vis2;
vector<pair<int,int>>e[N];
void dfs(int u) {
    vis1[u]=1;
    ++cnt1;
    for (auto P:e[u]) {
        int v=P.first,id=P.second;
        if (vis2[id])continue;
        vis2[id]=1;
        ++cnt2;
        if(!vis1[v])dfs(v);
    }
}
inline void work() {
    m=read();n=read();
    for (int i=1;i<=n;i++)e[i].clear();
    vis1.reset();
    vis2.reset();
    for (int i=1;i<=m;i++) {
        int u=read()+1;
        int v=read()+1;
        e[u].emplace_back(v,i);
        e[v].emplace_back(u,i);
    }
    for(int i=1;i<=n;i++){
        if(!vis1[i]){
            cnt1=cnt2=0;
            dfs(i);
            if(cnt2>cnt1){
                puts("rehash necessary");
                return;
            }
        }
    }
    puts("successful hashing");
}
int t;
int main(){
    t=read();
    while (t--)work();
    return 0;
}

AC 链接。