[数据结构与算法]acwing840 模拟散列表 2021/11/27

维护一个集合，支持如下几种操作：

1. I x，插入一个数?xx；
2. Q x，询问数?xx?是否在集合中出现过；

现在要进行?NN?次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数?NN，表示操作数量。

接下来?NN?行，每行包含一个操作指令，操作指令为?I x，Q x?中的一种。

输出格式

对于每个询问指令?Q x，输出一个询问结果，如果?xx?在集合中出现过，则输出?Yes，否则输出?No。

每个结果占一行。

数据范围

1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

?一般来说，hash表的时间复杂度可以看作o1

这里先分享一下拉链法，会用到之前的单链表，但是我单链表的题没写题解，等会我去回头写一下单链表的题解

这个拉链法就是在坐标为0~1e5-1 的哈希表坐标上，在各个槽点分出去链表，算是每个槽点的值，运用单链表的方法来存储，然后在查询的时候，用同样的方法获得哈希表下标，然后一个个遍历这个槽点的值。

这个取哈希表坐标的方法叫除留余数法，mod的值应该是个质数，所以这道题取N = 1e5 + 3?

memset用法是把数组内所有的值赋值同一个数

memset(data, 0, sizeof(data)); 就是把data【】数组的值全部赋值为0；

它插入的时候是一直在交界处增加新值。

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 1e5 + 3 ;
int h[N] , e[N] , ne[N] , idx ;
void insert(int x)
{
    int k = (x % N + N) % N ;
    e[idx] = x ;
    ne[idx] = h[k] ; // 
    h[k] = idx ++ ;
}
bool find(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()
{
    int x ;
    int n ;
    cin >> n ;
    memset(h , -1 , sizeof(h)) ;
    while(n--)
    {
        char op[2];
    scanf("%s%d" , op , &x);
    if(*op == 'I')
    {
        insert(x);
    }
    else
    {
        if(find(x)) cout << "Yes" <<endl;
        else cout << "No" << endl ;
    }
    }
    
}

?开放寻址法（蹲坑法）

只需要一个数组，find函数返回“坑位”

0×3f3f3f3f是acm中常用的无穷大变量

这个方法的数组长度是给定长度的2~3倍，所以这里N = 2e5 + 3

当k==N的时候相当于坑位走了一遍，让k从第0个坑位重新找hh

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 2e5 + 3  , null = 0x3f3f3f3f;
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 = 0 ;
      }
     return  k ;
}
int main()
{
    int n ;
    cin >> n ;
    memset(h , 0x3f , sizeof h) ;
    while(n--)
    {
      char op[2];
      int x ;
      scanf("%s%d" , op , &x);
      int k = find(x) ;
      if(*op == 'I')
      {
        h[k] = x ;
      }
      else
      {
        if(h[k] != null) cout << "Yes" <<endl;
        else cout << "No" << endl ;
      }
    }
   return 0 ;
}

?