作业 -05-java 实现一致性 hash 算法

package com.example.demo;
import java.util.*;
/**
 * hash一致性算法
 */
public class HashUniformity {
    public static String[] service = { "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"};
    public static Map<Integer, String> nodeMap = new TreeMap<>();
    static {
        int vmNum = 200;//虚拟节点数量
        //虚拟5个节点
        for (int i = 0; i < service.length; i++) {
            for (int j = 0; j < vmNum; j++) {
                String vmService = service[i] + "&vm" + j;
                int hash = getHash(vmService);
                if (hash < 0)
                    hash = Math.abs(hash); //取绝对值
                nodeMap.put(hash, vmService);
            }
        }
    }
    /**
     * 获取服务地址
     *
     * @param url
     * @return
     */
    public static String getService(String url) {
        int hash = getHash(url);
        String service = "";
        for (Integer key : nodeMap.keySet()) {
            if (hash < key) {
                service = nodeMap.get(key).substring(0, nodeMap.get(key).lastIndexOf("&vm"));
                break;
            }
        }
        return service;
    }
    /**
     * 获取hash
     *
     * @param str
     * @return
     */
    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;
    }
    /**
     * 生成随机字符串
     * @param length
     * @return
     */
    public static String getRandomString(int length){
        String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(62);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }
    /**
     * 求标准差
     * @param array
     * @return
     */
    public static double getStandardDeviation(int[] array){
        int sum = 0;
        for(int i=0;i<array.length;i++){
            sum += array[i];      //求出数组的总和
        }
        double average = sum/array.length;  //求出数组的平均数
        int total=0;
        for(int i=0;i<array.length;i++){
            total += (array[i]-average)*(array[i]-average);   //求出方差，如果要计算方差的话这一步就可以了
        }
        double standardDeviation = Math.sqrt(total/array.length);   //求出标准差
        return standardDeviation;
    }
    public static void main(String[] arg) {
        //统计每个服务器存储kv数量
        int[] serviceCount = new int[service.length];
        int count = 0;
        for (int i = 0; i < 1000000; i++) {
            String kv = getRandomString(20)+i;
            String ser = getService(kv);
            for(int j=0;j<service.length;j++){
                if(ser.equals(service[j])){
                    ++serviceCount[j];
                }
            }
        }
        for(int i=0;i<service.length;i++){
            System.out.println(service[i]+"-->"+serviceCount[i]);
        }
        double standardDeviation = getStandardDeviation(serviceCount);
        System.out.println("标准差："+standardDeviation);
    }
}