←喜欢的点个赞呗~

新更两种做法：跳表、01Trie

先来点正常的

一、拉链法及其变种

算法1

(普通拉链法)

用链表处理hash值冲突

#include<iostream>
using namespace std;
const int N=100003;
int h[N],num[N],ne[N],idx=1;
void add(int x){    //向表中加入元素
    int place=(x%N+N)%N;
    ne[idx]=h[place],num[idx]=x,h[place]=idx++;
}
bool find(int x){   //找元素
    int place=(x%N+N)%N;
    for(int i=h[place];i;i=ne[i])
        if(num[i]==x)
            return 1;
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            add(x);
        else
            puts(find(x)?"Yes":"No");
    }
    return 0;
}

算法2

(拉链法.自动取模)

众所粥知，int16_t是个很好的玩意~~

数据范围是-32768~32767，数组存的下！！！

当然，同样的方法不能用在开放寻址法，插入太多是存不下的

#include<iostream>
using namespace std;
const int N=70000;
int h[N],num[N],ne[N],idx=1;
void add(int x){    //向表中加入元素
    int16_t place=x;    //自动取模
    //加上32768变成0~65535之间的数
    ne[idx]=h[place+32768],num[idx]=x,h[place+32768]=idx++;
}
bool find(int x){   //找元素
    int16_t place=x;
    for(int i=h[place+32768];i;i=ne[i])
        if(num[i]==x)
            return 1;
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            add(x);
        else
            puts(find(x)?"Yes":"No");
    }
    return 0;
}

二、开放寻址法及其变种

算法3

(开放寻址法.线性探查法)

简称蹲坑法

