一致性 hash 算法 -java

import java.math.BigDecimal;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
 * Murmurs 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));
    }
}

import java.util.*;
public class ConsistentHashing {
    //真实服务结点
    private static List<String> realServerNodes = new LinkedList<String>();
    //hash环：使用有序树形数据结构
    private static SortedMap<Long, String> hashCircle = new TreeMap<Long, String>();
    static {
        //先模拟注册10个真实结点列表中
        for (int i = 0; i < 10; i++) {
            realServerNodes.add("192.1.1." + i);
        }
        //把真实节点通过hash算法写入到hash环
        for (String str : realServerNodes) {
            Long hash = Murmurs.hash(str);
            hashCircle.put(hash, str);
        }
        System.out.println();
    }
    //得到应当路由到的结点
    private static String getServer(String key) {
        //得到该key的hash值
        Long hash = Murmurs.hash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Long, String> subMap = hashCircle.tailMap(hash);
        String serverNode;
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Long i = hashCircle.firstKey();
            //返回对应的服务器
            serverNode = hashCircle.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Long i = subMap.firstKey();
            //返回对应的服务器
            serverNode = subMap.get(i);
        }
        return serverNode;
    }
    public static void main(String[] args) {
        HashMap<String, Integer> jsq = new HashMap();
        for (int i = 0; i < 1000000; i++) {
            String key = new Random(1000) + "fsd323e3" + new Random(1000);
            String serverNode = getServer(key);
            System.out.println("命中节点：" + serverNode);
            if (jsq.get(serverNode) != null) {
                jsq.put(serverNode, jsq.get(serverNode) + 1);
            } else {
                jsq.put(serverNode, 1);
            }
        }
        for (Map.Entry<String, Integer> entry : jsq.entrySet()) {
            System.out.println("serverNode: " + entry.getKey() + "; 命中次数: " + entry.getValue());
        }
    }
}