题目

---

思路

• 在我们向该结构中插入或者搜索元素时，根据元素的关键码，通过某种函数去计算得到一个存储位置（哈希地址），然后直接用得到的位置来进行插入或者搜索等操作。这种方法就叫做哈希 Hash（散列），这个函数叫做哈希函数（HashFunc）。
• 
• 回顾单链表

---

代码

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
int const n=100003;int h[n],e[n],ne[n],idx;
////h[]是哈希函数的一维数组//e[]是链表中存的值//ne[]是指针存的指向的地址//idx是当前指针void insert(int x)
{int k = (x % n + n) % n; ////对负数的处理,k是哈希值e[idx] = x;ne[idx] = h[k];h[k] = idx ++;                          //如果不同单链表的idx都是从0开始单独计数，//那么不同链表之间可能会产生冲突//比如如果第0个节点被分配给了第一个单链表，//那么所有单链表就只能从下一个节点开始分配，//所以所有单链表需要共用一个idx。//就是单链表的插入操作 开放寻址法
}
bool find(int x)
{int k= (x % n + n) % n;  ///为了让负数在整数有映射,负数的取模还是负数,加上maxn后为正,再%即可for(int i = h[k]; i != -1; i = ne[i])//if(e[i] == x)return true;return false;
}
int main(void)
{cin.tie(0);//减少时间 提高效率int n;  cin>>n;memset(h, -1, sizeof(h));  ///所有槽都清空,对应的是单链表的头(head) 指针为-1表示清空while(n--) {char op[2]; int x;scanf("%s%d", op, &x);if(op[0] == 'I') insert(x);else {if(find(x)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;  }