MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明，[4][5] 并出现了多个变种，[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。[7]
变种
当前的版本是MurmurHash3，[8][9] 能够产生出32-bit或128-bit哈希值。
较早的MurmurHash2[10]能产生32-bit或64-bit哈希值。对于大端存储和强制对齐的硬件环境有一个较慢的MurmurHash2可以用。MurmurHash2A 变种增加了Merkle–Damgård 构造，所以能够以增量方式调用。 有两个变种产生64-bit哈希值：MurmurHash64A，为64位处理器做了优化；MurmurHash64B，为32位处理器做了优化。MurmurHash2-160用于产生160-bit 哈希值，而MurmurHash1已经不再使用。
实现
最初的实现是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]。
算法
Murmur3_32(key, len, seed)
c1 0xcc9e2d51
c2 0x1b873593
r1 15
r2 13
m 5
n 0xe6546b64
hash seed
for each fourByteChunk of key
k fourByteChunk
k k * c1
k (k << r1) OR (k >> (32-r1))
k k * c2
hash hash XOR k
hash (hash << r2) OR (hash >> (32-r2))
hash hash * m + n
with any remainingBytesInKey
remainingBytes SwapEndianOrderOf(remainingBytesInKey)
remainingBytes remainingBytes * c1
remainingBytes (remainingBytes << r1) OR (remainingBytes >> (32 - r1))
remainingBytes remainingBytes * c2
hash hash XOR remainingBytes
hash hash XOR len
hash hash XOR (hash >> 16)
hash hash * 0x85ebca6b
hash hash XOR (hash >> 13)
hash hash * 0xc2b2ae35
hash hash XOR (hash >> 16)
参考
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
