哈希表

一.模拟散列表：

 1 维护一个集合，支持如下几种操作：
 2 
 3 I x，插入一个数 x；
 4 Q x，询问数 x 是否在集合中出现过；
 5 现在要进行 N 次操作，对于每个询问操作输出对应的结果。
 6 
 7 输入格式
 8 第一行包含整数 N，表示操作数量。
 9 
10 接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
11 
12 输出格式
13 对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
14 
15 每个结果占一行。
16 
17 数据范围
18 1≤N≤105
19 ?109≤x≤109
20 输入样例：
21 5
22 I 1
23 I 2
24 I 3
25 Q 2
26 Q 5
27 输出样例：
28 Yes
29 No

这里有两种写法:

(1)开发寻址法（蹲坑法）：我们只开一个一维数组，但数组的大小一般要开到N*2--N*3，其思想是：先用哈希函数算出，数存放的大概位置，

遇到冲突，则到下一个位置去看有没有人，若有接着往下看。无，说明找到了。

 1 #include 
 2 #include 
 3 
 4 using namespace std;
 5 
 6 const int N = 200003, null = 0x3f3f3f3f;
 7 
 8 int h[N];
 9 
10 int find(int x)//find函数的作用是找到x应该保存到的地方：
11 {
12     int t = (x % N + N) % N;//哈希函数,其作用是将数x映射到我们较小的集合中，即先算出数x要保存的大概位置
13     while (h[t] != null && h[t] != x)//h[t]!null表示t这个位置有人，且人不是x
14     {
15         t ++ ;
16         if (t == N) t = 0;//这一步很重要：
17     }
18     return t;
19 }
20 
21 int main()
22 {
23     memset(h, 0x3f, sizeof h);
24 
25     int n;
26     scanf("%d", &n);
27 
28     while (n -- )
29     {
30         char op[2];
31         int x;
32         scanf("%s%d", op, &x);
33         if (*op == 'I') h[find(x)] = x;
34         else
35         {
36             if (h[find(x)] == null) puts("No");
37             else puts("Yes");
38         }
39     }
40 
41     return 0;
42 }

这里解释一下为什么哈希函数写成：t=(x%N+N)%N;

因为X为-1e9~1e9，而在计算机中，一个负数去取模得到的还是负数，为了保证t不是负数还要加个N，

但如果当x是正数时，x%N+N会大于N，所以还要%N；

还有一种写法是拉链法:

这里直接用y总的：

 1 #include 
 2 #include 
 3 
 4 using namespace std;
 5 
 6 const int N = 100003;
 7 
 8 int h[N], e[N], ne[N], idx;
 9 
10 void insert(int x)
11 {
12     int k = (x % N + N) % N;
13     e[idx] = x;
14     ne[idx] = h[k];
15     h[k] = idx ++ ;
16 }
17 
18 bool find(int x)
19 {
20     int k = (x % N + N) % N;
21     for (int i = h[k]; i != -1; i = ne[i])
22         if (e[i] == x)
23             return true;
24 
25     return false;
26 }
27 
28 int main()
29 {
30     int n;
31     scanf("%d", &n);
32 
33     memset(h, -1, sizeof h);
34 
35     while (n -- )
36     {
37         char op[2];
38         int x;
39         scanf("%s%d", op, &x);
40 
41         if (*op == 'I') insert(x);
42         else
43         {
44             if (find(x)) puts("Yes");
45             else puts("No");
46         }
47     }
48 
49     return 0;
50 }
51 
52 作者：yxc
53 链接：https://www.acwing.com/activity/content/code/content/45308/
54 来源：AcWing
55 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 二.字符串哈希：

这位大佬的讲的特别好：https://www.acwing.com/solution/content/24738/

要在此基础上补充上几点：

1.p[N]这个数组是用来保存p的次方的：

因为p[N]也是ULL 类型，所以当其爆数值时，相当于自动%2^64;

2.关于哈希值的公式推导：

所以 才有h[l,r]=h[r]-h[l-1]*p[r-l+1]