hash函数MurmurHash「建议收藏」
hash函数MurmurHash「建议收藏」
全栈程序员站长
发布于 2022-11-02 16:47:18
发布于 2022-11-02 16:47:18
一、介绍
MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。
Java界中Redis，Memcached，Cassandra，HBase，Lucene都用它。
在Java的实现，Guava的Hashing类里有，上面提到的Jedis，Cassandra里都有Util类。
但存在的问题是由于Java的数据类型long与C语言中无符号长整型uint64_t有区别，导致Java输出版本存在负数，针对这个问题进行了修改；另外需要注意的是中文不同编码（UTF-8或GBK）会导致输出结果的不同，使用中需要统一编码。
二、原理
hash函数MurmurHash「建议收藏」
算法图例
hash函数MurmurHash「建议收藏」
三、性能测试对比
import java.nio.charset.StandardCharsets;
import org.apache.commons.codec.digest.DigestUtils;
import com.google.common.hash.Hashing;
public class Test {
public static void main(String[] args) {
System.out.println(murmur3Test("334324324234234sfsfsdfwwrtregreg"));
long startTime=System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
Test.md5Test("KFETHGRETWERFSDFWEFWEFWF");
}
long endTime=System.currentTimeMillis();
System.out.println("1000万次md5Test算法程序运行时间： " + (endTime - startTime ) + "ms");
long startTime2=System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
Test.murmur3Test("KFETHGRETWERFSDFWEFWEFWF");
}
long endTime2=System.currentTimeMillis();
System.out.println("1000万次murmur3Test算法程序运行时间： " + (endTime2 - startTime2 ) + "ms");
}
public static String murmur3Test(String primaryKey) {
return Hashing.murmur3_32().hashString(primaryKey, StandardCharsets.UTF_8).toString() +
"_" + primaryKey;
}
public static String md5Test(String primaryKey) {
return DigestUtils.md5Hex(primaryKey)+ "_" + primaryKey;
}
}输出：
539aa3e7_334324324234234sfsfsdfwwrtregreg
1000万次md5算法程序运行时间： 4420ms
1000万次murmur3Test算法程序运行时间： 1902ms结论:
MurmurHash算法比md5快一倍。
四、使用场景
1、根据uuid，通过hash算法进行取模分库分表
2、用来计算出key的slot值
3、短链接
五、其他算法
ketamahash一致性哈希算法
由若干固定的虚拟节点来计算出每个虚拟节点的slots，数据存储的时候，算出key的slot值，然后存入相邻最近的虚拟节点
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/180273.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022年10月19日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis（TencentDB for Redis）是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备，提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。