从数学理论上来讲，没有可行的方案用于设计“完美”的哈希函数。现实中，哈希的设计显然不是技术问题，而是艺术问题。
但是请记住：任何一种哈希总有它的优缺点。
先看代码：
  1 unsigned int RSHash(const std::string& str)
  2 {
  3    unsigned int b    = 378551;
  4    unsigned int a    = 63689;
  5    unsigned int h = 0;
  6 
  7    for(std::string::size_type i = 0; i < str.size(); ++i)
  8    {
  9       h = h * a + str[i];
 10       a = a * b;
 11    }
 12 
 13    return h;
 14 }
 15 /* End Of RS Hash Function */
 16 
 17 unsigned int JSHash(const std::string& str)
 18 {
 19    unsigned int h = 1315423911;
 20 
 21    for(std::string::size_type i = 0; i < str.size(); ++i)
 22    {
 23       h ^= ((h << 5) + str[i] + (h >> 2));
 24    }
 25 
 26    return h;
 27 }
 28 /* End Of JS Hash Function */
 29 
 30 unsigned int PJWHash(const std::string& str)
 31 {
 32    unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
 33    unsigned int ThreeQuarters     = (unsigned int)((BitsInUnsignedInt  * 3) / 4);
 34    unsigned int OneEighth         = (unsigned int)(BitsInUnsignedInt / 8);
 35    unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
 36    unsigned int h              = 0;
 37    unsigned int test              = 0;
 38 
 39    for(std::string::size_type i = 0; i < str.size(); ++i)
 40    {
 41       h = (h << OneEighth) + str[i];
 42 
 43       if((test = h & HighBits)  != 0)
 44       {
 45          h = (( h ^ (test >> ThreeQuarters)) & (~HighBits));
 46       }
 47    }
 48 
 49    return h;
 50 }
 51 /* End Of  P. J. Weinberger Hash Function */
 52 
 53 unsigned int ELFHash(const std::string& str)
 54 {
 55    unsigned int h = 0;
 56    unsigned int x    = 0;
 57 
 58    for(std::string::size_type i = 0; i < str.size(); ++i)
 59    {
 60       h = (h << 4) + str[i];
 61       if((x = h & 0xF0000000L) != 0)
 62       {
 63          h ^= (x >> 24);
 64       }
 65       h &= ~x;
 66    }
 67 
 68    return h;
 69 }
 70 /* End Of ELF Hash Function */
 71 
 72 unsigned int BKDRHash(const std::string& str)
 73 {
 74    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
 75    unsigned int h = 0;
 76 
 77    for(std::string::size_type i = 0; i < str.size(); ++i)
 78    {
 79       h = (h * seed) + str[i];
 80    }
 81 
 82    return h;
 83 }
 84 /* End Of BKDR Hash Function */
 85 
 86 unsigned int SDBMHash(const std::string& str)
 87 {
 88    unsigned int h = 0;
 89 
 90    for(std::string::size_type i = 0; i < str.size(); ++i)
 91    {
 92       h = str[i] + (h << 6) + (h << 16) - h;
 93    }
 94 
 95    return h;
 96 }
 97 /* End Of SDBM Hash Function */
 98 
 99 unsigned int DJBHash(const std::string& str)
