murmurhash源码分析

分析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 (MemcachedC语言客户端驱动)[26]、maatkit[27]Hadoop[1]、Kyoto Cabinet[28]以及RaptorDB[29]

虽然说破天就是一个hash函数。。似乎没什么好分析的?

不过由于是第一次分析有现实意义的代码,所以简单一点也不是罪过吧orz

以及这次分析代码的重点不在hash算法本身…而是算法之外的其他东西…

大概感受下有现实意义的工程代码的布局之类orz

hash函数本身没有分析…这个没什么好分析的吧…应该是类似一种构造,看懂每一步很容易,但是你还是想不出来啊?而且一堆”magic number”

代码很短,也就200行,分析见注释。