MurmurHash3原理讲解

Murmur哈希是一种非加密函数的哈希函数，下面我们在介绍哈希函数之前我们需要了解一下什么是好的哈希函数(可以通过下面两个测试)。
1.好的哈希函数应该通过卡方测试(chi-squared test)
卡方测试:
$X_c^2={\sum }_{i=0}^{N-1}(O_i-E_i{)}^2/E_i,其中O_i为观察量,而E_i为估计量$
我们测试的方案就是给出大量的数据，然后利用哈希函数计算出他们的哈希值，然后测试这批数据是否符合均匀分布。具体的做法可以参考数理统计第30讲（分类数据与分布拟合的卡方检验）里面的6.4.2的连续分布，也可以自己复习一下概率论与数理统计里面的对应章节的例题进行类比即可。
2.好的哈希函数应该通过雪崩测试(avalanche test)
指的是哈希函数对于输入的敏感度。比如对于一个输入的key1,得到了val1,接下来我们把key1的某一个位或者某一个字符改掉,得到val2，保证val1与val2中间变化的位数至少有50%,这说明对于微小的输入改动，得到的哈希值差别很大，哈希函数的输入敏感度很强。
3.Murmurhash3函数原理
从名字上来看，Murmurhash指的就是mutiply和rotate,组成murmur，即乘和旋转两个操作，但是实际上还有xor异或操作在名字中没有体现。
Murmurhash3分为三个步骤，我们来一步步的讲:

在讲解之前我们需要写出几个常量:(这些常量是根据我们前面两个测试实践测出来发现
这些数据效果是比较好的,当然也可以有更好的数据常量,下面只是做一个参考)
const unsigned int c1 = 0xcc9e2d51;		// 3,432,918,353
const unsigned int c2 = 0x1b873593;		// 461,845,907

const int r1 = 15;
const int r2 = 13;

const int m = 5;
const int n = 0xe6546b64;	//3,864,292,196

//注意,对于32位的机器而言,一个word是4个byte即32bits,下面我们讲解的
//都是针对32位的机器
1.对输入的数据input_data进行4字节分组(每4个字节分一组)
例如:"abcdefghi" --> "abcd","efgh","i",前面两段是正常分组,而对于"i"则是剩余数据
下面我们对"abcde"作为讲解例子:
这里我们的第一个步骤就是对正常的分组数据进行计算:"abcd"
"abcd"==>0x61626364,我们赋给K = 0x61626364(这是一个32bit的block)
//接下来我们就进行下面的操作
K = K*c1
K = K rot by r1 (比如1010这个数据rot by 1,得到的结果就是0101,即进行循环左移一位)
K = K*c2
//在我们的murmurhash3的输入参数中,除了需要进行hash的数据,我们还需要一个随机
//数种子seed,这个seed是一个随机数,可以随机取,这里我定义h = seed
h = h ^ K
h = h rot by r2
h = h*m + n
//以上就是第一部分所左的工作,如果正常分组不止一组,就将上面的部分多循环几遍直到
//每一组都可以完成

//2.接下来我们处理剩余的数据remaining bytes = "e",下面的做法本质就是将数据倒置一下
//比如剩余数据是"efg",倒置得到:gfe,十六进制表示就是0x00676665
unsigned int k = 0
switch(len(remaining_bytes)){
	case 3:k^=remaining_bytes[2]<<16;
	case 2:k^=remaining_bytes[1]<<8;
	case 1:k^=remaining_bytes[0];
}
//然后做如下变换:
k = k * c1
k = k rot by r1
k = k * c2
h ^= k//h是上一步得到的数据
h ^= len(input_data)//本例的input_data = "abcde"那么这里就是h^=5
//到这里我们的第二步就结束了

//3.接下来这一步是最后一步,作用是强化通过雪崩测试,加强输入敏感性,下面的常量内容
//都是经验值,总的步骤就是异或,乘,异或,乘,异或
	h ^= h >> 16;
	h *= 0x85ebca6b;	// 2,246,822,507
	h ^= h >> 13;
	h *= 0xc2b2ae35;	// 3,266,489,909
	h ^= h >> 16;

经过上面的三步最后得到的h就是我们的哈希值了。
代码在这里