「架构师训练营第 1 期」第五周作业

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
 * * 带虚拟节点的一致性哈希算法
 */
public class ConsistentHashingWithVirtualNode {
    /**
     * * 真实节点类
     */
    static class ServerNode {
        String name;
        volatile AtomicInteger requestHit = new AtomicInteger(0); //计算请求次数
        public ServerNode(String name) {
            this.name = name;
        }
        public void request() {
            requestHit.incrementAndGet();
        }
    }
    /**
     * * 虚拟节点类
     */
    static class VirtualNode {
        String name;
        ServerNode serverNode;
        int hash;
        public VirtualNode(int i, ServerNode serverNode) {
            this.serverNode = serverNode;
            this.name = "VirtualNode-" + i + "-" + serverNode.name;
        }
        public void request() {
            serverNode.request();
        }
        public void setHash(int hash) {
            this.hash = hash;
        }
    }
    /**
     * * 真实节点
     */
    private static List<ServerNode> serverNodes = new ArrayList<>();
    /**
     * * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点
     */
    private static SortedMap<Integer, VirtualNode> virtualNodes = new TreeMap<>();
    /**
     * * 真实节点的数目
     */
    private static final int SERVER_NODE_NUM = 10;
    /**
     * * 虚拟节点的数目
     */
    private static final int VIRTUAL_NODES = 150;
    static {
        // 初始化真实服务器节点
        for (int i = 0; i < SERVER_NODE_NUM; i++) {
            serverNodes.add(new ServerNode("ServerNode-" + i));
        }
        // 添加虚拟节点
        for (ServerNode serverNode : serverNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                VirtualNode virtualNode = new VirtualNode(i, serverNode);
                //确保所有的虚拟节点都能被初始化
                int j = 0;
                while (virtualNodes.containsKey(getHash(virtualNode.name + j))) {
                    j++;
                }
                int hash = getHash(virtualNode.name + j);
                virtualNode.setHash(hash);
                virtualNodes.put(hash, virtualNode);
//                System.out.println("虚拟节点[" + virtualNode.name + "]被添加, hash值为" + hash);
            }
        }
    }
    /**
     * 哈希算法，可扩展
     */
    private static int getHash(String str) {
        int hashCode = str.hashCode();
        return Math.floorMod(Math.abs(hashCode), SERVER_NODE_NUM * VIRTUAL_NODES);
    }
    /**
     * 发起请求
     */
    private static void request(String requestkey) {
        // 计算路由Key
        int hash = getHash(requestkey);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, VirtualNode> subMap = virtualNodes.tailMap(hash);
        int i = subMap.firstKey();
        VirtualNode virtualNode = virtualNodes.get(i);
        virtualNode.request();
    }
    /**
     * 计算平均值
     */
    public static double average(List<Double> hits) {
        double sumHit = 0;
        for (Double hit : hits) {
            sumHit += hit;
        }
        return sumHit / hits.size();
    }
    /**
     * 计算方差
     * 方差s^2=[（x1-x）^2+（x2-x）^2+......（xn-x）^2]/（n）（x为平均数）
     */
    public static double variance(List<Double> hits) {
        double avg = average(hits);    //求平均值
        double var = 0;
        for (double i : hits) {
            var += (i - avg) * (i - avg);    //（x1-x）^2+（x2-x）^2+......（xn-x）^2
        }
        return var / hits.size();
    }
    /**
     * 计算标准差
     * 标准差σ=sqrt(s^2)，即标准差=方差的平方根
     */
    public static double standardDiviation(List<Double> hits) {
        return Math.sqrt(variance(hits));
    }
    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();
    }
    public static void main(String[] args) {
        int requestTimes = 1000000;
        for (int i = 0; i < requestTimes; i++) {
            String requestKey = getRandomString(100);
            request(requestKey);
        }
        List<Double> hits = new ArrayList<>();
        for (ServerNode serverNode : serverNodes) {
//            System.out.println(serverNode.requestHit);
            hits.add(Double.valueOf(serverNode.requestHit.get()));
        }
        System.out.println("测试环境：");
        System.out.println("真实节点数：" + SERVER_NODE_NUM + "   虚拟节点数：" + VIRTUAL_NODES + "   请求次数：" + requestTimes);
        System.out.println("测试结果：");
        System.out.println("平均值：" + average(hits) + "   方差：" + variance(hits) + "   标准差：" + standardDiviation(hits));
    }
}

测试环境：
真实节点数：10   虚拟节点数：150   请求次数：1000000
测试结果：
平均值：100000.0   方差：41570.4   标准差：203.88820466128