模拟散列表(哈希表)

哈希表
哈希表是把一个比较大的值域映射到一个比较小的空间
哈希表的存储结构：
1.开放寻址法：当出现冲突时，按照顺序将数据存放到数组的下一个位置。
2.拉链法：当出现冲突时，在这个位置拉一个链，链上是所有满足这一冲突的元素

 哈希表的时间复杂度可以看作O( 1 ),一般只会有添加和查找操作。
字符串的哈希方式：
例题：

输入样例：

1. 5
2. I 1
3. I 2
4. I 3
5. Q 2
6. Q 5

复制代码

期望输出：

1. Yes
2. No

复制代码

代码实现：
1.拉链法，需要多开两个数组用来存放数据值和下一个指向地址
[code]#includeusing 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)     {         if(e==a) return true;     }     return false;}int main(){    memset(h,-1,sizeof(h));    int n;    cin>>n;    for(int i=1;i