100 {
101    unsigned int h = 5381;
102 
103    for(std::string::size_type i = 0; i < str.size(); ++i)
104    {
105       h = ((h << 5) + h) + str[i];
106    }
107 
108    return h;
109 }
110 /* End Of DJB Hash Function */
111 
112 unsigned int DEKHash(const std::string& str)
113 {
114    unsigned int h = str.size();
115 
116    for(std::string::size_type i = 0; i < str.size(); ++i)
117    {
118       h = ((h << 5) ^ (h >> 27)) ^ str[i];
119    }
120 
121    return h;
122 }
123 /* End Of DEK Hash Function */
124 
125 unsigned int BPHash(const std::string& str)
126 {
127    unsigned int h = 0;
128    for(std::string::size_type i = 0; i < str.size(); ++i)
129    {
130       h = h << 7 ^ str[i];
131    }
132 
133    return h;
134 }
135 /* End Of BP Hash Function */
136 
137 unsigned int FNVHash(const std::string& str)
138 {
139    const unsigned int fnv_prime = 0x811C9DC5;
140    unsigned int h = 0;
141    for(std::string::size_type i = 0; i < str.size(); ++i)
142    {
143       h *= fnv_prime;
144       h ^= str[i];
145    }
146 
147    return h;
148 }
149 /* End Of FNV Hash Function */
150 
151 unsigned int APHash(const std::string& str)
152 {
153    unsigned int h = 0xAAAAAAAA;
154 
155    for(std::string::size_type i = 0; i < str.size(); ++i)
156    {
157       h ^= ((i & 1) == 0) ? ((h <<  7) ^ str[i] * (h >> 3)) :
158                             (~((h << 11) + (str[i] ^ (h >> 5))));
159    }
160 
161    return h;
162 }
163 /* End Of AP Hash Function */
164 
165 unsigned int BMFHash(const std::string& str)
166 {
167   const char* itr = str.c_str();
168   std::string::size_type len = str.size();
169   unsigned int loop = 0;
170   unsigned int h = 1;
171   while(len >= 8)
172   {
173     const unsigned int& i1 = *(reinterpret_cast<const unsigned int*>(itr));
174     itr += sizeof(unsigned int);
175     const unsigned int& i2 = *(reinterpret_cast<const unsigned int*>(itr));
176     itr += sizeof(unsigned int);
177     h ^= (h <<  7) ^  i1 * (h >> 3) ^ (~((h << 11) + (i2 ^ (h >> 5))));
178     len -= 8;
179   }
180   while(len >= 4)
181   {
182     const unsigned int& i = *(reinterpret_cast<const unsigned int*>(itr));
183     if(loop & 0x01)
184       h ^= (h <<  7) ^ i * (h >> 3);
185     else
186       h ^= (~((h << 11) + (i ^ (h >> 5))));
187     ++loop;
188     len -= 4;
189     itr += sizeof(unsigned int);
190   }
191   while(len >= 2)
192   {
193     const unsigned short& i = *(reinterpret_cast<const unsigned short*>(itr));
194     if(loop & 0x01)
195       h ^= (h << 7) ^ i * (h >> 3);
196     else
197       h ^= (~((h << 11) + (i ^ (h >> 5))));
198     ++loop;
199     len -= 2;
200     itr += sizeof(unsigned short);
201   }
202   if(0 < len)
203     h += ((*itr) ^ (h * 0xA5A5A5A5)) + loop;
204   return h;
205 }
206 /* End Of Bloom Filter Hash Function */
207

最终结果：

375050个字符窜(小的几个字符大的几百个字符)，进行6108120(很多重复)次操作，用不同哈希函数的哈希表速度(std::unordered_set)对比，单位：毫秒。

测试环境：系统WinXP，g++4.6.3(-O3)，Intel I3 2120，2G内存

哈希

RS

JS

PJW

ELF

BKDR

SDBM

DJB

DEK

BP

FNV

AP

BMF

插入

1529

1783.12

2594.24

2612.27

1534.49

1586.76

1548.43

1447.74

无穷大

1591.83

2078.48

1277.42

查找

1316.3

1506.2

2162.45

2178.9

1311.76

1308.41

1307.99

1257.59

无穷大

1311.85

1719.16

1219.48

删除

1974.04

2244.73

3447.51

3466.72

1923.81

1911.25

1961.45

1842.1

无穷大

1900.16

2600.93

1384.3

 结论：相对复杂的Bloom filter以微弱优势胜出，简单的DEK哈希值得称赞。


除了上面12个哈希函数外，下面两个也许更好用，看上去比上面那些都复杂。

murmur哈希。其中unint32_t就是32位无符号整型，大概相当于unsigned long。

 1 // subject to change
 2 #define ROT32(x, y) ((x << y) | (x >> (32 - y)))
 3 uint32_t murmur3(const char *key, uint32_t len, uint32_t seed)
 4 {
 5     static const uint32_t c1 = 0xcc9e2d51;
 6     static const uint32_t c2 = 0x1b873593;
 7     static const uint32_t r1 = 15;
 8     static const uint32_t r2 = 13;
 9     static const uint32_t m = 5;
10     static const uint32_t n = 0xe6546b64;
11 
12     uint32_t val = seed;
13 
14     const int nblocks = len >> 2;
15     const uint32_t *blocks = (const uint32_t*) key;
16     int i;
17     uint32_t k;
18     for(i = 0; i < nblocks; i++)
19   {
20         k = blocks[i];
21         k *= c1;
22         k = ROT32(k, r1);
23         k *= c2;
24 
25         val ^= k;
26         val = ROT32(val, r2) * m + n;
27     }
28 
29     const uint8_t *tail = (const uint8_t*) (key + nblocks * 4);
30     uint32_t k1 = 0;
31 
32     switch(len & 3)
33     {
34     case 3:
35         k1 ^= tail[2] << 16;
36     case 2:
37         k1 ^= tail[1] << 8;
38     case 1:
39         k1 ^= tail[0];
40 
41         k1 *= c1;
42         k1 = ROT32(k1, r1);
43         k1 *= c2;
44         val ^= k1;
45     }
46 
47     val ^= len;
48     val ^= (val >> 16);
49     val *= 0x85ebca6b;
50     val ^= (val >> 13);
51     val *= 0xc2b2ae35;
52     val ^= (val >> 16);
53 
54     return val;
55 }

