public class ConsistentHash {
    /**
     * 虚拟节点到真实节点的映射
     */
    private Map<Integer, String> virtualNodeToNodeMap = new TreeMap();
    /**
     * 真实节点到虚拟节点的映射
     */
    private Map<String, Set<Integer>> nodeToVirtualNodeMap = new HashMap<>();
    /**
     * 数据存储,key为nodeId，value为数据，数据类型为Map<String, String>
     */
    private Map<String, Map<String, String>> dataMap = new HashMap<>();
    private Random random = new Random();
    /**
     * 查询真实节点nodeId
     *
     * @param key 数据的key值
     * @return 真实节点nodeId
     */
    private String findNode(String key) {
        int dataMod = Math.abs(key.hashCode() % Integer.MAX_VALUE);
        int virtualNode = search(dataMod, virtualNodeToNodeMap.keySet());
        return virtualNodeToNodeMap.get(virtualNode);
    }
    /**
     * 保存数据
     *
     * @param key   数据key值
     * @param value 数据value值
     */
    public void put(String key, String value) {
        String nodeId = findNode(key);
        Map<String, String> stringStringMap = dataMap.computeIfAbsent(nodeId, k -> new HashMap<>());
        stringStringMap.put(key, value);
    }
    /**
     * 查询数据
     *
     * @param key 数据key值
     * @return 数据value值
     */
    public String get(String key) {
        String nodeId = findNode(key);
        return dataMap.get(nodeId) == null ? null : dataMap.get(nodeId).get(key);
    }
    /**
     * 二分查找数据匹配的虚拟节点
     *
     * @param dataMod 数据key值hash取余
     * @param nodeSet 虚拟节点位置集合
     * @return 虚拟节点位置
     */
    private int search(int dataMod, Set<Integer> nodeSet) {
        List<Integer> nodeList = new ArrayList<>(nodeSet);
        int left = 0;
        int right = nodeList.size() - 1;
        //数据dataMod比最后一个节点大或者比第一个节点小，匹配到第一个节点
        if (dataMod > nodeList.get(right) || dataMod < nodeList.get(left)) {
            return nodeList.get(0);
        }
        while (left < right) {
            int mid = (left + right) / 2;
            if (nodeList.get(mid) == dataMod) {
                return nodeList.get(mid);
            } else if (nodeList.get(mid) > dataMod) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nodeList.get(right);
    }
    /**
     * 添加节点
     *
     * @param nodeId         真实节点Id
     * @param virtualNodeNum 虚拟节点个数
     */
    public void addNode(String nodeId, int virtualNodeNum) {
        for (int i = 0; i < virtualNodeNum; i++) {
            int round = random.nextInt(Integer.MAX_VALUE);
            if (!virtualNodeToNodeMap.containsKey(round)) {
                virtualNodeToNodeMap.put(round, nodeId);
                Set<Integer> integers = nodeToVirtualNodeMap.computeIfAbsent(nodeId, k -> new HashSet<>());
                integers.add(round);
                nodeToVirtualNodeMap.put(nodeId, integers);
            }
        }
    }
    /**
     * 删除节点
     *
     * @param nodeId 真实节点Id
     */
    public void removeNode(String nodeId) {
        Set<Integer> removedVirtualNodeSet = nodeToVirtualNodeMap.remove(nodeId);
        if (CollectionUtils.isNotEmpty(removedVirtualNodeSet)) {
            for (Integer virtualNode : removedVirtualNodeSet) {
                virtualNodeToNodeMap.remove(virtualNode);
            }
        }
        dataMap.remove(nodeId);
    }
    /**
     * 打印标准差
     */
    public void print() {
        //计算总数据量
        AtomicInteger sum = new AtomicInteger();
        nodeToVirtualNodeMap.forEach((k, v) -> {
            int i = dataMap.get(k) == null ? 0 : dataMap.get(k).size();
            sum.addAndGet(i);
        });
        //计算方差
        AtomicReference<Double> sumPow = new AtomicReference<>((double) 0);
        nodeToVirtualNodeMap.forEach((k, v) -> {
            double pow = Math.pow((dataMap.get(k).size() - (sum.doubleValue() / nodeToVirtualNodeMap.size())), 2);
            sumPow.updateAndGet(v1 -> v1 + pow);
        });
        //打印标准差
        System.out.println("标准差：" + Math.sqrt(sumPow.get() / sum.doubleValue()));
    }
}

public class ConsistentHashTest {
    long[] testData = new long[1000000];
    @Before
    public void before() {
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            long l = random.nextLong();
            testData[i] = l;
        }
    }
    @Test
    public void test() {
        System.out.print("虚拟节点数：1,");
        test0(1);
        for (int i = 10; i <= 300; i += 10) {
            System.out.print("虚拟节点数：" + i + ",");
            test0(i);
        }
    }
    private void test0(int virtualNodeNum) {
        ConsistentHash consistentHash = new ConsistentHash();
        for (int i = 0; i < 10; i++) {
            consistentHash.addNode("node" + i, virtualNodeNum);
        }
        for (int i = 0; i < 1000000; i++) {
            consistentHash.put("" + testData[i], "" + testData[i]);
        }
        consistentHash.print();
    }
}

虚拟节点数：1,标准差：201.50569043081637
虚拟节点数：10,标准差：99.73175044087013
虚拟节点数：20,标准差：79.58521105079762
虚拟节点数：30,标准差：47.06226511760776
虚拟节点数：40,标准差：65.39111537510276
虚拟节点数：50,标准差：27.08199379661697
虚拟节点数：60,标准差：48.66145834230618
虚拟节点数：70,标准差：47.294346998346434
虚拟节点数：80,标准差：34.054695270990166
虚拟节点数：90,标准差：45.663282624007664
虚拟节点数：100,标准差：36.52003608979597
虚拟节点数：110,标准差：24.84981621662422
虚拟节点数：120,标准差：29.891592262708254
虚拟节点数：130,标准差：27.797646375187956
虚拟节点数：140,标准差：33.411939303189214
虚拟节点数：150,标准差：18.821508919318877
虚拟节点数：160,标准差：27.064991483464393
虚拟节点数：170,标准差：23.53887452704568
虚拟节点数：180,标准差：32.69040620732633
虚拟节点数：190,标准差：15.280666215842816
虚拟节点数：200,标准差：24.98085154673475
虚拟节点数：210,标准差：26.587770609812324
虚拟节点数：220,标准差：14.074486775722944
虚拟节点数：230,标准差：24.10723708764652
虚拟节点数：240,标准差：14.091914135418225
虚拟节点数：250,标准差：16.858168939715842
虚拟节点数：260,标准差：15.62551701544624
虚拟节点数：270,标准差：13.93321527860673
虚拟节点数：280,标准差：15.521547409971726
虚拟节点数：290,标准差：16.375284547146045
虚拟节点数：300,标准差：9.322771798129567