package com.study.architect.homework.week05;
import java.util.*;
/**
 * @ClassName ConsistentHashing
 * @Description 一致性Hash算法
 * @Date 2020/7/8 22:45
 * @Version 1.0
 **/
public class ConsistentHashing {
    // 物理节点
    private Set<String> physicalNodes = new TreeSet<String>() {
        {
            add("192.168.1.101");
            add("192.168.1.102");
            add("192.168.1.103");
            add("192.168.1.104");
            add("192.168.1.105");
            add("192.168.1.106");
            add("192.168.1.107");
            add("192.168.1.108");
            add("192.168.1.109");
            add("192.168.1.110");
        }
    };
    //虚拟节点
    private final int VIRTUAL_COPIES = 200; // 物理节点至虚拟节点的复制倍数
    private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 => 物理节点
    // 32位的 Fowler-Noll-Vo 哈希算法
    // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
    private static Long FNVHash(String key) {
        final int p = 16777619;
        Long hash = 2166136261L;
        for (int idx = 0, num = key.length(); idx < num; ++idx) {
            hash = (hash ^ key.charAt(idx)) * 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 ConsistentHashing() {
        for (String nodeIp : physicalNodes) {
            addPhysicalNode(nodeIp);
        }
    }
    // 添加物理节点
    public void addPhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.put(hash, nodeIp);
        }
    }
    // 删除物理节点
    public void removePhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.remove(hash);
        }
    }
    // 查找对象映射的节点
    public String getObjectNode(String object) {
        long hash = FNVHash(object);
        SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
        Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
        return virtualNodes.get(key);
    }
    // 统计对象与节点的映射关系
    public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
        // 统计
        Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
        for (int object = objectMin; object <= objectMax; ++object) {
            String nodeIp = getObjectNode(Integer.toString(object));
            Integer count = objectNodeMap.get(nodeIp);
            objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
        }
        // 打印
        double totalCount = objectMax - objectMin + 1;
        System.out.println("======== " + label + " ========");
        for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
            long percent = (int) (100 * entry.getValue() / totalCount);
            System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
        }
    }
    public static void main(String[] args) {
        ConsistentHashing ch = new ConsistentHashing();
        // 节点情况
        System.out.println("==================================================");
        ch.dumpObjectNodeMap("节点情况", 0, 65536);
        // 添加数据
        Map<String, Integer> physicalStatisticsMap = new HashMap<>();
        for (String physicalNode : ch.physicalNodes) {
            physicalStatisticsMap.put(physicalNode, 0);
        }
        for (int i = 0; i < 1000000; i++) {
            String physicalNode = ch.getObjectNode("测试数据key" + i);
            int curr = physicalStatisticsMap.get(physicalNode);
            physicalStatisticsMap.put(physicalNode, ++curr);
        }
        // 计算方差
        Integer[] array = (Integer[])physicalStatisticsMap.values().toArray(new Integer[physicalStatisticsMap.values().size()]);
        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);   //求出标准差
        // 输出统计
        System.out.println("==================================================");
        System.out.println("物理节点数据统计：" + physicalStatisticsMap);
        System.out.println("标准差：" + standardDeviation);
    }