计算机系统应用教程网站

网站首页 > 技术文章 正文

MurmurHash算法及应用场景

btikc 2024-09-18 08:43:23 技术文章 53 ℃ 0 评论

算法简介

Murmur哈希算法是一种非加密型哈希算法,适用于一般的哈希检索操作,由Austin Appleby创建于2008年。

之所以说是非加密型,与追求安全的MD5算法不同,它不是专门设计为不可逆转破解,而是追求高性能与低碰撞率。这两个特性会在下文做具体代码验证。

算法解读

Murmur哈希算法名称由来就是它的计算过程:Multiply and Rotate,且在哈希的过程中需要经历多次Multiply and Rotate,因此取名叫Murmur,核心思路就是下面这几行代码(Guava中的算法实现):

可以看到是一个while循环,每次处理4个字符,对这四个字符做:

其中mixK1方法如下:

将计算到的k1旋转rotateLeft方法:

再根据算出来的k1执行mixH1方法:

大家要记住几个关键变量或常量:C1、C2、h1、k1。

k1怎么来的?

int k1 = c0 | (c1 << 8) | (c2 << 16) | (c3 << 24);

h1就是seed,随机数种子,可以自己生成或使用默认的。

其中的C1和C2常量如下:

为什么是这个值呢?其实都是Austin Appleby经过大量实验计算得出来的一个最优数字。

这个算法核心思想就是不断的“k1 *= C1; k1 = rotateLeft(k1, r);”,所以取名叫murmurhash,这样是不是就好记住一点,或者叫陌陌哈希,陌陌总能记住了吧?

实际应用

Murmur算法在Java中有很多具体的实现:

Guava的Hashing:

https://github.com/google/guava/blob/master/guava/src/com/google/common/hash/Murmur3_32HashFunction.java

Jedis中的MurmurHash:

https://github.com/xetorthio/jedis/blob/master/src/main/java/redis/clients/util/MurmurHash.java

Cassandra中的MurmurHash:

https://github.com/apache/cassandra/blob/aa7c7362a94dd3da81ff521589cd2e6f998ae4c1/src/java/org/apache/cassandra/utils/MurmurHash.java

性能测试

比较常用的MD5算法和Murmurhash算法对字符串加密的性能,先写对应的两个方法:

对随机字符串10w次加密随机生成的100位字符串测试耗时:

测试结果:

MD5总耗时:897ms

Murmurhash总耗时:294ms

低碰撞率

Murmurhash的哈希剧烈度要比Java自带的HashCode()要高,高剧烈度即代表着低碰撞率,Hash表的低碰撞率代表着更高的性能。

代码验证一下Murmurhash和jdk自带的hashcode的散列值:

输出如下:

可以看到,对于两个相近的字符串,hashcode的值只相差1位数,而Murmurhash却相差十万八千里。了解hash数据结构的相信大家已经知道意味着什么了。

拓展阅读

Tags:

猜你喜欢

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表