package com.bonree.controller.report;

import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 一致性哈希算法
 *
 * @author yangxl
 * @date 2021-02-03 16:00
 */
public class ConsistentHash {

    public static void main(String[] args) {
        // 连续调用10次,随机10个client
        for (int i = 0; i < 10; i++) {
            System.out.println(getServer("client" + i));
        }
    }

    /**
     * 哈希环：用TreeMap来实现，因为TreeMap是排序的
     */
    private static final SortedMap<Integer, String> HASH_RING = new TreeMap<>();

    /**
     * 虚拟节点个数：为了使哈希的结果能够尽可能均匀分布
     * 当服务器节点比较少的时候，必然造成大量数据集中到一个节点上面，极少数数据集中到另外的节点上面
     */
    private static final int VIRTUAL_NODES = 160;

    /**
     * 服务器节点
     */
    private static final List<String> SERVER_IPS = new ArrayList<>();

    static {
        SERVER_IPS.add("10.240.5.131");
        SERVER_IPS.add("10.240.5.132");
        SERVER_IPS.add("10.240.5.133");
        SERVER_IPS.add("10.240.5.134");
        // 对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
        for (String ip : SERVER_IPS) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(ip + "VN" + i);
                HASH_RING.put(hash, ip);
            }
        }
    }

    /**
     * 根据传入值计算指定IP
     *
     * @param client 要计算hash值的字符串
     * @return 指定IP
     */
    private static String getServer(String client) {
        int hash = getHash(client);
        // 得到大于该Hash值的排好序的Map
        SortedMap<Integer, String> subMap = HASH_RING.tailMap(hash);
        // 大于该hash值的第一个元素的位置
        Integer nodeIndex = subMap.firstKey();
        // 如果不存在大于该hash值的元素，则返回根节点
        if (nodeIndex == null) {
            nodeIndex = HASH_RING.firstKey();
        }
        // 返回对应的虚拟节点名称
        return subMap.get(nodeIndex);
    }

    /**
     * 计算给定字符串的hash值
     *
     * @param str 要计算hash值的字符串
     * @return hash值
     */
    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;
    }

}