import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
/**
 * 一致性hash
 */
public class ConsistentHash {
    //默认虚拟节点为100个
    private int virtualCount = 150;
    //虚拟机节点map
    private SortedMap<Integer, String> virtualNodeMap;
    //物理节点集合
    private List<String> physicalNodes;
    //访问物理节点map
    HashMap<String, Integer> visitPhysicalNodeMap;
    /**
     * 默认
     */
    public ConsistentHash() {
        this(150);
    }
    /**
     * 虚拟节点个数
     *
     * @param virtualCount
     */
    public ConsistentHash(int virtualCount) {
        virtualNodeMap = new TreeMap<>();
        physicalNodes = new ArrayList<>();
        this.virtualCount = virtualCount;
        visitPhysicalNodeMap = new HashMap<>();
    }
    /**
     * 增加物理节点
     *
     * @param nodeName
     */
    public void addPhysicalNode(String nodeName) {
        if (!physicalNodes.contains(nodeName)) {
            physicalNodes.add(nodeName);
            for (int i = 0; i < virtualCount; i++) {
                Integer hasKey = hash(String.format("%s#%d", nodeName, i));
                virtualNodeMap.put(hasKey, nodeName);
            }
            visitPhysicalNodeMap.put(nodeName, 0);
        }
    }
    /**
     * 删除物理节点
     *
     * @param nodeName
     */
    public void removePhysicalNode(String nodeName) {
        if (physicalNodes.contains(nodeName)) {
            physicalNodes.remove(nodeName);
            for (int i = 0; i < virtualCount; i++) {
                Integer hasKey = hash(String.format("%s#%d", nodeName, i));
                virtualNodeMap.remove(hasKey);
            }
            visitPhysicalNodeMap.remove(nodeName);
        }
    }
    /**
     * 根据查找key值，计算hash值，找到虚拟机节点map对应的物理节点
     *
     * @param key
     * @return
     */
    public String findPhysicalNode(String key) {
        if (key != null && !key.trim().equals("")) {
            SortedMap<Integer, String> sortedMap = virtualNodeMap.tailMap(hash(key));
            String node = virtualNodeMap.get(sortedMap.isEmpty() ? virtualNodeMap.firstKey() : sortedMap.firstKey());
            //每次查询到物理节点，统计结果+1
            visitPhysicalNodeMap.put(node, visitPhysicalNodeMap.get(node) + 1);
            return node;
        } else
            return key;
    }
    /**
     * 计算标准差
     * 计算标准差 =  （每个样本 - 平均值）的平方之和 / （服务器节点数） ，所得结果，再取平方
     * sqrt(((x1-x)^2 +(x2-x)^2 +......(xn-x)^2)/n )
     *
     * @param keyCount
     * @return
     */
    public long calculateStdDeviation(int keyCount) {
        long average = keyCount / physicalNodes.size();
        AtomicLong variance = new AtomicLong();
        visitPhysicalNodeMap.forEach((k, v) -> {
            variance.addAndGet((long) Math.pow((v - average), 2));
            System.out.println(String.format("服务器【%s】访问次数 %d", k, v));
        });
        return Math.round(Math.sqrt(variance.get() / physicalNodes.size()));
    }
    /**
     * 清空所有数据集
     */
    public void clear() {
        virtualNodeMap.clear();
        physicalNodes.clear();
        visitPhysicalNodeMap.clear();
    }
    /**
     * 改进的32位FNV算法1
     *
     * @param data
     * @return
     */
    private Integer hash(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }
}

public static void main(String[] args){
        long start =  System.currentTimeMillis();
        ConsistentHash consistentHash = new ConsistentHash(200);
        consistentHash.addPhysicalNode("192.168.10.1:200");
        consistentHash.addPhysicalNode("192.168.10.2:200");
        consistentHash.addPhysicalNode("192.168.10.3:200");
        consistentHash.addPhysicalNode("192.168.10.4:200");
        consistentHash.addPhysicalNode("192.168.10.5:200");
        consistentHash.addPhysicalNode("192.168.10.6:200");
        consistentHash.addPhysicalNode("192.168.10.7:200");
        consistentHash.addPhysicalNode("192.168.10.8:200");
        consistentHash.addPhysicalNode("192.168.10.9:200");
        consistentHash.addPhysicalNode("192.168.10.10:200");
        int count = 100 * 10000;
       
        Random random = new Random();
        for (int j = 0; j < count; j++) {
            String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
            StringBuilder builder = new StringBuilder(20);
            for (int i = 0; i < 20; i++) {
                int index = random.nextInt(62);
                builder.append(str.charAt(index));
            }
            consistentHash.findPhysicalNode(builder.toString());
        }
        long end = System.currentTimeMillis();
        System.out.println(String.format("耗时%d毫秒",end-start));
        System.out.println(String.format("方差：%d",consistentHash.calculateStdDeviation(count)));
    }