分布式系统设计理论之一致性哈希

/**
 * @desc: Java实现一致性哈希
 * @author: YanMingXin
 * @create: 2021/10/16-16:46
 **/
public class ConsistentHash<T> {

    /**
     * 哈希函数类
     */
    private final HashFunction hashFunction;
    /**
     * 虚拟节点个数（不同节点一共的，会自动平均）
     */
    private final int numberOfReplicas;
    /**
     * 哈希环
     */
    private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

    /**
     * 构造方法
     *
     * @param hashFunction     自定义哈希函数类（必须有hash()方法）
     * @param numberOfReplicas 副本个数
     * @param nodes            服务器节点
     */
    public ConsistentHash(HashFunction hashFunction,
                          int numberOfReplicas, Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
        this.hashFunction = new HashFunction();
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 向哈希环增加节点的副本
     *
     * @param node
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hash(node.toString() + i), node);
        }
    }

    /**
     * 删除节点
     *
     * @param node
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hash(node.toString() + i));
        }
    }

    /**
     * 根据请求得到他将要访问的节点
     *
     * @param key
     * @return
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        //将请求hash转换
        int hash = hashFunction.hash(key);
        //将请求放入哈希环
        if (!circle.containsKey(hash)) {
            //返回该映射中键值大于或等于hash的部分的视图。
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            //判断tailMap是否为空，是则返回哈希环第一个节点的值，反之则返回最近的节点
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    /**
     * 哈希函数类
     */
    class HashFunction {
        /**
         * 具体的哈希函数
         *
         * @param key
         * @return
         */
        public int hash(Object key) {
            return key.hashCode() / Integer.MAX_VALUE;
        }
    }
}