package interview.hash;
import java.util.*;
public class ConsistentHash {
    //一致性hash简单实现
    //1 确定区间值
    //2 节点散列到区间值（物理节点+虚拟节点，虚拟节点解决数据倾斜不均匀（1 本身节点散列不均匀；2 添加删除节点不均匀））
    //3 元素散列到区间值
    //4 顺时针获取下一个节点位置
    //虚拟节点的个数，经验：物理节点个位数时，每个物理节点160个虚拟节点时，数据会分散很平均
    //上述实现原理中， 元素散列比节点散列频繁的多，即读多写少， 使用链表维护区间值圆环效率不高，二叉树查找非常适合，使用TreeMap-红黑树，按照key排序，查找效率高
    //物理节点数
    private List<String> nodes = null;
    //所有节点(虚拟+物理)
    private SortedMap<Long,String> allVirutualNodes = null;
    private int virtual = 100;
    public ConsistentHash(String []nodeNames){
        this.nodes= new ArrayList<>(Arrays.asList(nodeNames));
        this.refreshHashCircle();
    }
    /**
     * 刷新hash Circle
     */
    public void refreshHashCircle(){
        if(allVirutualNodes ==null){
                allVirutualNodes = new TreeMap<>();
        }else{
            allVirutualNodes.clear();
        }
        for(String node:nodes){
            for(int i=0;i<virtual;i++){
                String nn = "pn"+node+"&&vn"+i;
                long hash = HashUtil.getHash(nn);
                allVirutualNodes.put(hash,node);
            }
        }
    }
    /**
     *  添加节点
     * @param nodeName
     */
    public void addNode(String nodeName){
        nodes.add(nodeName);
        this.refreshHashCircle();
    }
    /**
     * 删除节点
     * @param nodeName
     */
    public void removeNode(String nodeName) {
        Iterator<String> iterator = nodes.iterator();
        while(iterator.hasNext()){
            String sss = iterator.next();
            if(sss.equals(nodeName))
                iterator.remove();
        }
        this.refreshHashCircle();
    }
    /**
     *  获取节点
     * @param key
     * @return
     */
    public String getNode(String key){
        long hash = HashUtil.getHash(key);
        SortedMap<Long,String> subMap = allVirutualNodes.tailMap(hash);
        if(subMap==null||subMap.isEmpty()){
            return allVirutualNodes.get(allVirutualNodes.firstKey());
        }
        String s = subMap.get(subMap.firstKey());
        return s;
    }
}

package interview.hash;
public class HashUtil {
    /**
     *  FNV1_32_HASH算法
     * @param value
     * @return
     */
    public static int getHash(String value){
        final int p = 16777619;
        int result = (int) 2166136261L;
        for (int i = 0; i < value.length(); i++) {
            result = (result ^ value.charAt(i)) * p;
        }
        result += result << 13;
        result ^= result >> 7;
        result += result << 3;
        result ^= result >> 17;
        result += result << 5;
        return Math.abs(result);
    }
}

package interview.hash;
import java.util.*;
public class Test {
    public static void main(String []args){
        Map<String, Integer> hitMap = new HashMap<>();
        List<String> nodes = new ArrayList<>();
        int countNode = 10;
        for (int i = 0; i < countNode; i++) {
            String node = "192.168.1." + i+8080;
            nodes.add(node);
            hitMap.put(node,0);
        }
        ConsistentHash consistentHash = new ConsistentHash(nodes);
        long startTime = System.currentTimeMillis();
        int countKV = 1000000;
        for (int i = 0; i < countKV; i++) {
            String uuid = UUID.randomUUID().toString();
            String node = consistentHash.getNode(uuid);
            int count = hitMap.get(node);
            hitMap.put(node, ++count);
        }
        for (Map.Entry<String, Integer> entry : hitMap.entrySet()) {
            System.out.println(entry.toString());
        }
        System.out.println("--------------------------------------------------------");
        long spentTime = System.currentTimeMillis() - startTime;
        System.out.println(String.format("spent %s ms", spentTime));
        int averageHit = countKV / countNode;
        double temp = hitMap.values().stream().map(value -> Math.pow((value - averageHit), 2)).reduce(0.0, (s, e) -> s = s + e);
        double standardDeviation = Math.sqrt(temp/countNode);
        System.out.println("方差：standardDeviation: " + standardDeviation);
    }
}