class HashCircle {
    SortedMap<Long,VirtualNode> hashTree;
    List<String> serverList;
    HashCircle() {
        serverList = Arrays.asList("192.168.1.10","192.168.1.11","192.168.1.12","192.168.1.13","192.168.1.14"
        ,"192.168.1.15","192.168.1.16","192.168.1.17","192.168.1.18","192.168.1.19");
        hashTree = new TreeMap<>();
        List<Long> nodeCursorList = new ArrayList<>();
        int index =0;
        for (String serverIp :serverList) {
            long hashValue = googleHash(serverIp);
            nodeCursorList.add(hashValue);
            hashTree.put(hashValue, new VirtualNode("node" + index++));
        }
        nodeCursorList = nodeCursorList.stream().sorted().collect(Collectors.toList());
        int kvCount = 1000000;
        for (int i = 0; i < kvCount; i++) {
            long kvHashValue = googleHash(UUID.randomUUID().toString());
            int hitCursor = 0;
            for (int j = nodeCursorList.size() -1;j > -1;j-- ) {
                if (kvHashValue > nodeCursorList.get(j)) {
                    if (j != nodeCursorList.size() - 1) {
                        hitCursor = j + 1;
                    }
                    break;
                }
            }
            VirtualNode nodeCursor = hashTree.get(nodeCursorList.get(hitCursor));
            nodeCursor.setHitTimes(nodeCursor.getHitTimes() + 1);
        }
        System.out.println(hashTree.size());
    }
    Double getStandardDeviation(){
        double sum = 0d ;
        for (Long key:hashTree.keySet()) {
            VirtualNode nodeCursor = hashTree.get(key);
            sum += Math.pow(nodeCursor.getHitTimes() - 100000,2);
        }
        return Math.sqrt(sum/10);
    }
    private int googleHash(String s){
        HashFunction hashFunction = Hashing.murmur3_128(31);
        return Math.abs(hashFunction.hashString(s, Charsets.UTF_8).hashCode());
    }

public class HashCircleWithVirtualNode {
    SortedMap<Integer,VirtualNode> vnMap;
    List<String> serverList;
    int kvCount ;
    public HashCircleWithVirtualNode(int kvCount) {
        this.kvCount = kvCount;
        buildTreeMap();
    }
    private String getVirtualNode(String key) {
        int hashValue = googleHash(key);
        SortedMap<Integer, VirtualNode> subMap = vnMap.tailMap(hashValue);
        VirtualNode virtualNode;
        if (subMap.isEmpty()) {
            virtualNode = vnMap.get(vnMap.firstKey());
        } else {
            virtualNode = subMap.get(subMap.firstKey());
        }
        return virtualNode.getType().substring(0, virtualNode.getType().indexOf("#"));
    }
    public Map<String,Integer> getKvDistribution() {
        Map<String, Integer> serverIpMap = new HashMap<>();
        for (int i = 0; i < kvCount; i++) {
            String key = RandomStringUtils.randomAlphabetic(6); //UUID.randomUUID().toString();
            String ip = getVirtualNode(key);
            if (serverIpMap.containsKey(ip)) {
                serverIpMap.replace(ip, serverIpMap.get(ip) + 1);
            } else {
                serverIpMap.put(ip, 1);
            }
        }
        return serverIpMap;
    }
    private void buildTreeMap() {
        serverList = new ArrayList<>();
        for(int i = 1;i<11;i++) {
            for (int j = 1; j < 101; j++) {
                serverList.add("192.168.1." + i + "#VN" + j);
            }
        }
        vnMap = new TreeMap<>();
        for (String serverIp :serverList) {
            int hashValue = googleHash(serverIp);
            vnMap.put(hashValue, new VirtualNode(serverIp));
        }
    }
    private int googleHash(String s){
        HashFunction hashFunction = Hashing.murmur3_32();
        return Math.abs(hashFunction.hashString(s, Charsets.UTF_8).hashCode());
    }
}