哈希表：哈希表通过把关键码值（Key value）映射到表中一个位置来访问记录，从而大大加快了查找的速度。

// 1.拉链法
// #include<iostream>
// #include<cstring>
// using namespace std;
// const int N=10013;
// 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 n;
//     cin>>n;
//     memset(h,-1,sizeof h);
//     while(n--)
//     {
//         char op[2];
//         int x;
//         cin>>op>>x;
//         if(op[0]=='I')insert(x);
//         else 
//         {
//             if(find(x))puts("Yes");
//             else puts("No");
//         }
//     }
// }
// //2.开放寻址法
// #include<iostream>
// #include<cstring>
// using namespace std;
// const int N=131,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;1.h[k]==null找到空位了，插入x  2.h[k]==x;
// }

// int main()
// {
//     int n;
//     cin>>n;
//     memset(h,0x3f,sizeof h);

//     while(n--)
//     {
//         char op[2];
//         int x;
//         cin>>op>>x;
//         int k=find(x);
//         插入
//         if(op[0]=='I')h[k]=x;
//         查找
//         else 
//         {
//             if(h[k]!=null)puts("Yes");
//             else puts("No");
//         }
//     }
//     return 0;
// }
// 3.字符串哈希
// 判断区间是否相等
// #include<iostream>
// using namespace std;
// typedef unsigned long long ULL;

// const int N=100010,x=131;

// int n,m;
// char str[N];
// ULL h[N],p[N];//将字母转化为x进制的数字；p[N]存储x^N,每个字母的哈希值;h[N]存储前字符串前几位的哈希值

// ULL get(int l,int r)
// {
//     return h[r]-h[l-1]*p[r-l+1];//求l->r字符串的哈希值
// }

// int main()
// {
//     cin>>n>>m>>(str+1);
//     p[0]=1;
//     for(int i=1;i<=n;i++)
//     {
//         p[i]=p[i-1]*x;
//         h[i]=h[i-1]*x+str[i];
//     }
//     while(m--)
//     {
//         int l1,r1,l2,r2;
//         cin>>l1>>r1>>l2>>r2;
//         if(get(l1,r1)==get(l2,r2))puts("Yes");
//         else puts("No");
//     }
// }