#include<iostream>
#include<cstring>
using namespace std;
const int N=200003,INF=0x3f3f3f3f;
int num[N];
int find(int x){
    int place=(x%N+N)%N;
    while(num[place]!=INF&&num[place]!=x){  //该坑已被占用，去下一个坑
        place++;
        if(place==N)    //逛到最后一个坑，就回到开始
            place=0;
    }
    return place;   //返回最后找到的坑
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

算法4

(开放寻址法.平方探查法)

就是蹲坑方式变了一下

极具瞎试精神

#include<iostream>
#include<cstring>
using namespace std;
const int N=200003,INF=0x3f3f3f3f;
int num[N];
int find(int x){
    int place=(x%N+N)%N,idx=1;
    int i=place;
    while(num[i]!=INF&&num[i]!=x){
        i=(place+idx*idx)%N;    //直接跑到编号为idx的平方的坑位去
        idx++;
    }
    return i;
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

算法5

(开放寻址法.双散列探查法)

就每一个数单独生成一个步长

是开放寻址法最好的方法之一

#include<iostream>
#include<cstring>
using namespace std;
const int N=200003,INF=0x3f3f3f3f;
int num[N];
int find(int x){
    int place=(x%N+N)%N,step=17-x%17;   //这里的17可以替换成其它数，时间不尽相同
    while(num[place]!=INF&&num[place]!=x)
        place=(place+step)%N;
    return place;
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

再来点不正常的

三、套用别的题的思路

算法6

(离散化1)

离散化的排序是离线算法

所以加入时间，然后直接搜索

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
struct node{
    int x,t;
    bool operator<(const node &W)const{
        if(x!=W.x)
            return x<W.x;
        return t<W.t;
    }
}is[N],qs[N];   //分别代表所有插入和所有询问
int icnt,qcnt;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            is[icnt++]={x,i};
        else
            qs[qcnt++]={x,i};
    }
    sort(is,is+icnt);
    for(int i=0;i<qcnt;i++){
        int l=0,r=icnt-1;   //二分
        while(l<r){
            int mid=l+r>>1;
            if(is[mid].x<qs[i].x)
                l=mid+1;
            else
                r=mid;
        }
        //值相等的同时，该值第一次被插入的时间还得比询问时间早
        if(is[l].x==qs[i].x&&is[l].t<qs[i].t)   
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

算法7

(离散化2)

不难发现，记录时间这一操作可以改为离散化后再开个数组记录一下出现的数量

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
struct node{
    bool type;
    int x;
}qs[N];
int dc[N],cnt[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            qs[i]={0,x};
        else
            qs[i]={1,x};
        dc[i]=x;
    }
    sort(dc+1,dc+1+n);
    for(int i=1;i<=n;i++){
        int p=lower_bound(dc+1,dc+1+n,qs[i].x)-dc;
        if(qs[i].type==0)
            cnt[p]++;
        else
            puts(cnt[p]?"Yes":"No");
    }
    return 0;
}

算法8

(Trie树)

把每个数看成只由负号和数字组成的字符串

#include<iostream>
using namespace std;
const int N=400005; //数组要稍微开大一点（比赛时要开得更大，这个值并不保险）
int son[N][11],idx;
bool cnt[N];
void add(char now[]){   //插入字符串
    int p=0;
    for(int i=0;now[i];i++){
        int u=now[i]-'0';
        if(now[i]=='-') //单独处理负号
            u=10;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]=1;
}
bool search(char now[]){    //查找一个字符串是否存在
    int p=0;
    for(int i=0;now[i];i++){
        int u=now[i]-'0';
        if(now[i]=='-')
            u=10;
        if(!son[p][u])
            return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2],x[11];
        scanf("%s%s",type,x);
        if(type[0]=='I')
            add(x);
        else
            puts(search(x)?"Yes":"No");
    }
    return 0;
}

算法9

（01Trie）

用数字的二进制建Trie树

#include<iostream>
using namespace std;
const int N=100010,T=32;
int son[N*T][2],idx;
bool cnt[N*T];
void add(int x){
    int p=0;
    for(int i=T-1;~i;i--){
        int u=x>>i&1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]=1;
}
bool search(int x){
    int p=0;
    for(int i=T-1;~i;i--){
        int u=x>>i&1;
        if(!son[p][u])
            return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            add(x);
        else
            puts(search(x)?"Yes":"No");
    }
    return 0;
}

算法10

（平衡树）

维护普通平衡树的插入和查询单点存不存在两种操作

然后把插入的数扔到平衡树里

#include<iostream>
using namespace std;
const int N=100010,INF=1e8;
struct node{
    int l,r;
    int key,var;
}tr[N];
int root,idx;
inline int get_node(int key){   //建点
    tr[++idx].key=key;
    tr[idx].var=rand();
    return idx;
}
inline void zig(int &p){    //右旋
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
}
inline void zag(int &p){    //左旋
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
}
inline void build(){    //建树
    get_node(-INF);
    get_node(INF);
    root=1;
    tr[1].r=2;
    if(tr[1].var<tr[2].var)
        zag(root);
}
void insert(int &p,int key){
    if(!p)
        p=get_node(key);    //通过指针间接设定l或R
    else if(tr[p].key==key)
        return;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].var>tr[p].var)
            zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].var>tr[p].var)
            zag(p);
    }
}
bool get_rank_by_key(int p,int key){
    if(!p)  //点不存在
        return 0;
    if(tr[p].key==key)
        return 1;
    if(tr[p].key>key)
        return get_rank_by_key(tr[p].l,key);
    return get_rank_by_key(tr[p].r,key);
}
int main(){
    build();
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            insert(root,x);
        else
            puts(get_rank_by_key(root,x)?"Yes":"No");
    }
    return 0;
}

算法11

(线段树)

和离散化基本思路相同

先排序，加入时间,然后用线段树维护询问的区间最大值

适合广大拥有二分恐惧症的同学们

没错就是闲的

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
struct node{
    int l,r;
    int maxn;
}tr[N<<2];
PII is[N],qs[N];
int icnt,qcnt;
inline void pushup(int p){
    tr[p].maxn=max(tr[p<<1].maxn,tr[p<<1|1].maxn);
}
void build(int l,int r,int p){
    tr[p]={l,r};
    if(l==r){
        tr[p].maxn=is[l].x;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}
int query(int p,int x){
    int l=tr[p].l,r=tr[p].r;
    if(l==r)
        return tr[p].maxn==x?l:0;
    if(tr[p<<1].maxn>=x)
        return query(p<<1,x);
    else if(tr[p<<1|1].maxn>=x)
        return query(p<<1|1,x);
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            is[++icnt]={x,i};
        else
            qs[++qcnt]={x,i};
    }
    sort(is+1,is+icnt+1);   //排序
    build(1,n,1);   //建树
    for(int i=1;i<=qcnt;i++){
        int p=query(1,qs[i].x);
        puts(p&&is[p].y<qs[i].y?"Yes":"No");    //查询
    }
    return 0;
}

