week5. 课后作业

package com.demo.hash;
import com.sun.xml.internal.ws.util.StringUtils;
import java.util.*;
public class hashConsistencyAlgorithm {
    //10台待添加入Hash环的服务器列表
    private static String[] servers = {"192.168.0.111","192.168.1.111","192.168.2.111","192.168.3.111","192.168.4.111",
            "192.168.5.111","192.168.6.111","192.168.7.111","192.168.8.111","192.168.9.111"};
    //真实节点列表
    private static List<String> realNodes = new LinkedList<String>();
    //虚拟节点列表
    private static SortedMap<Integer,String> virtualMap = new TreeMap<Integer, String>();
    //虚拟节点数
    private static final int NUM_HOST = 10 ;
    /**
     * @description:使用FNV1_32_HASH算法计算服务器的Hash值
     * @author:cd
     * @param: str
     * @return:int
     * @time:2020/7/8 18:39
     */
    private static int getHash(String str) {
//        int hash = str.hashCode();
        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;
    }
    /**
     * @description:程序初始化把所有的服务器放入virtualMap中
     * @author:cd
     * @param: null
     * @return:
     * @time:2020/7/8 16:41
     */
    static {
        //添加真实节点
        for(int i = 0 ; i < servers.length; i++){
            realNodes.add(servers[i]);
        }
        //添加虚拟节点
        for(String str : realNodes){
            for(int i = 1; i<=NUM_HOST; i++){
                String nodename = str + "VM" + String.valueOf(i);
                //如果算出来的值为负数则取其绝对值
//                int hash = Math.abs(nodename.hashCode());
                int hash = getHash(nodename);
                virtualMap.put(hash,nodename);
//                System.out.println("虚拟节点hash："+ hash +"["+nodename+"]放入");
            }
        }
    }
    
    /**
     * @description:通过传入随机数获取应当路由到的结点的key
     * @author:cd
     * @param: key
     * @return:
     * @time:2020/7/8 16:58
     */
    private static Integer getServer(String key){
        //得到该key的hash值
//        int hash = Math.abs(key.hashCode());
        int hash = getHash(key);
        //返回对应的服务器的key
        Integer host_hash ;
        //返回对应的服务器
        String host;
        //取出大于该hash值的所有Map
        SortedMap<Integer,String> bigMap = virtualMap.tailMap(hash);
        if(bigMap.isEmpty()){
            //如果没有大于hash的值则取virtualMap第一个node
            host_hash = virtualMap.firstKey();
            host = virtualMap.get(host_hash);
        }else {
            //第一个Key就是顺时针过去离node最近的那个结点
            host_hash = bigMap.firstKey();
            //返回对应的服务器
            host= bigMap.get(host_hash);
        }
        if(host != null && host.length() != 0){
            //真实的服务器主机
            String realHost = host.substring(0,host.indexOf("VM"));
//            System.out.println(realHost);
//            return realHost;
        }
        return host_hash;
    }
    /**
     * @description:生成随机数来获取hash一致性算法返回的key
     * @author:cd
     * @param:
     * @return:java.lang.String
     * @time:2020/7/8 17:57
     */
    private static Integer getKey() {
        Random random = new Random();
        int nextInt = random.nextInt(15);
        nextInt = nextInt > 10 ? nextInt : 10;
        char start = 'S';
        String result = "";
        for (int i = 0; i < nextInt; i++) {
            int nextInt1 = random.nextInt(58);
            result += (char)(start + nextInt1);
        }
        return getServer(result);
    }
    /**
     * @description:标准差计算
     * @author:cd
     * @param: x
     * @return:double
     * @time:2020/7/7 21:06
     */
    public static double StandardDiviation(Map<Integer, Integer> data) {
        int machineSize = data.size();
        long dataSize = 0L;
        for (Integer value : data.values()) {
            dataSize += value;
        }
        double averageSize = dataSize / machineSize;
        long total = 0;
        for (Integer value : data.values()) {
            total += (value - averageSize) * (value - averageSize);
        }
        return Math.sqrt(total / (machineSize - 1));
    }
    /**
     * @description:hash一致性标准差结果验证
     * @author:cd
     * @param: args
     * @return:void
     * @time:2020/7/7 21:08
     */
    public static void main(String[] args) {
        //测试100万KV数据，10个服务器节点的情况下，计算这些KV数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性
        Map<Integer, Integer> data = new HashMap<Integer, Integer>();
        for (int i = 0; i < 1000000; i++) {
            int key = getKey();
            data.put(key, key);
        }
        System.out.println(StandardDiviation(data));
    }
}