哈希表

1、思路

1、拉链法

2、开放寻址法

开数组要到输入范围的2~3倍，冲突的概率就很小。

2、代码模板

1、拉链法

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e5+3;		//1e5+3是大于1e5的最小质数

int h[N],e[N],ne[N],idx;		//h就是槽，拉链就是之前的链表 ，e存值，ne存下一位地址，idx表示当前用到了哪个位置 
void insert(int x)
{
	int k=(x%N+N)%N;		//加N再%N是为了让k为正数
	e[idx]=x;				//先存入新的值
	ne[idx]=h[k];			//指向下一个位置 
	h[k]=idx++; 			//h[k]存的下一个位置。刚开始h[k]=-1，之后不断加点，但最后一个就是-1  
}
bool find(int x)
{
	int k=(x%N+N)%N; 		//同理 
	for(int i=h[k];i!=-1;i=ne[i])//从h[k]头节点开始，遍历拉链 
		if(e[i]==x)					//当找到时 
			return true;	
} 
int main()
{
	int n;
	scanf("%d",&n);
	memset(h,-1,sizeof h);	 
	while(n--)
	{
		char op[2];
		int x;
		scanf("%s%d",op,&x);
		if(*op=='I')
			insert(x);			//插入x 
		else
		{
			if(find(x))
				puts("Yes");
			else
				puts("No");	
		}		
	} 
	return 0;
} 

2、开放寻址法

#include<iostream>
#include<cstring>
using namespace std;

const int N=2e5+3;		//1e5+3是大于1e5的最小质数
const int null=0x3f3f3f3f;	//一个大于1e9次方的数，约定要是等于这个数，就是这个位置当前没有存值 
int h[N];		 		//

int find(int x)			//核心操作，如果找到了返回位置，没找到就返回它应该存储的位置 
{
	int k=(x%N+N)%N;
	while(h[k]!=null&&h[k]!=x)//如果当前位置已经被占，且存的不是要找的数 
	{
		k++;
		if(k==N)			//当k已经循环到了最后，就从第1个开始 
			k=0; 	
	}
	return k;	
} 
int main()
{
	int n;
	scanf("%d",&n);
	memset(h,0x3f,sizeof h);	    //memset是字节赋值，所以只用写一个3f,int类型四个字节 
	while(n--)
	{
		char op[2];
		int x;
		scanf("%s%d",op,&x);
		int k=find(x);
		if(*op=='I')			//插入x 
			h[k]=x;
		else					//寻找x 
		{
			if(h[k]!=null)		//找到的位置不是空就是找到了 
				puts("Yes");
			else
				puts("No");	
		}		
	} 
	return 0;
} 

3、题目