crapwow不为多数人所知，但是这个哈希函数的效果比murmur还要稍微好一点。除此之外还有Google的CityHash，特别复杂，据说比murmur也好一点，没有和crapwow对比过。

 1 uint32_t crapwow(const char* key, uint32_t len, uint32_t seed)
 2 {
 3 #if !defined(__LP64__) && (defined __i386__) && (defined __GNUG__)
 4   // esi = k, ebx = h
 5   uint32_t val;
 6   asm(
 7       "leal 0x5052acdb(%%ecx,%%esi), %%esi\n"
 8       "movl %%ecx, %%ebx\n"
 9       "cmpl $8, %%ecx\n"
10       "jb DW%=\n"
11       "QW%=:\n"
12       "movl $0x5052acdb, %%eax\n"
13       "mull (%%edi)\n"
14       "addl $-8, %%ecx\n"
15       "xorl %%eax, %%ebx\n"
16       "xorl %%edx, %%esi\n"
17       "movl $0x57559429, %%eax\n"
18       "mull 4(%%edi)\n"
19       "xorl %%eax, %%esi\n"
20       "xorl %%edx, %%ebx\n"
21       "addl $8, %%edi\n"
22       "cmpl $8, %%ecx\n"
23       "jae QW%=\n"
24       "DW%=:\n"
25       "cmpl $4, %%ecx\n"
26       "jb B%=\n"
27       "movl $0x5052acdb, %%eax\n"
28       "mull (%%edi)\n"
29       "addl $4, %%edi\n"
30       "xorl %%eax, %%ebx\n"
31       "addl $-4, %%ecx\n"
32       "xorl %%edx, %%esi\n"
33       "B%=:\n"
34       "testl %%ecx, %%ecx\n"
35       "jz F%=\n"
36       "shll $3, %%ecx\n"
37       "movl $1, %%edx\n"
38       "movl $0x57559429, %%eax\n"
39       "shll %%cl, %%edx\n"
40       "addl $-1, %%edx\n"
41       "andl (%%edi), %%edx\n"
42       "mull %%edx\n"
43       "xorl %%eax, %%esi\n"
44       "xorl %%edx, %%ebx\n"
45       "F%=:\n"
46       "leal 0x5052acdb(%%esi), %%edx\n"
47       "xorl %%ebx, %%edx\n"
48       "movl $0x5052acdb, %%eax\n"
49       "mull %%edx\n"
50       "xorl %%ebx, %%eax\n"
51       "xorl %%edx, %%esi\n"
52       "xorl %%esi, %%eax\n"
53       : "=a"(val), "=c"(len), "=S"(len), "=D"(key)
54       : "c"(len), "S"(seed), "D"(key)
55       : "%ebx", "%edx", "cc"
56      );
57   return val;
58 #else
59   #define CWFOLD(a, b, lo, hi) \
60   {\
61     p = (uint32_t)(a) * (uint64_t)(b);\
62     lo ^= (uint32_t)p;\
63     hi ^= (uint32_t)(p >> 32);\
64   }
65 
66   #define CWMIXA(in) { CWFOLD(in, m, k, h); }
67   #define CWMIXB(in) { CWFOLD(in, n, h, k); }
68 
69   const uint32_t m = 0x57559429;
70   const uint32_t n = 0x5052acdb;
71   const uint32_t* key4 = (const uint32_t*)key;
72   uint32_t h = len;
73   uint32_t k = len + seed + n;
74   uint64_t p;
75 
76   while(len >= 8)
77   {
78     CWMIXB(key4[0])
79     CWMIXA(key4[1])
80     key4 += 2;
81     len -= 8;
82   }
83 
84   if(len >= 4)
85   {
86     CWMIXB(key4[0])
87     key4 += 1;
88     len -= 4;
89   }
90 
91   if(0 != len)
92   {
93     CWMIXA(key4[0] & ((1 << (len * 8)) - 1 ))
94   }
95 
96   CWMIXB(h ^ (k + n))
97   return k ^ h;
98 #endif
99 }