murmurhash

转自:http://www.trueeyu.com/?p=1325

 

 MurmurHash是一种非加密型哈希函数，由Austin Appleby在2008年发明，并且有多个变种。
    特点：对于规律性较强的key，MurmurHash的随机分布特性表现更良好。

    MurmurHash1是第一个版本，速度比Bob Jenkins'的lookup3，但不是非常robust.
    MurmurHash2速度更快并且robust，被应用于Google,Yahoo,Microsoft的很多公司的代码中
    MurmurHash3是最新的版本，开发这个版本的原因是因为第二版有一些小缺陷，MurmurHash3速度比MurmurHash2速度快一点，并且有128-bit的版本，这对于为大数据块的生成identifier是很有用的。

    MurmurHash1的mix function
    h += k;
    h *= m;
    h ^= h >> r;
    k是block的key,h是32-bit hash值，m,k是常数

    MurmurHash2的mix function
    k *= m;
    k ^=k >> r;
    k *= m;
    h *= m;
    h ^= k;
    k是block的key,h是32-bit hash值，m,k是常数

    MurmurHash3的mix function
    k *= c1;
    k = rot1(k, r1)
    k *= c2;
    h ^= k;
    h = rot1(h, r1)
    h = h * m1 + n1;

    详细的hash算法说明，源码链接：http://code.google.com/p/smhasher/wiki/MurmurHash

一.各处版本函数的的详细说明：

版本1：

1.uint32_t MurmurHash1 (const void* key, int len, uint32_t seed)
–生成32位的hash值
–不支持incremental

2.unsigned int MurmurHash1Aligned (const void* key, int len, uisigned int seed)
–生成32位的hash值
–不支持incremental
–只作对齐读

版本2：

3.uint32_t MurmurHash2(const void* key, int len, uint32_t seed)
–生成32位的hash值
–不支持incremental

4.uint64_t MurmurHash64A(const void* key, int len, uint64_t seed)
–生成64位的hash值
–为64位平台设计
–不支持incremental

5.uint64_t MurmurHash64B(const void* key, int len, uint64_t seed)
–生成64位的hash值
–为32位平台设计
–不支持incremental

6.uint32_t MurmurHash2A(const void* key, int len, uint32_t seed)
–使用Merkle-Damgard construction
–对于small key，由于在hash结尾有添加值，所以速度比murmurhash速度慢10%-20%

7.uint32_t MurmurHashNeutral2(const void* key, int len, uint32_t seed)
–算法同MurmurHash2相同，但是endian- and alignment-neutral（兼容不同的字节序和对齐方式）
–速度是MurmrHash2的一半

8.uint32_t MurmurHashAligned2(const void* key, int len, uint32_t seed)
–算法同MurmurHash2相同
–只进行对齐的读
–速度比MurmurHash2慢

版本3

9.void MurmurHash3_x86_32(const void* key, int len, uint32_t seed, void* out)
–生成32位的hash值
–为32位平台设计

10.void MurmurHash3_x86_128(const void* key, const int len, uint32_t seed, void* out)
–生成128位的hash值
–为32位平台设计

11.void MurmurHash3_x64_128(const void* key, const int len, const uint32_t seed, void* out)
–生成128位的hash值
–为64位平台设计