algorithm - つぶやきハッシュについて説明してください。

Question

私はつぶやきハッシュを見つけました。これは、既知の最速で、衝突耐性が非常に高いようです。完全なソース コードでアルゴリズムまたは実装についてさらに掘り下げようとしましたが、理解するのに苦労しています。ここで誰かが使用されているアルゴリズムを説明したり、完全なソース コード、できれば C で実装したりできますか。著者の Web サイトから C ソース コードを読みましたが、次のようにseedわかりhませkんm。

これは何を意味するのでしょうか？:

k *= m; 
k ^= k >> r; 
k *= m; 
    
h *= m; 
h ^= k;

data += 4;
len -= 4;

参照 : http://murmurhash.googlepages.com/

Answer 1

コードはこちらから入手できます。m と r は、アルゴリズムで使用される定数です。k *= m は、変数 k を取り、それを m 倍することを意味します。k ^= k >> r は、k を取り、r 桁のビットを右シフトし (たとえば、r が 2 の場合、110101 は 001101 になります)、k で XOR することを意味します。

残りの作業に十分対応できることを願っています。

よろしく

Answer 2

Murmurアルゴリズムの最良の説明は、Murmur Hash ウィキペディアのページにあります。

Murmur3_32(キー、レン、シード)
    //注: このバージョンでは、すべての整数演算が実行されます
    //符号なし 32 ビット整数。オーバーフローの場合、
    //結果はアプリケーションによって制限されます
    //モジュロ 2 32演算の。

    c1 ← 0xcc9e2d51
    c2 ← 0x1b873593
    r1←15
    r2←13
    メートル ← 5
    n ← 0xe6546b64

    ハッシュ←シード

    キーの fourByteChunk ごとに
        k ← fourByteChunk

        k←k×c1
        k ← (k ROL r1)
        k←k×c2

        ハッシュ ← ハッシュ XOR k
        ハッシュ ← (ハッシュ ROL r2)
        ハッシュ ← ハッシュ × m + n

    残りのBytesInKey
        残りのバイト数 ← SwapEndianOrderOf(remainingBytesInKey)
        // 注: エンディアン スワッピングは、ビッグ エンディアン マシンでのみ必要です。

        残りバイト数 ← 残りバイト数 × c1
        残りバイト数 ← (残りバイト数 ROL r1)
        残りバイト数 ← 残りバイト数 × c2

        ハッシュ ← ハッシュ XOR 残りのバイト数

    ハッシュ ← ハッシュ XOR len

    ハッシュ ← ハッシュ XOR (ハッシュ SHR 16)
    ハッシュ←ハッシュ×0x85ebca6b
    ハッシュ ← ハッシュ XOR (ハッシュ SRH 13)
    ハッシュ←ハッシュ×0xc2b2ae35
    ハッシュ ← ハッシュ XOR (ハッシュ SHR 16)

そして私自身：