基于murmurhash+List实现一致性Hash

一致性Hash原理这里不再介绍了，下面是一个简单版的实现方案。

1、MurmurHashUtils

package com.jane.pos.sync.utils;

import java.io.UnsupportedEncodingException;
import java.math.BigDecimal;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

/**
 * 利用murmurHash实现高性能的低碰撞的纯数字hash值
 */
public class MurmurHashUtils {

    private static final String UTF_8 = "UTF-8";

    public static long hash74A(byte[] data, int seed) {
        return hash74A(ByteBuffer.wrap(data), seed);
    }

    public static long hash74A(ByteBuffer buf, int seed) {
        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(byte[] key) {
        return hash74A(key, 0x1234ABCD);
    }

    public static long hash(String key) {
        return hash(encode(key));
    }

    /**
     * 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));
    }

    private static byte[] encode(String data) {
        try {
            return data.getBytes(UTF_8);
        } catch (UnsupportedEncodingException e) {
            throw new IllegalArgumentException(e);
        }
    }
}

2、HashUtils

package com.jane.pos.sync.utils;

import java.math.BigDecimal;
import java.util.*;

public class HashUtils {

    /**
     * 真实节点虚拟化,为了节点分布均衡
     * @param realNodes 真实节点列表
     * @param inventedNum 每个节点虚拟的节点个数
     * @param hashList 用数组模拟hash环
     * @return
     */
    public static Map<BigDecimal, String> inventedNodes(String[] realNodes, int inventedNum, List<BigDecimal> hashList) {
        //虚拟点和真实节点的对应关系
        Map<BigDecimal, String> map = new HashMap<>();
        if(realNodes.length > 0) {
            for (String node : realNodes) {
                for(int i = 1; i <= inventedNum; i++) {
                    BigDecimal hashCode = MurmurHashUtils.hashUnsigned(node + i);
                    map.put(hashCode, node);
                    //组建hash值数组，模拟hash环
                    hashList.add(hashCode);
                }
            }
        }

        return map;
    }

    /**
     * 根据key获取固定的一致性节点
     * @param realNodes 真实节点
     * @param inventedNum 虚拟的节点数量
     * @param key hash的key,这个key对应一个固定的唯一的真实节点
     * @return
     */
    public static String getFixedOnlyNode(String[] realNodes, int inventedNum, String key) {
        List<BigDecimal> hashList = new ArrayList<>();
        Map<BigDecimal, String> map = inventedNodes(realNodes, inventedNum, hashList);
        //hash数组排序
        Collections.sort(hashList);
        BigDecimal findHash = MurmurHashUtils.hashUnsigned(key);
        for(BigDecimal item : hashList){
            //第一个大的节点，即为要的节点
            if(item.compareTo(findHash) == 1 ) {
                return map.get(item);
            }
        }
        //未命中的key,对节点取余当作下标，获取真实节点
        return map.get(findHash.divideAndRemainder(BigDecimal.valueOf(hashList.size()))[1]);
    }

}

3、启动文件

public static void main(String[] args) throws InterruptedException {

        String storeNo = "store";
        String[] nodes = {"tag01","tag02","tag03","tag04","tag05"};
        for (int i = 0; i <= 10; i++){
            String key = storeNo + i;
            for (int j = 0; j <= 10; j++) {
                String node = HashUtils.getFixedOnlyNode(nodes, 10, key);
                System.out.println(key + "----" + node);
            }
        }
    }

4、结果

store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03