算法12

权值线段树

这种线段树维护的不是数，而是每个数有多少个

由于数的范围较大，仍然需要离散化

这道题只需要单点修改，单点查询，显得很没必要

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct Query{
    bool type;
    int x;
}qs[N];
struct Node{
    int l,r;
    int maxn;
}tr[N<<2];
int dc[N];
inline void pushup(int p){
    tr[p].maxn=max(tr[p<<1].maxn,tr[p<<1|1].maxn);
}
void build(int l,int r,int p){
    auto &u=tr[p];
    u={l,r};
    if(l==r)
        return;
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
}
void add(int p){
    auto &u=tr[p];
    if(u.l==u.r){
        u.maxn++;
        return;
    }
    int mid=u.l+u.r>>1;
    if(p<=mid)
        add(p<<1);
    else
        add(p<<1|1);
    pushup(p);
}
int query(int p){
    auto u=tr[p];
    if(!u.maxn)
        return 0;
    if(u.l==u.r)
        return u.maxn;
    int mid=u.l+u.r>>1;
    if(p<=mid)
        return query(p<<1);
    else
        return query(p<<1|1);
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            qs[i]={0,x};
        else
            qs[i]={1,x};
        dc[i]=x;
    }
    sort(dc+1,dc+1+n);  //离散化
    for(int i=1;i<=n;i++){
        int p=lower_bound(dc+1,dc+1+n,qs[i].x)-dc;
        if(qs[i].type==0)
            add(p); //单点修改
        else
            puts(query(p)?"Yes":"No");  //单点查询
    }
    return 0;
}

算法13

分块

就是换了一种维护方式

没错还是闲的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
PII is[N],qs[N];
int icnt,qcnt;
int len,maxn[N];
inline int query(int x){
    int p=0;
    while(p<=icnt/len&&maxn[p]<x)
        p++;
    for(int i=p*len;i<=p*len+len-1;i++)
        if(is[i].x==x)
            return i;
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            is[++icnt]={x,i};
        else
            qs[++qcnt]={x,i};
    }
    sort(is+1,is+icnt+1);   //排序
    len=sqrt(icnt);
    memset(maxn,-0x3f,sizeof maxn);
    for(int i=1;i<=icnt;i++)
        maxn[i/len]=max(maxn[i/len],is[i].x);
    for(int i=1;i<=qcnt;i++){
        int p=query(qs[i].x);
        puts(p&&is[p].y<qs[i].y?"Yes":"No");
    }
    return 0;
}

算法14

（st表）

和线段树一个思路

只是不存树的节点，改为用st表作最大值搜索

#include<iostream>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=100010,T=20;
PII is[N],qs[N];
int icnt,qcnt;
int maxp[N][T];
inline void init(){
    for(int i=icnt;i;i--){
        maxp[i][0]=i;
        for(int t=1;i+(1<<t)-1<=icnt&&t<T;t++){
            int a=maxp[i][t-1],b=maxp[i+(1<<t-1)][t-1];
            maxp[i][t]=is[a].x>is[b].x?a:b;
        }
    }
}
inline int get(int l,int r){
    int len=log(r-l+1)/log(2);
    int a=maxp[l][len],b=maxp[r-(1<<len)+1][len];
    return is[a].x>is[b].x?a:b;
}
int query(int l,int r,int x){
    if(l==r)
        return is[l].x==x?l:0;
    int mid=l+r>>1;
    if(is[get(l,mid)].x>=x)
        return query(l,mid,x);
    else if(is[get(mid+1,r)].x>=x)
        return query(mid+1,r,x);
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            is[++icnt]={x,i};
        else
            qs[++qcnt]={x,i};
    }
    sort(is+1,is+icnt+1);   //排序
    init();
    for(int i=1;i<=qcnt;i++){
        int p=query(1,icnt,qs[i].x);
        puts(p&&is[p].y<qs[i].y?"Yes":"No");    //查询
    }
    return 0;
}

算法15

跳表

跳表本质上是多层的有序链表

每层的每个数有0.5的概率继承到上面一层

这样期望的时间复杂度就是O(nlogn)的

