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 hash40 {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 Function40 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 }