哈希模板

 1 一维哈希
 2 const int MAX=100007;
 3 bool Hash[MAX];
 4 int idx[MAX];
 5 int val[MAX];
 6 
 7 void Insert(int id,int num)
 8 {
 9     int k=num%MAX;
10     while(Hash[k] && val[k]!=num)
11     {
12         k++;
13         if(k==MAX) k=k-MAX;
14     }
15     if(!Hash[k])
16     {
17         Hash[k]=1;
18         idx[k]=id;
19         val[k]=num;
20     }
21 }
22 
23 int found(int num)
24 {
25     int k=num%MAX;
26     while( Hash[k] && val[k]!=num)
27     {
28         k++;
29         if( k==MAX) k=k-MAX;
30     }
31     if( !Hash[k]) return -1;
32     return idx[k];
33 }
34 二维哈希，而且优化。hash表如果用开放地址线性探测法解决冲突的话，很容易超时，
35 而用链地址法解决冲突效果要好很多。
36 这种哈希，相当于邻接表一样的。
37 但是表头为空，所以memset（）。其实也挺好理解的。
38 
39 struct hash
40 {
41     int x;
42     int y;
43     struct hash *next;
44 };
45 struct hash hash_table[1003];
46 
47 
48 void Insert(int x,int y)
49 {
50     unsigned k=(x*x+y*y)%INF;
51     struct hash *new_hash;
52     new_hash=(struct hash *)malloc(sizeof(struct hash));
53     new_hash->x=x;
54     new_hash->y=y;//build 
55 
56     new_hash->next=hash_table[k].next;
57     hash_table[k].next=new_hash;
58 }
59 bool found(int x,int y)
60 {
61     unsigned k=(x*x+y*y)%INF;
62     struct hash *new_hash;
63     new_hash=hash_table[k].next;
64     while(new_hash!=NULL)
65     {
66         if(new_hash->x==x && new_hash->y==y)break;
67         else new_hash=new_hash->next;
68     }
69     if(new_hash)return false;
70     return true;
71 }
72 memset(hash_table,0,sizeof(hash_table));

字符串哈希

 1 const int MAX = 100007;
 2 bool Hash1[MAX];
 3 bool Hash2[MAX];
 4 int num1[MAX],num2[MAX];
 5 int val1[MAX],val2[MAX];
 6 char xx1[100002][22];int xlen1,cur;
 7 char xx2[100002][82];int xlen2;
 8 
 9 void Insert(int x,bool *hash,int *num,int *val,int len)
10 {
11     int k=x%MAX;
12     while(hash[k]==true && num[k]!=x)
13     {
14         k++;
15         if(k==MAX) k=k-MAX;
16     }
17     if(hash[k]==false)
18     {
19         hash[k]=true;
20         num[k]=x;
21         val[k]=len;
22     }
23 }
24 bool found(int x,bool *hash,int *num,int *val)
25 {
26     int k=x%MAX;
27     while(hash[k]==true && num[k]!=x)
28     {
29         k++;
30         if(k==MAX) k=k-MAX;
31     }
32     if(num[k]==x)
33     {
34         cur=val[k];
35         return true;
36     }
37     return false;
38 }
39 // ELF Hash Function
40 unsigned int ELFHash(char *str)
41 {
42     unsigned int hash = 0;
43     unsigned int x = 0;
44     while (*str)
45     {
46         hash = (hash << 4) + (*str++);
47         if ((x = hash & 0xF0000000L) != 0)
48         {
49             hash ^= (x >> 24);
50             hash &= ~x;
51         }
52     }
53     return (hash & 0x7FFFFFFF);
54 }