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位平台设计

二.性能测试:

Comments

2013-06-21