一致性 hash 算法

public class ConsistentHash {
    private TreeMap<Integer, String> virtualNodeMap = new TreeMap<>();
    private List<String> nodes;
    private Integer virtualSize = 32;
    public ConsistentHash(List<String> nodes){
        this.nodes = nodes;
        init();
    }
    public ConsistentHash(List<String> nodes, Integer virtualSize){
        this.nodes = nodes;
        this.virtualSize = virtualSize;
        init();
    }
    /**
     * 初始化，计算虚拟节点hashcode
     */
    private void init(){
        for(String node : nodes){
            addNodeWithVirtual(node);
        }
    }
    /**
     * 获取分配节点
     * @param key
     * @return
     */
    public String getNode(String key){
        // 计算hashcode
        int hashCode = HashUtils.getHashCode(key);
        // 取hashcode对应节点
        String node = virtualNodeMap.get(hashCode);
        // 如果节点不存在，就找最近的下一个节点，TreeMap.ceilingEntry 方法用来返回与该键至少大于或等于给定键的实体
        if(node == null){
            Map.Entry<Integer, String> ceilingEntry = virtualNodeMap.ceilingEntry(hashCode);
            if(ceilingEntry == null){// 如果没有符合条件的节点，就返回开始节点
                node = nodes.get(0);
            }else{
                node = ceilingEntry.getValue();
            }
        }
        return node;
    }
    /**
     * 添加新节点
     * @param node
     */
    public void addNodeWithVirtual(String node){
        for(int i=0; i<virtualSize; i++){
            String virtualNode = node+"@"+i;
            virtualNodeMap.put(HashUtils.getHashCode(virtualNode), node);
        }
    }
    /**
     * 添加新节点
     * @param node
     */
    public void addNode(String node){
        if(this.nodes.contains(node)){
            return;
        }
        this.nodes.add(node);
        addNodeWithVirtual(node);
    }
    /**
     * 删除节点
     * @param node
     */
    public void removeNode(String node){
        if(!this.nodes.contains(node)){
            return;
        }
        this.nodes.remove(node);
        for(int i=0; i<virtualSize; i++){
            String virtualNode = node+"@"+i;
            virtualNodeMap.remove(HashUtils.getHashCode(virtualNode));
        }
    }
}

public class HashUtils {
    /**
     * hashcode
     * @param node
     * @return
     */
    public static int getHashCode(String node) {
//        return node.hashCode();
        return Hashing.hmacMd5(node.getBytes()).hashInt(0).asInt();
    }
}

public class MathUtils {
    /**
     * 求和
     * @param values
     * @return
     */
    public static int sum(int[] values){
        int sum = 0;
        for(int value : values){
            sum += value;
        }
        return sum;
    }
    /**
     * 平均数
     * @param values
     * @return
     */
    public static double avg(int[] values){
        return sum(values)/values.length;
    }
    /**
     * 方差
     * @param values
     * @return
     */
    public static double deviation(int[] values){
        double avg = avg(values);
        double total = 0d;
        for(int value : values){
            total += (value - avg)*(value - avg);
        }
        return total;
    }
    /**
     * 标准差
     * standard deviation
     * @param values
     * @return
     */
    public static double std(int[] values){
        return Math.sqrt(deviation(values)/values.length);
    }
}

public class ConsistentHashTest {
    String[] nodes = new String[]{
            "192.168.1.1",
            "192.168.1.2",
            "192.168.1.3",
            "192.168.1.4",
            "192.168.1.5",
            "192.168.1.6",
            "192.168.1.7",
            "192.168.1.8",
            "192.168.1.9",
            "192.168.1.10"};
    ConcurrentHashMap<String, ServerNode<String, String>> nodeMap = new ConcurrentHashMap<>(10);
    @Before
    public void init(){
        for(String node : nodes){
            nodeMap.put(node, new ServerNode<>());
        }
    }
    @Test
    public void testNodeHasVirtual() {
        ConsistentHash chvn = new ConsistentHash(Arrays.asList(nodes));
        // 模拟100万KV
        for(int i=0; i<100_000_0; i++){
            String key = String.valueOf(i);//UUID.randomUUID().toString();
            String value = String.valueOf(i);
            String node = chvn.getNode(key);
            nodeMap.get(node).set(key, value);
        }
        // 统计标准差
        statistics();
    }
    /**
     * 结果统计
     */
    public void statistics(){
        int[] nodeSize = new int[nodes.length];
        for(int i=0; i<nodes.length; i++){
            String node = nodes[i];
            int size  = nodeMap.get(node).getSize();
            nodeSize[i] = size;
            System.out.println("节点["+node+"]缓存数据量："+size);
        }
        System.out.println("标准差："+MathUtils.std(nodeSize));
    }
}

节点[192.168.1.1]缓存数据量：81012
节点[192.168.1.2]缓存数据量：70351
节点[192.168.1.3]缓存数据量：109951
节点[192.168.1.4]缓存数据量：95222
节点[192.168.1.5]缓存数据量：118972
节点[192.168.1.6]缓存数据量：99679
节点[192.168.1.7]缓存数据量：132763
节点[192.168.1.8]缓存数据量：87460
节点[192.168.1.9]缓存数据量：105101
节点[192.168.1.10]缓存数据量：99489
标准差：17258.1747180865