哈希表
哈希表是把一个比较大的值域映射到一个比较小的空间
哈希表的存储结构：
1.开放寻址法：当出现冲突时，按照顺序将数据存放到数组的下一个位置。
2.拉链法：当出现冲突时，在这个位置拉一个链，链上是所有满足这一冲突的元素
哈希表的时间复杂度可以看作O( 1 ),一般只会有添加和查找操作。
字符串的哈希方式：
例题：
输入样例：
5 I 1 I 2 I 3 Q 2 Q 5
期望输出：
Yes
No
代码实现：
1.拉链法，需要多开两个数组用来存放数据值和下一个指向地址
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+3; //取大于1e5的一个质数int h[N];//哈希表
int e[N],ne[N],idx;//存放拉链void insert(int a)
{int k = (a % N + N)%N;//因为负数取模还是负数，为了让数变成正数，先取模再加N再取模e[idx] = k; //新建一个结点并赋值ne[idx] = h[k];//让新节点的next指针指向原先h[k]指向的结点h[k]=idx++;//让h[k]指向新结点
}bool query(int a)
{int k = (a % N + N)%N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==a) return true;}return false;
}int main()
{memset(h,-1,sizeof(h));int n;cin>>n;for(int i=1;i<=n;i++){char op[2];int a;scanf("%s%d",op,&a);if(*op=='I') insert(a);else{if(query(a)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}
}
2.开放寻址法，需要将数组多开两到三倍
#include<bits/stdc++.h>
using namespace std;const int N = 3e5+7,null = 0x3f3f3f3f;int h[N];//与拉链法不同的是，find操作会返回元素所在的值或者元素应该在的值
int find(int u)
{int k=(u%N+N)%N;while(h[k]!=null && h[k]!=u){cout<<h[k]<<endl;k++;if(k=N) k=0;}return k;
}int main()
{int n;cin>>n;memset(h,0x3f,sizeof(h));//memset是按字节填充的，int有4个字节，也就是每个数是0x3f3f3f3fwhile(n--){char op[2];int a;scanf("%s%d",op,&a);int k =find(a);if(*op=='I') h[k]=a;else{if(h[k]==a) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}
}