public class Case4Application {
    SortedMap<Integer, String> sortedCircle = new TreeMap<>();
    int virtualNums = 200;

    /**
     * 初始化虚拟节点
     */
    private void init(List<String> nodes) {

        //服务器节点对应放大虚拟节点
        Map<String, String> virtualNodes = new HashMap<>();
        for (String node : nodes) {
            for (int i = 0; i < virtualNums; i++) {
                virtualNodes.put(node + "_" + i, node);
            }
        }

        for (String key : virtualNodes.keySet()) {
            sortedCircle.put(hash(key), virtualNodes.get(key));
        }

    }

    /**
     * 增加节点
     * @param node
     */
    private void addNode(String node) {
        //服务器节点对应放大虚拟节点
        Map<String, String> virtualNodes = new HashMap<>();
        for (int i = 0; i < virtualNums; i++) {
            virtualNodes.put(node + "_" + i, node);
        }
        for (String key : virtualNodes.keySet()) {
            sortedCircle.put(hash(key), virtualNodes.get(key));
        }
    }

    /**
     * 找到离该key的hash值最新的一个节点
     * 找不到取第一个节点
     *
     * @param key
     * @return
     */
    private String findNodeByHash(String key) {
        int hash = hash(key);
        SortedMap<Integer, String> subMap = sortedCircle.tailMap(hash);
        return subMap.isEmpty()
                ? sortedCircle.get(sortedCircle.firstKey())
                : subMap.get(subMap.firstKey());
    }

    /**
     * hash值计算
     * 32位FNV算法1
     *
     * @param data
     * @return
     */
    private static int hash(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }

    /**
     * 计算缓存key在节点上的分布和标准差
     *
     * @param keyValus
     */
    private void compute(Map<String, Object> keyValus) {
        //每个节点分配的缓存key个数
        Map<String, Integer> result = new HashMap<>();
        for (String key : keyValus.keySet()) {
            String nodeName = findNodeByHash(key);
            if (result.get(nodeName) == null) {
                result.put(nodeName, 1);
            } else {
                Integer value = result.get(nodeName);
                result.put(nodeName, value + 1);
            }
        }


        System.out.println(result);
        System.out.println("标准差：" + stdDev(result, keyValus.size()));
    }


    /**
     * 标准差计算
     *
     * @param map
     * @param totalNums
     * @return
     */
    private double stdDev(Map<String, Integer> map, long totalNums) {
        int n = map.size();
        long avgNums = totalNums / map.size();
        double sum = 0;
        for (String key : map.keySet()) {
            int value = map.get(key);
            sum += (value - avgNums) * (value - avgNums);
        }
        return Math.sqrt(sum / n);

    }

    public static void main(String[] args) {
        //服务器节点
        List<String> nodes = Arrays.asList("node1", "node2", "node3"
                , "node4", "node5", "node6", "node7", "node8", "node9", "node10");

        Case4Application case4Application = new Case4Application();
        //初始化，默认虚拟节点为200
        case4Application.init(nodes);

        //需要环节的1000000个key
        Map<String, Object> keyValus = new HashMap<>();
        for (int i = 1; i <= 1000000; i++) {
            keyValus.put("key" + i, "value" + i);
        }
        //输出缓存key在节点上的分布及标准差
        case4Application.compute(keyValus);

        //添加一个新节点
        case4Application.addNode("node11");
        case4Application.compute(keyValus);
    }
}


// {node4=98661, node10=92694, node5=103651, node2=88519, node3=112497, node8=90940, node9=89461, node6=94505, node7=109283, node1=119789}
// 标准差：10284.048249595098
// {node4=89700, node5=92328, node10=83027, node11=92332, node2=78758, node3=105872, node8=85593, node9=82934, node6=90864, node7=101427, node1=97165}
// 标准差：7867.034967623964