架构师训练营第五周课后作业

import org.apache.commons.lang3.StringUtils;
import java.util.*;
public class HashCircle {
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
    private static String getServer(SortedMap<Integer, String> virtualNodes, String key) {
        int hash = getHash(key);
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if (subMap.isEmpty()) {
            Integer i = virtualNodes.firstKey();
            virtualNode = virtualNodes.get(i);
        } else {
            Integer i = subMap.firstKey();
            virtualNode = subMap.get(i);
        }
        if (StringUtils.isNotBlank(virtualNode)) {
            return virtualNode.substring(0, virtualNode.indexOf("-"));
        }
        return null;
    }
    public static double Variance(List<Integer> x) {
        int m = x.size();
        double sum = 0;
        for (int i = 0; i < m; i++) {//求和
            sum += x.get(i);
        }
        double dAve = sum / m;//求平均值
        double dVar = 0;
        for (int i = 0; i < m; i++) {//求方差
            dVar += (x.get(i) - dAve) * (x.get(i) - dAve);
        }
        return dVar / m;
    }
    public static void main(String[] args) {
        String[] servers = {"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"};
        List<String> realNodes = new LinkedList<>();
        SortedMap<Integer, String> virtualNodes = new TreeMap<>();
        Map<String, Integer> countMap = new HashMap<>();
        int virtualCount = 5;
        for (int i = 0; i < servers.length; i++) {
            realNodes.add(servers[i]);
            countMap.put(servers[i], 0);
        }
        for (String str : realNodes) {
            for (int i = 0; i < virtualCount; i++) {
                String virtualNodeName = str + "-" + i;
                int hash = getHash(virtualNodeName);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        List<String> keys = new ArrayList<>();
        for (int k = 0; k < 1000000; k++) {
            keys.add("key" + k + "-" + k);
        }
        for (int i = 0; i < keys.size(); i++) {
            String server = getServer(virtualNodes, keys.get(i));
            countMap.put(server, countMap.get(server) + 1);
        }
        List<Integer> x = new ArrayList<>();
        for (String key : countMap.keySet()
        ) {
            x.add(countMap.get(key));
        }
        System.out.println(Math.sqrt(Variance(x)));
        System.out.println(countMap);
    }
}