理论上来讲除了Splay的区间翻转，平衡树能干的跳表都能干

#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=100010,T=17,INF=2e9;
struct Node{
    int r,d;
    int x;
}sl[N*T];
int idx;
inline void build(){    //建哨兵
    for(int i=1;i<=T*2;i++){
        Node &u=sl[++idx];
        if(i&1)
            u.x=-INF,u.r=i+1;
        else
            u.x=INF;
        if(i<T*2-2)
            u.d=i+2;
    }
}
inline int rand_level(){    //生成随机层数
    for(int i=1;i<=T;i++)
        if(rand()%2)
            return i;
    return T;
}
inline void add(int x){
    int p=1,h=rand_level();
    for(int c=T;c;c--){
        while(sl[sl[p].r].x<=x)
            p=sl[p].r;
        if(c<=h){
            sl[++idx].x=x;
            sl[idx].r=sl[p].r;
            sl[p].r=idx;
            if(c>1)
                sl[idx].d=idx+1;
        }
        if(c>1)
            p=sl[p].d;
    }
}
inline bool query(int x){
    int p=1;
    for(int c=T;c;c--){
        while(sl[sl[p].r].x<=x)
            p=sl[p].r;
        if(c>1)
            p=sl[p].d;
    }
    return sl[p].x==x;
}
int main(){
    srand(time(0));
    build();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            add(x);
        else
            puts(query(x)?"Yes":"No");
    }
    return 0;
}

四、其他哈希方法

此类讲述不同哈希地址生成方法

仍需使用某种冲突处理

此处统一使用开放寻址法

算法16

（随机数法）

使用随机数作为哈希地址

注意这里的随机数是自己写的伪随机函数

即传入的参数一样得到的值一定一样

伪随机函数很不好写，很容易出现神奇的错误，不建议使用

#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;
const int N=2000003,INF=0x3f3f3f3f;
int num[N];
inline int random(int x){   //瞎写的伪随机函数，像极了折叠法，敬请谅解
    return abs(x%10000*7+x/100000*5);
}
int find(int x){
    int place=random(x);
    while(num[place]!=INF&&num[place]!=x)
        if(place++==N)
            place=0;
    return place;
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

算法17

(折叠法)

将关键字分成位数相同的几个部分

然后将各个部分相加作为哈希地址

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2000003,INF=0x3f3f3f3f;
int num[N];
int find(int x){
    int place=abs(x/100000+x%100000);   //折叠生成哈希地址
    while(num[place]!=INF&&num[place]!=x)
        if(place++==N)
            place=0;
    return place;
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

算法18

（数字分析法）

抽取关键字的几位

遇到比较坑的题，比如这道，要抽半天才能过，很不好调

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2000003,INF=0x3f3f3f3f;
int num[N];
int find(int x){
    int place=abs(x/10%1000000);    //抽取第2到第7位
    while(num[place]!=INF&&num[place]!=x)
        if(place++==N)
            place=0;
    return place;
}
int main(){
    memset(num,0x3f,sizeof num);
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            num[find(x)]=x;
        else
            puts(num[find(x)]==x?"Yes":"No");
    }
    return 0;
}

五、偷懒做法

算法19

(map大法)

直接用map模拟

没啥好说的

#include<iostream>
#include<map>
using namespace std;
map<int,bool> m;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            m[x]=1;
        else
            puts(m.count(x)?"Yes":"No");
    }
    return 0;
}

算法20

(unordered_map大法)

思路和map大法类似

只是一般情况下比map要快

#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int,bool> m;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            m[x]=1;
        else
            puts(m.count(x)?"Yes":"No");
    }
    return 0;
}

算法21

(set大法)

就是换了个容器

#include<iostream>
#include<set>
using namespace std;
set<int> s;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            s.insert(x);
        else
            puts(s.count(x)?"Yes":"No");
    }
    return 0;
}

算法22

(unordered_set大法)

就是又㕛叒叕换了个容器

比set快很多

#include<iostream>
#include<unordered_set>
using namespace std;
unordered_set<int> s;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char type[2];
        int x;
        scanf("%s%d",type,&x);
        if(type[0]=='I')
            s.insert(x);
        else
            puts(s.count(x)?"Yes":"No");
    }
    return 0;
}

未完待更