浅谈hash

作者很蒻，在这里总结一下自己学一小点hash的经验。

hash可以用于查找，速度很快，可以近似看作为O(1)的时间复杂度，缺点是占用空间比较大，不过在竞赛中这种空间换时间的方式还是值得的。

哈希冲突是说不同的元素的关键字有可能相同，不能保证一个关键字与元素是一一对应的，这样就产生了哈希冲突。

如果想解决哈希冲突，将每一组元素存到对应的关键字的一个链表里去，如果我们找到了这个元素所在的链表，就要花费线性时间复杂度来查找。

解决哈希冲突还有一种方法，那就是顺序寻址法。顺序寻址法就是如果当前关键字已经有了之前的元素，那么以此向后找，直到找到空的关键字，将该元素存至此关键字。

而哈希，一般用求模运算来确定关键字，mod一般被我们设定成一个很大的素数，只要空间足够，素数的大小越大越好。这样可以有效避免哈希冲突，避免花费线性复杂度来查找元素。

附上hash模板！

 1 #include<iostream>
 2 #include<cstdio>
 3 #define N 50000
 4 #define B 999979
 5 using namespace std;
 6 int tot,adj[B],nxt[N],num[N];
 7 int top,stk[N];
 8 void init(){
 9     tot=0;
10     while(top) adj[stk[top--]]=0;
11 }
12 void insert(int k){
13     int h=k%B;
14     for(int e=adj[h];e;e=nxt[e])
15         if(num[e]==k) return;
16     if(!adj[h]) stk[++top]=h;
17     nxt[++tot]=adj[h],adj[h]=tot;
18     num[tot]=k;
19 }
20 bool query(int k){
21     int h=k%B;
22     for(int e=adj[h];e;e=nxt[e])
23         if(num[e]==k) return 1;
24     return 0;
25 }
26 int a[10000];
27 int main(){
28     init();
29     int n,m;
30     cin>>n;
31     for(int i=1;i<=n;i++){
32         cin>>a[i];
33         insert(a[i]);
34     }
35     cin>>m;
36     int num;
37     for(int i=1;i<=m;i++){
38         cin>>num;
39         if(query(num)) cout<<"Yes/n";
40         else cout<<"No/n";
41     }
42     return 0;
43 } 

又结束了awa