热门问题
时间线
聊天
视角
Murmur哈希
来自维基百科,自由的百科全书
Remove ads
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)
Remove ads
參考
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads