分析 levelDB 源码的时候遇到的，发现是一个广泛应用的 hash 算法，而且是纯 C 写的，于是找来了源码看。
MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明，[4][5] 并出现了多个变种，[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。[7]
最初的实现是C++的，但是被移植到了其他的流行语言上，包括 Python,[11]C,[12]C#,[9][13]Perl,[14]Ruby,[15]PHP,[16]Haskell,[17]、Scala[18]、Java[19][20]和JavaScript[21][22]等。
这个算法已经被若干开源计划所采纳，最重要的有libstdc++ (4.6版)、Perl[23]、nginx (不早于1.0.1版)[24]、Rubinius[25]、 libmemcached (Memcached的C语言客户端驱动)[26]、maatkit[27]、Hadoop[1]、Kyoto Cabinet[28]以及RaptorDB[29]。
虽然说破天就是一个hash函数。。似乎没什么好分析的？
不过由于是第一次分析有现实意义的代码，所以简单一点也不是罪过吧orz
以及这次分析代码的重点不在hash算法本身，而是算法之外的其他东西。
大概感受下有现实意义的工程代码的布局之类orz
hash函数本身没有分析，这个没什么好分析的吧，应该是类似一种构造：看懂每一步很容易，但是你还是想不出来啊？而且一堆"magic number"
代码很短，也就200行，分析见注释。
详细代码
1/**
2 * `main.c' - murmurhash
3 *
4 * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
5 */
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10#include <unistd.h>
11#include <inttypes.h>
12#include "murmurhash.h"
13
14static void
15usage () {
16 fprintf(stderr, "usage: murmur [-hV] [options]\n");
17}
18
19static void //函数类型和函数名不一行写是什么风格orz
20help () {
21 fprintf(stderr, "\noptions:\n");
22 fprintf(stderr, "\n --seed=[seed] hash seed (optional)");
23 fprintf(stderr, "\n");
24}
25
26static char *
27read_stdin () {
28 size_t bsize = 1024;
29 size_t size = 1;
30 char buf[bsize];
31 char *res = (char *) malloc(sizeof(char) * bsize);
32 char *tmp = NULL;
33
34 // memory issue
35 if (NULL == res) { return NULL; } //申请内存失败了
36
37 // cap
38 res[0] = '\0';
39
40 // read
41 if (NULL != fgets(buf, bsize, stdin)) {
42 // store
43 tmp = res; //异常安全？
44 // resize
45 size += (size_t) strlen(buf);
46 // realloc
47 res = (char *) realloc(res, size);
48
49 // memory issues
50 if (NULL == res) {
51 free(tmp);
52 return NULL;
53 }
54
55 // yield
56 strcat(res, buf); //将buf连接到res后面
57 // printf("buf:%s res:%s\n",buf,res);
58 return res;
59 }
60
61 free(res);
62
63
64 return NULL;
65}
66
67#define isopt(opt, str) (0 == strncmp(opt, str, strlen(str)))
68//比较opt和str前strlen(str)个字符。
69
70#define setopt(opt, key, var) { \
71 char tmp = 0; \
72 size_t len = strlen(key) + 1; \
73 for (int i = 0; i < len; ++i) { tmp = *opt++; } \
74 var = opt; \
75}
76// key是"seed",让len = strlen(key)+1，是为了把seed和‘=’跳过去。
77// 因此seed，‘=’，后面的数字之间不支持有空格。
78// 得到的var是*char型的seed.
79
80
81int
82main (int argc, char **argv) { //argc是命令行的参数个数，**argv是字符串数组
83 char *buf = NULL;
84 char *key = NULL;
85 char *seed = NULL;
86 uint32_t h = 0;
87
88 // parse opts
89 {
90 char *opt = NULL;
91 char tmp = 0;
92
93 // for ( int i = 0 ; i < argc ; i++) printf("Argument %d is %s.\n", i, argv[i]);
94 opt = *argv++; // unused，因为第0个参数就是“murmur”，跳过。
95
96
97 while ((opt = *argv++)) { //argv参数最后会变成null,退出循环
98// printf("opt: %s argv:%s\n",opt,*argv);
99
100 // flags
101 if ('-' == *opt++) {
102 switch (*opt++) {
103 case 'h':
104 return usage(), help(), 0; //直接用了return和逗号表达式，避免了break，代码简洁了（？
105
106 case 'V':
107 fprintf(stderr, "%s\n", MURMURHASH_VERSION);
108 return 0;
109
110 case '-': //参数不要带空格
111 if (isopt(opt, "seed")) {
112 setopt(opt, "seed", seed);
113 }
114 break; //是break而不是return，说明在--seed参数后面还可以跟其他参数。
115 // 如果跟了多个 --seed 参数，前面的参数会被最后一个覆盖掉，hash 结果与最后一个 seed 对应。
116 default:
117 tmp = *opt--;//这个tmp好像没什么用啊？
118 // error
119 fprintf(stderr, "unknown option: `%s'\n", opt);
120 usage();
121 return 1;
122 }
123 }
124 }
125 }
126
127 if (NULL == seed) { //赞！ 避免了手残把等号写成赋值号的可能，下面也都用了这种写法。
128 seed = "0";
129 }
130
131#define hash(key) murmurhash(key, (uint32_t) strlen(key), (uint32_t) atoi(seed));
132 // atoi，把字符串转成了 int 型，然后被强转了。。。
133 if (1 == isatty(0)) { return 1; } // isatty 判断文件描述符是否为终端机（是则为 1，不是为 0）
134 else if (ferror(stdin)) { return 1; }
135 else {
136 buf = read_stdin();
137 if (NULL == buf) { return 1; }
138 else if (0 == strlen(buf)) { buf = ""; }
139 h = hash(buf);
140 printf("%" PRIu32 "\n", h);
141 //PRIu32是头文件inttypes.h包含的宏，用于平台独立的printf编码。
142 //会自动根据平台去对应相应的类型说明符。
143 do {
144 key = read_stdin();
145 if (NULL == key) { break; }
146 else if (0 == strlen(buf)) { buf = ""; }
147 h = hash(buf);
148 printf("%d" PRIu32 "\n", h);
149 } while (NULL != key);
150 }
151
152#undef hash
153
154 return 0;
155}
156
157
158
159
160/**
161 * `murmurhash.h' - murmurhash
162 *
163 * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
164 */
165
166#include <stdlib.h>
167#include <stdio.h>
168#include <stdint.h>
169#include "murmurhash.h"
170
171uint32_t
172murmurhash (const char *key, uint32_t len, uint32_t seed) {
173 uint32_t c1 = 0xcc9e2d51;
174 uint32_t c2 = 0x1b873593;
175 uint32_t r1 = 15;
176 uint32_t r2 = 13;
177 uint32_t m = 5;
178 uint32_t n = 0xe6546b64;
179 uint32_t h = 0;
180 uint32_t k = 0;
181 uint8_t *d = (uint8_t *) key; // 32 bit extract from `key'
182 const uint32_t *chunks = NULL;
183 const uint8_t *tail = NULL; // tail - last 8 bytes
184 int i = 0;
185 int l = len / 4; // chunk length
186
187 h = seed;
188
189 chunks = (const uint32_t *) (d + l * 4); // body
190 tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key'
191
192 // for each 4 byte chunk of `key'
193 for (i = -l; i != 0; ++i) {
194 // next 4 byte chunk of `key'
195 k = chunks[i];
196
197 // encode next 4 byte chunk of `key'
198 k *= c1;
199 k = (k << r1) | (k >> (32 - r1));
200 k *= c2;
201
202 // append to hash
203 h ^= k;
204 h = (h << r2) | (h >> (32 - r2));
205 h = h * m + n;
206 }
207
208 k = 0;
209
210 // remainder
211 switch (len & 3) { // `len % 4'
212 case 3: k ^= (tail[2] << 16);
213 case 2: k ^= (tail[1] << 8);
214
215 case 1:
216 k ^= tail[0];
217 k *= c1;
218 k = (k << r1) | (k >> (32 - r1));
219 k *= c2;
220 h ^= k;
221 }
222
223 h ^= len;
224
225 h ^= (h >> 16);
226 h *= 0x85ebca6b;
227 h ^= (h >> 13);
228 h *= 0xc2b2ae35;
229 h ^= (h >> 16);
230
231 return h;
232}