kenju's blog

About Programming, Mathematics, Security and Blockchain

MurmurHashとは何か

背景

RubyのHashTableの実装が知りたくて、ソースコードを読んでいた時に、"MurmurHash"という単語に出会った。何かよくわからなかったので、調べて見た。

https://github.com/ruby/ruby/blob/c08f7b80889b531865e74bc5f573df8fa27f2088/st.c:

/* This hash function is quite simplified MurmurHash3
 * Simplification is legal, cause most of magic still happens in finalizator.
 * And finalizator is almost the same as in MurmurHash3 */

MurmurHash is…

Implementations

他の言語はWikipedia | Implementationsを参考にされたい。

C/C++

https://github.com/aappleby/smhasher

本体。SMHasherの一環として開発されている。src/MurmurHash3.cppが最新バージョンの実際の実装。プラットフォームごと(つまり、プロセッサのビットごと)に最適化された実装が3パターン用意されている

  • void MurmurHash3_x86_32()
  • void MurmurHash3_x86_128()
  • void MurmurHash3_x64_128

https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp

Ruby

https://github.com/ksss/digest-murmurhash

こちらの作成された背景に関しては、以下のブログ記事に詳しい:

http://ksss9.hatenablog.com/entry/2013/12/01/233837

JavaScript

https://github.com/garycourt/murmurhash-js

An optimized JavaScript implementation of the MurmurHash algorithms.

こちらのPoCを元に、ライブラリとして公開しているのが以下のレポジトリ:

https://github.com/perezd/node-murmurhash

NOTE: This is a port of Gary Court’s excellent work, to a commonJS module that can be easily included into a node.js project or the browser. I take no credit for the implementation. I am simply making it easier to use for others.

ソースコード自体は複雑度は置いといて行数自体は少なく、node-murmurhash側のMurmus Hash 3の実装は、50行程度

NPMのダウンロード数は上記の方が多いが、↓のmurmurhash-nativeの方が開発が活発で筋が良さそう(あくまでぱっと見の印象。本番で使う場合はより詳細な検討必要)。

https://github.com/royaltm/node-murmurhash-native

This library provides Austin Appleby’s non-cryptographic “MurmurHash” hashing algorithm functions in a few different flavours.

Main References

http://tanjent.livejournal.com/756623.html

Murmur Hashが最初に公開された記事。 簡単なベンチマークとPoCが記されている。

Version 1は↓:

unsigned int MurmurHash ( const unsigned char * data, int len, unsigned int h )
{
    const unsigned int m = 0x7fd652ad;
    const int r = 16;

    h += 0xdeadbeef;

    while(len >= 4)
    {
        h += *(unsigned int *)data;
        h *= m;
        h ^= h >> r;

        data += 4;
        len -= 4;
    }

    switch(len)
    {
    case 3:
        h += data[2] << 16;
    case 2:
        h += data[1] << 8;
    case 1:
        h += data[0];
        h *= m;
        h ^= h >> r;
    };

    h *= m;
    h ^= h >> 10;
    h *= m;
    h ^= h >> 17;

    return h;
}

https://sites.google.com/site/murmurhash/

MurmurHash 2まで公式情報源として機能していた。2011年の"Update March 1, 2011 - The 32-bit variant of MurmurHash3 is finalized, and this page is deprecated.”で役目を終えた。

UPDATE - If you’re reading this via a link from Google or Reddit, please go here - http://murmurhash.googlepages.com. All future updates about MurmurHash will be posted there. (http://tanjent.livejournal.com/756623.html)

https://github.com/aappleby/smhasher

現在のMurmur Hash 3はGitHub repoで管理されている。非暗号ハッシュアルゴリズムのテストスイートであるSMHasherの一環として開発されている。

The SMHasher suite also includes MurmurHash3, which is the latest version in the series of MurmurHash functions - the new version is faster, more robust, and its variants can produce 32- and 128-bit hash values efficiently on both x86 and x64 platforms.

http://www.yosbits.com/wordpress/?p=1442

高速ハッシュアルゴリズムのまとめ。ざっくりまとめが読みたい時に重宝。

  • MurmurHash
  • CityHash
  • FarmHash
  • xxHash
  • SipHash