热门问题
时间线
聊天
视角

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

參考

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads