普通数字哈希

「爱情、让人受尽委屈。」 2021-06-22 15:36 298阅读 0赞

## 常见哈希 ##

## 模拟散列表 ##

维护一个集合，支持如下几种操作：
    
    “I x”，插入一个数x；
    “Q x”，询问数x是否在集合中出现过；
    现在要进行N次操作，对于每个询问操作输出对应的结果。
    
    输入格式
    第一行包含整数N，表示操作数量。
    
    接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。
    
    输出格式
    对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。
    
    每个结果占一行。
    
    数据范围
    1≤N≤105
    −109≤x≤109

1.拉链法

#include <iostream>
    #include <string>
    #include <algorithm> 
    #include <vector>
    using namespace std;
    const int N=1e5+7;//N最好取最大范围最近的质数 
    int h[N],e[N],ne[N],index;

void insert(int x){ 
    	int k=(x%N+N)%N;//将数字存入哈希表先取模是因为插入的x有可能是负数再加N转化为正数，最后再求模可能原本是正数 
    	e[index]=x;
    	ne[index]=h[k];//拉链法就是以h[k]为头结点建立点链表 
    	h[k]=index;
    	index++;
    	
    }

bool query(int x){ 
    	int k=(x%N+N)%N;
    	for(int i=h[k];i!=-1;i=ne[i]){ //遍历单链表 
    		 if(e[i]==x){ 
    		 	return true;
    		 }
    	}
    	return false;
    }

int main(){ 
    	fill(h,h+N,-1);
       int n;
       cin>>n;
       while(n--){ 
       	int x;
       	 char c;
       	 cin>>c;
       	 if(c=='I'){ 
       	 	cin>>x;
       	 	 insert(x);
    		}
    	else{ 
    		cin>>x;
    		if(query(x)){ 
    		   cout<<"Yes"<<endl;	
    		}
    		else{ 
    			cout<<"No"<<endl;
    		}
    	}	
       }
        
        
        return 0;
    }

2.寻址法

#include <iostream>
    #include <string>
    #include <algorithm> 
    #include <vector>
    using namespace std;
    const int N=2e5+7,null=1e9+100;//寻址法一般数组要开大两到三倍的质数
    int h[N];//将h数组全部初始化为不在数据范围的值

int find(int x)
    { 
    	int k=(x%N+N)%N;
    	while(h[k]!=null&&h[k]!=x){ 
    		k++;
    		if(k==N-1){ 
    			k=0;//找到最后一个找不到的时候就回到第一个 
    		}
    	}
    	return k;
     }

int main(){ 
      fill(h,h+N,null);
       int n;
       cin>>n;
       while(n--){ 
       	int x;
       	 char c;
       	 cin>>c;
       	 if(c=='I'){ 
       	 	cin>>x;
       	 	  h[find(x)]=x;
    		}
    	else{ 
    		cin>>x;
    		if(h[find(x)]==null){ 
    		   cout<<"No"<<endl;	
    		}
    		else{ 
    			cout<<"yse"<<endl;
    		}
    	}	
       }
        
        
        return 0;
    }