目录介绍

• 01.MurmurHash算法介绍
• 02.算法实现类
• 03.测试案例代码

01.MurmurHash算法介绍

• MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。官方只提供了C语言的实现版本。
• Java界中Redis，Memcached，Cassandra，HBase，Lucene都用它。在Java的实现，Guava的Hashing类里有，上面提到的Jedis，Cassandra里都有Util类。
• 但存在的问题是由于Java的数据类型long与C语言中无符号长整型uint64_t有区别，导致Java输出版本存在负数，针对这个问题进行了修改；另外需要注意的是中文不同编码（UTF-8或GBK）会导致输出结果的不同，使用中需要统一编码。

02.算法实现类

• 代码如下所示：

  /**
   * 一致性Hash的一种算法 高效低碰撞率
   */
  public class Murmurs {
   
      /**
       * murmur hash算法实现
       */
      public static Long hash(byte[] key) {
   
          ByteBuffer buf = ByteBuffer.wrap(key);
          int seed = 0x1234ABCD;
   
          ByteOrder byteOrder = buf.order();
          buf.order(ByteOrder.LITTLE_ENDIAN);
   
          long m = 0xc6a4a7935bd1e995L;
          int r = 47;
   
          long h = seed ^ (buf.remaining() * m);
   
          long k;
          while (buf.remaining() >= 8) {
              k = buf.getLong();
   
              k *= m;
              k ^= k >>> r;
              k *= m;
   
              h ^= k;
              h *= m;
          }
   
          if (buf.remaining() > 0) {
              ByteBuffer finish = ByteBuffer.allocate(8).order(
                      ByteOrder.LITTLE_ENDIAN);
              // for big-endian version, do this first:
              // finish.position(8-buf.remaining());
              finish.put(buf).rewind();
              h ^= finish.getLong();
              h *= m;
          }
   
          h ^= h >>> r;
          h *= m;
          h ^= h >>> r;
   
          buf.order(byteOrder);
          return h;
      }
   
      public static Long hash(String key) {
          return hash(key.getBytes());
      }
   
      /**
       * Long转换成无符号长整型（C中数据类型）
       */
      public static BigDecimal readUnsignedLong(long value) {
          if (value >= 0)
              return new BigDecimal(value);
          long lowValue = value & 0x7fffffffffffffffL;
          return BigDecimal.valueOf(lowValue).add(BigDecimal.valueOf(Long.MAX_VALUE)).add(BigDecimal.valueOf(1));
      }
   
      /**
       * 返回无符号murmur hash值
       */
      public static BigDecimal hashUnsigned(String key) {
          return readUnsignedLong(hash(key));
      }
      
      public static BigDecimal hashUnsigned(byte[] key) {
          return readUnsignedLong(hash(key));
      }
  }

03.测试案例代码

• 测试代码如下所示

  public class Test1 {
  
  	public static void main(String args[]) {
  		String str1 = "https://github.com/wangzheng0822/ratelimiter4j";
  		Long hash1 = Murmurs.hash(str1);
  		System.out.println("yc---1----逗比"+hash1);
  		String str2 = "yangchong";
  		Long hash2 = Murmurs.hash(str2);
  		System.out.println("yc---2----逗比"+hash2);
  		String str3 = "yc";
  		Long hash3 = Murmurs.hash(str3);
  		System.out.println("yc---3----逗比"+hash3);
  	}
  }

• 打印日志

  yc---1----逗比-1671702139016379172
  yc---2----逗比-3494225305897906437
  yc---3----逗比1687004302862169404