极客时间 - 架构师一期 - 第五周作业

public class ConsistentHashingWithoutVirtualNode {
    /**
     * 待添加入Hash环的服务器列表
     */
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111",
            "192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111"};
    /**
     * key表示服务器的hash值，value表示服务器的名称
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();

    /**
     * 初始化，所有的服务放入sortedMap中
     */
    static {
        for (int i = 0; i < servers.length; i++) {
            int hash = getHash(servers[i]);
            sortedMap.put(hash, servers[i]);
        }
    }

    public static void main(String[] args) {
        //编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
        int[] serversConnectCount = new int[servers.length];
        for (int i = 0; i < serversConnectCount.length; i++) {
            serversConnectCount[i] = 0;
        }

        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < servers.length; i++) {
            map.put(servers[i], 0);
        }

        int count = 1000000;
        for (int i = 0; i < count; i++) {
            String randomIp = getRandomIp();
            randomIp = randomIp + ":" + new Random().nextInt(10000);
//            System.out.println("[" + randomIp + "]的hash值为" + getHash(randomIp) + ", 被路由到结点[" + getServer(randomIp) + "]");
            map.put(getServer(randomIp), map.get(getServer(randomIp)) + 1);
        }
        double[] bzc = new double[10];
        int i = 0;
        for (String key : map.keySet()) {
            System.out.println(key + ", count:[" + map.get(key) + "]");
            bzc[i] = map.get(key);
            i++;
        }
        System.out.println("标准差：" + standardDiviation(bzc));
    }

    private static String getServer(String node) {
        int hash = getHash(node);
        //返回从fromKey到末尾之间的数据
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.size() == 0) {
            return sortedMap.get(sortedMap.firstKey());
        }
        Integer i = subMap.firstKey();
        return subMap.get(i);
    }

    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
     *
     * @param str
     * @return
     */
    public 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;
    }


    public static String getRandomIp() {

        // ip范围
        int[][] range = {
                {607649792, 608174079}, // 36.56.0.0-36.63.255.255
                {1038614528, 1039007743}, // 61.232.0.0-61.237.255.255
                {1783627776, 1784676351}, // 106.80.0.0-106.95.255.255
                {2035023872, 2035154943}, // 121.76.0.0-121.77.255.255
                {2078801920, 2079064063}, // 123.232.0.0-123.235.255.255
                {-1950089216, -1948778497}, // 139.196.0.0-139.215.255.255
                {-1425539072, -1425014785}, // 171.8.0.0-171.15.255.255
                {-1236271104, -1235419137}, // 182.80.0.0-182.92.255.255
                {-770113536, -768606209}, // 210.25.0.0-210.47.255.255
                {-569376768, -564133889}, // 222.16.0.0-222.95.255.255
        };

        Random random = new Random();
        int index = random.nextInt(10);
        String ip = num2ip(range[index][0] + new Random().nextInt(range[index][1] - range[index][0]));
        return ip;
    }

    /*
     * 将十进制转换成IP地址
     */
    public static String num2ip(int ip) {
        int[] b = new int[4];
        String ipStr = "";
        b[0] = ((ip >> 24) & 0xff);
        b[1] = ((ip >> 16) & 0xff);
        b[2] = ((ip >> 8) & 0xff);
        b[3] = (ip & 0xff);
        ipStr = (b[0]) + "." + (b[1]) + "." + (b[2]) + "." + (b[3]);

        return ipStr;
    }

    //所有数（个数为n）记为一个数组[n]。将数组的所有数求和后除以n得到算数平均值。数组的所有数分别减去平均值，得到的n个差值分别取平方，
    // 再将得到的所有平方数求和，然后除以数的个数或个数减一（若所求为总体标准差则除以n,若所求为样本标准差则除以（n-1）），
    // 最后把得到的商取算术平方根，就是取1/2次方，得到的结果就是这组数（n个数据）的标准差。
    //标准差σ=sqrt(s^2)
    public static double standardDiviation(double[] x) {
        int m = x.length;
        double sum = 0;
        for (int i = 0; i < m; i++) {//求和
            sum += x[i];
        }
        double dAve = sum / m;//求平均值
        double dVar = 0;
        for (int i = 0; i < m; i++) {//求方差
            dVar += (x[i] - dAve) * (x[i] - dAve);
        }
        //reture Math.sqrt(dVar/(m-1));
        return Math.sqrt(dVar / m);
    }

}