murmurhash3 学习笔记

背景

由于项目中有报文排重需求,所以会将报文字符串作为分布式锁key。
考虑到报文不定长并且散列性不太好,如其作为锁key,特别是当key值过大时,使用redis进行读写都会有相对的性能下降。

参考文献里测试对比:
长度为10:写平均耗时0.053ms,读0.040ms
长度为20000:写平均耗时0.352ms,读0.084ms

一种简单的方案是对报文进行一次md5,然后拿来做key。
考虑到md5的性能并不高,找到了更合适的murmurhash3非加密哈希算法:

murmurhash3 学习笔记

算法图例

murmurhash3 学习笔记

(可以看到里面有c1, c2, n 三个很特别的常量,据算法作者Austin Appleby讲,都是他血汗地用大量测试数据调测出来的,为了不被其他好事之徒当头一暴击,他保留继续微调的权利。)

参考文档里都说murmurhash3棒棒的,但是不实践下还是不能随意拿来进献给Boss, 我找了一个代码,做了一个性能对比,测试使用了Google的guava里的Hashing.murmur3_32(),对比apache的commons-lang3的md5Hex算法。

测试源码

public class HashTest {

    public static String md5Test(String primaryKey) {
        return DigestUtils.md5Hex(primaryKey).substring(0, 4) + "_" + primaryKey;
    }

    public static String murmur3Test(String primaryKey) {
        return Hashing.murmur3_32().hashString(primaryKey, StandardCharsets.UTF_8).toString().substring(0, 4) + 
            "_" + primaryKey;
    }
}

跑测试源码如下(为方便直接用了Spock单测脚本):


@Unroll
class HashTestSpec extends Specification {

    def "HashTest md5 & murmurhash3"() {
        long startTime=System.currentTimeMillis()
        for (int i = 0; i < 10000; i++) {
            HashTest.md5Test(getRandomString(10))
        }
        long endTime=System.currentTimeMillis()
        print "1万次md5算法程序运行时间: " + (endTime - startTime ) + "ms"
        print "\n"

        long startTime2=System.currentTimeMillis()
        for (int i = 0; i < 10000; i++) {
            HashTest.murmur3Test(getRandomString(10))
        }
        long endTime2=System.currentTimeMillis()
        print "1万次murmurhash3算法程序运行时间: " + (endTime2 - startTime2 ) + "ms"
        expect:
        1==1
    }
}

对比测试结果:
1万次md5算法程序运行时间: 235ms
1万次murmurhash算法程序运行时间: 73ms

有4倍的差距。

按参考文档建议,换成murmur3_128,1万次murmurhash算法程序运行时间: 51ms, 果然更优秀。

getRandomString的参考代码也一并附上,方便好事之徒做复现。

    public static String getRandomString(int length){
        String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(62);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }

参考

上一篇:金融行业数据实时共享场景下的动态脱敏技术


下一篇:面向网络运营者的等保2.0最全实用解读!