常见字符串哈希函数

最常用的两个：

 1          
 2 const int MAXN = 1000003;
 3 
 4 常用1
 5 1  SDBMHash
 6 int SDBMHash(char *str)
 7 {
 8     int hash = 0;
 9     while (*str) hash = (*str++) + (hash << 6) + (hash << 16) - hash;
10     return (hash & 0x7FFFFFFF) % MAXN;
11 }
12  
13 
14 常用2 
15 
16 int BKDRHash(char *str)
17 {
18     int seed = 131; 
19     int hash = 0;
20     while (*str) hash = hash * seed + (*str++);
21     return (hash & 0x7FFFFFFF) % MAXN;
22 }

最常见的8个：

  1 const int MAXN = 1000003;
  2 
  3 //常用 1
  4 1  SDBMHash
  5 unsigned int SDBMHash(char *str)
  6 {
  7     unsigned int hash = 0;
  8     while (*str)
  9     {
 10         // equivalent to: hash = 65599*hash + (*str++);
 11         hash = (*str++) + (hash << 6) + (hash << 16) - hash;
 12     }
 13     return (hash & 0x7FFFFFFF)%MAXN;
 14 }
 15  
 16 2  RS Hash Function
 17 unsigned int RSHash(char *str)
 18 {
 19     unsigned int b = 378551;
 20     unsigned int a = 63689;
 21     unsigned int hash = 0;
 22  
 23     while (*str)
 24     {
 25         hash = hash * a + (*str++);
 26         a *= b;
 27     }
 28     return (hash & 0x7FFFFFFF)%MAXN;
 29 }
 30  
 31 3 JS Hash Function
 32 unsigned int JSHash(char *str)
 33 {
 34     unsigned int hash = 1315423911;
 35  
 36     while (*str)
 37     {
 38         hash ^= ((hash << 5) + (*str++) + (hash >> 2));
 39     }
 40     return (hash & 0x7FFFFFFF)%MAXN;
 41 }
 42  
 43 4 P. J. Weinberger Hash Function
 44 unsigned int PJWHash(char *str)
 45 {
 46     unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
 47     unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
 48     unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
 49     unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
 50     unsigned int hash             = 0;
 51     unsigned int test             = 0;
 52     while (*str)
 53     {
 54         hash = (hash << OneEighth) + (*str++);
 55         if ((test = hash & HighBits) != 0)
 56         {
 57             hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
 58         }
 59     }
 60     return (hash & 0x7FFFFFFF)%MAXN;
 61 }
 62  
 63 5 ELF Hash Function
 64 unsigned int ELFHash(char *str)
 65 {
 66     unsigned int hash = 0;
 67     unsigned int x    = 0;
 68     while (*str)
 69     {
 70         hash = (hash << 4) + (*str++);
 71         if ((x = hash & 0xF0000000L) != 0)
 72         {
 73             hash ^= (x >> 24);
 74             hash &= ~x;
 75         }
 76     }
 77     return (hash & 0x7FFFFFFF)%MAXN;
 78 }
 79  
 80 //常用2 
 81 6 BKDR Hash Function
 82 unsigned int BKDRHash(char *str)
 83 {
 84     unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
 85     unsigned int hash = 0;
 86     while (*str)
 87     {
 88         hash = hash * seed + (*str++);
 89     }
 90     return (hash & 0x7FFFFFFF)%MAXN;
 91 }
 92  
 93 7 DJB Hash Function
 94 unsigned int DJBHash(char *str)
 95 {
 96     unsigned int hash = 5381;
 97     while (*str)
 98     {
 99         hash += (hash << 5) + (*str++);
100     }
101     return (hash & 0x7FFFFFFF)%MAXN;
102 }
103  
104 8 AP Hash Function
105 unsigned int APHash(char *str)
106 {
107     unsigned int hash = 0;
108     int i;
109     for (i=0; *str; i++)
110     {
111         if ((i & 1) == 0)
112         {
113             hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
114         }
115         else
116         {
117             hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
118         }
119     }
120     return (hash & 0x7FFFFFFF)%MAXN;
121 }

原文链接：http://blog.csdn.net/cgl1079743846/article/details/7833794