MurmurHash 哈希算法

简单（根据生成的汇编指令数量）。
良好的分布（几乎所有键组和铲斗尺寸均通过卡方检验。
好 雪崩 行为（最大偏差0.5％）。
良好的碰撞阻力（通过Bob Jenkin的frog.c酷刑测试。对于4字节键没有碰撞，没有小的（1到7位）差异）。
在Intel/AMD硬件上表现出色，散列质量和CPU消耗之间的良好折衷。

MurmurHash: (multiply and rotate) and (multiply and rotate) Hash, a hash algorithm that uses multiplication and rotation.

一、Hash函数定义

散列函数（Hash function），又称散列算法或哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。它将数据压缩成摘要，使数据量变小并固定格式。散列函数会打乱混合数据，重新生成一个称为散列值（hash values，hash codes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来表示。好的散列函数在输入域中很少出现散列冲突。

特点

• 加密：散列算法计算得到的散列值具有不可逆性，可有效保护密码。
• 压缩：将任意长度的输入通过散列算法转换为固定长度的输出。
• 应用：保护资料、确保传递真实的信息、散列表、错误校正、语音识别、信息安全等。

常见哈希算法

MD系列（MD5）、SHA系列（SHA-1）、CRC，甚至JDK hashCode()也是一种哈希算法。可以将它们分为三代：

• 第一代：SHA-1（1993）、MD5（1992）、CRC（1975）、Lookup3（2006）
• 第二代：MurmurHash（2008）
• 第三代：CityHash，SpookyHash（2011）

分类可分为加密型和非加密型：

• 加密型：MD系列（MD5）、SHA系列（SHA-1）
• 非加密型：CRC、MurmurHash

这里记录一下在第二代中几乎一统江湖的MurmurHash。

二、MurmurHash定义

MurmurHash是一种非加密型哈希函数，适用于一般的哈希检索操作。由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域。与其他流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。

特点

1. 快速：MurmurHash3比MD5快。
2. 低碰撞：MurmurHash3 128位版本的哈希值与MD5一样，128位的哈希值在数据量较小的情况下基本不会发生碰撞。
3. 高混淆：散列值比较均匀，适用于哈希表、布隆过滤器等，元素会均匀分布。

应用

MurmurHash广泛应用于各开源产品，如Java界中的Redis、Memcached、Cassandra、Hadoop、HBase、Lucene、Spark、Nginx等常见的大数据库底层，都使用了这个算法作为底层的存储算法。

介绍

MD5生成的哈希值为128位。这里的哈希值指的是二进制值，而不是HEX或base64格式化后的可读值。通常我们提到的32位MD5是指由32个字符组成的HEX格式的MD5。MurmurHash算法家族的最新成员是MurmurHash3，支持32位和128位，推荐使用128位的MurmurHash3。它是原作者被Google挖走后基于Murmur2的缺陷进行改进的。

32位的MurmurHash在某些场景下非常有用，比如哈希的对象长度小于128位、存储空间要求较小、需要将字符串转换为整数等。然而，32位哈希值发生碰撞的可能性比128位的要高得多。当数据量达到十万时，很有可能发生碰撞。

Murmur是一个良好的通用散列函数系列，适用于非加密用途。MurmurHash提供以下优点：

• 混淆性好：最大限度地提高分布质量，最小化碰撞次数。
• 适用于散列UUID等高级散列函数的用途，如CityHash、Jenkins、Paul Hsieh等。
• 使用像Murmur这样的工程散列函数可以最大限度地提高分布质量，并最大限度地减少碰撞次数，但它不提供任何其他保证。

三、MurmurHash使用

1. 导入包：Java版可以使用Google Guava包中提供的工具类。

        
            com.google.guava
            guava
            30.1.1-jre
        

四、性能测试

结果：

MD5的性能测试：

MD5结果：

由于我测试的字符串较短，可能是因为使用了不同版本的jar包以及MacOS版本的问题，尽管MurmurHash比MD5快，但性能差距没有达到10倍。

其他性能测试，包括使用hutool包下的MurmurHash.hash64的情况：

getHexHashStringWithGoogle128=3f3d5e5f32f9fff6a34dfa6329a83bf7
getHexHashStringWithGoogle32=2cb92c51
getHexHashStringWithHutool64=4742386bfc5110a8
getHexMD5String=05fbb1053d692f9f6730d1a24e577a92
一亿数据，getHexHashStringWithGoogle128一共花费时间：36秒
一亿数据，getHexHashStringWithGoogle32一共花费时间：19秒
一亿数据，getHexHashStringWithHutool64一共花费时间：18秒
一亿数据，getHexMD5String一共花费时间：62秒