hash函数MurmurHash

待我称王封你为后i 2023-07-18 02:32 19阅读 0赞

**一、介绍**

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）会导致输出结果的不同，使用中需要统一编码。

**二、原理**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b3Fpbmdsb25nODUwMTAy_size_16_color_FFFFFF_t_70][]

算法图例

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b3Fpbmdsb25nODUwMTAy_size_16_color_FFFFFF_t_70 1][]

**三、性能测试对比**

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值，然后存入相邻最近的虚拟节点

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b3Fpbmdsb25nODUwMTAy_size_16_color_FFFFFF_t_70]: /images/20230528/7fb08722e63c41c0994fa9dc8df29f18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b3Fpbmdsb25nODUwMTAy_size_16_color_FFFFFF_t_70 1]: /images/20230528/8b9f1eff94af413593f8f744dbbe0b72.png