介绍

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域。该名称来自两个基本操作，乘法（MU）和旋转（R），在其内部循环中使用。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。
MurmurHash与加密散列函数不同，它不是专门设计为难以被对手逆转，因此不适用于加密目的。它常被应用于分布式系统，很多开源项目如Kafka、Redis，Memcached，Cassandra，HBase，Elasticsearch等等都使用它。
MurmurHash的当前的版本是MurmurHash3，能够产生出32-bit或128-bit哈希值。

优点

• 速度快，比安全散列算法快几十倍；
• 变化足够激烈，相似的字符串如“abc”和“abd”能够均匀散落在哈希环上；
• 不保证安全性（缺点）；

种类

Murmurhash3
2018年的版本是Murmurhash3，它产生一个32位或128位散列值。 使用128位时，x86和x64版本不会生成相同的值，因为算法针对各自的平台进行了优化。
Murmurhash2
Murmurhash2产生一个32位或64位的值。 较慢版本的Murmurhash2可用于大端和对齐的机器。 Murmurhash2A变体添加了Merkle-Damgård构造，因此可以逐渐调用它。 有两种变体生成64位值; 针对64位处理器的Murmurhash64A和针对32位处理器的Murmurhash64B。 Murmurhash2-160生成160位散列，而Murmurhash1已过时。

Murmurhash3算法

算法描述

算法图例

开源实现

Guava的Hashing类，Jedis和Cassandra的Util类均提供了MurmurHash算法的Java实现

PK

Time33算法
CityHash

附录

哈希

什么是哈希
hash（散列、杂凑）函数，是将任意长度的数据映射到固定长度的域上。
即将一段数据M进行杂糅，然后输出一段数据h。作为他的数据特征（指纹）
即无论m多长，输出的h的长度是固定的。
Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置.
通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址.
比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可

哈希函数
hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。
一句话：散列（Hashing）通过散列函数将要检索的项与索引（散列，散列值）关联起来，生成一种便于搜索的数据结构（散列表）。

哈希函数的性质

• 同一函数的散列值不相同，那么其原始输入也不相同，上图中k1，k3和k4。（确定性）
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是不相同的，上图中的k2，k5这种情况称为“哈希碰撞”。（不确定性）

hash函数的构造准则：简单、均匀

• 散列函数的计算简单，快速；
• 散列函数能将关键字集合K均匀地分布在地址集{0,1，…，m-1}上，使冲突最小。