作业一：一致性 hash 实现

package com.rudy.consistent;
import java.util.*;
public class ConsistentHash {
    //物理节点
    private ArrayList<Node> realNodes = new ArrayList<>();
    //有序的虚拟节点，根据物理节点生成
    private HashMap<Node, List<Integer>> realVirtualNodes = new HashMap<>();
    private SortedMap<Integer, Node> sortedMap = new TreeMap<>();
    //添加物理节点
    public void addNode(Node node) {
        realNodes.add(node);
        List<Integer> virtualNodes = new ArrayList<>();
        realVirtualNodes.put(node, virtualNodes);
        //小于等于要求的个虚拟节点
        for (int i = 0; i < node.getVirtualNums(); i++) {
            String ip = node.ip + i;
            int hashVaule = FNV1_32_HASH.getHash(ip);
            if (!this.sortedMap.containsKey(hashVaule)) {
                virtualNodes.add(hashVaule);
                this.sortedMap.put(hashVaule, node);
            }
        }
    }
    //移除物理节点
    public void removeNode(Node node) {
        List<Integer> virtualNodes = this.realVirtualNodes.get(node);
        if (realVirtualNodes != null) {
            for (Integer hash : virtualNodes) {
                this.sortedMap.remove(hash);
            }
        }
        this.realVirtualNodes.remove(node);
        this.realNodes.remove(node);
    }
    //获得物理节点
    public Node getNode(String key) {
        int hash = FNV1_32_HASH.getHash(key);
        //得到大于该hash指的所有虚拟节点map
        SortedMap<Integer, Node> subMap = sortedMap.tailMap(hash);
        if (!subMap.isEmpty()) {
            //取第一个key
            Integer vhash = subMap.firstKey();
            //返回对应的服务器
            return subMap.get(vhash);
        } else {
            return sortedMap.get(sortedMap.firstKey());
        }
    }
    /**
     * 使用的是 FNV1_32_HASH
     */
    public static long hash(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            hash = (hash ^ key.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;
    }
    public static double StandardDeviation(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        long average = sum / nums.length;
        int sum2 = 0;
        for (int i = 0; i < nums.length; i++) {
            sum2 += Math.pow(nums[i] - average, 2);
        }
        return Math.sqrt(sum2 / nums.length);
    }
    public static void main(String[] args) {
        ConsistentHash ch = new ConsistentHash();
        ch.addNode(new Node("192.168.1.10", 100));
        ch.addNode(new Node("192.168.1.11", 100));
        ch.addNode(new Node("192.168.1.12", 100));
        ch.addNode(new Node("192.168.1.13", 100));
        ch.addNode(new Node("192.168.1.14", 100));
        ch.addNode(new Node("192.168.1.15", 100));
        ch.addNode(new Node("192.168.1.16", 100));
        ch.addNode(new Node("192.168.1.17", 100));
        ch.addNode(new Node("192.168.1.18", 100));
        ch.addNode(new Node("192.168.1.19", 100));
        int[] chNums = new int[10];
        for (int i = 0; i < 1000000; i++) {
            String ip = ch.getNode("a" + i).getIp();
            int num = Integer.valueOf(ip.substring(ip.length() - 1));
            chNums[num]++;
        }
        for (int i = 0; i < chNums.length; i++) {
            System.out.println("服务器" + i + ":" + chNums[i]);
        }
        System.out.println(ConsistentHash.StandardDeviation(chNums)/1000000);
    }
}
//服务器节点
class Node {
    //地址
    String ip;
    //对应的虚拟节点个数
    int virtualNums;
    public Node(String ip, int virtualNums) {
        this.ip = ip;
        this.virtualNums = virtualNums;
    }
    public String getIp() {
        return ip;
    }
    public int getVirtualNums() {
        return virtualNums;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return virtualNums == node.virtualNums &&
                Objects.equals(ip, node.ip);
    }
    @Override
    public int hashCode() {
        return Objects.hash(ip, virtualNums);
    }
}