一致性 hash

package org.seal.learn.learning.concurrent;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * 一致性哈希算法
 *
 * @author xiwang
 * @date 2020-10-25 00:00
 */
public class ConsistentHashMap {
    /**
     * 10个物理节点
     */
    private static String[] NODES = {"127.0.0.1:8001", "127.0.0.1:8002",
            "127.0.0.1:8003", "127.0.0.1:8004", "127.0.0.1:8005", "127.0.0.1:8006",
            "127.0.0.1:8007", "127.0.0.1:8008", "127.0.0.1:8009", "127.0.0.1:8010"};
    /**
     * 使用SortedMap可以排序，再使用tailMap获取key比hashCode[client_ip]大的子map
     */
    private static SortedMap<Integer, String> VIRTUAL_NODES;
    /**
     * 每个物理节点1个虚拟节点
     */
    private static int VIRTUAL_NODE_NUM = 1;
    /**
     * 模拟线上的10台服务器对应的10个虚拟节点
     */
    static {
        VIRTUAL_NODES = new TreeMap<>();
        for (int i = 0, len = NODES.length; i < len; i++) {
            int hashCode;
            String virtualNode;
            for (int j = 0; j < VIRTUAL_NODE_NUM; j++) {
                // 计算节点的哈希值作为key，节点ip("127.0.0.1:8001|node|i")作为value
                virtualNode = NODES[i] + "|node|" + j;
                // 计算虚拟节点的hashCode
                hashCode = getHashCode(virtualNode);
                VIRTUAL_NODES.putIfAbsent(hashCode, virtualNode);
                System.out.println("add virtualNode：" + virtualNode + ", hashCode：" + hashCode);
            }
        }
    }
    /**
     * 使用32位FNV_1计算节点的hashCode
     *
     * @param node
     * @return
     */
    private static int getHashCode(String node) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < node.length(); i++) {
            hash = (hash ^ node.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;
    }
    /**
     * 通过client_ip的哈希值路由一个虚拟节点，再映射到物理节点
     *
     * @param clientIp
     * @return
     */
    public static String routeServer(String clientIp) {
        int hashCode = getHashCode(clientIp);
        SortedMap<Integer, String> subMap = VIRTUAL_NODES.tailMap(hashCode);
        int firstKey = subMap.firstKey();
        String virtualNode = subMap.get(firstKey);
        //寻找物理节点，把|node|x去掉
        String actualNode = virtualNode.substring(0, virtualNode.length() - 7);
        System.out.println("clientIp：" + clientIp + "，hashcode：" + hashCode + "，virtualNode："
                + virtualNode + "，actualNode：" + actualNode);
        return actualNode;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        String[] ips = {"127.0.0.1", "127.0.0.2"};
        for (int i = 0, len = ips.length; i < len; i++) {
            String getNode = routeServer(ips[i]);
            System.out.println("放置节点：" + getNode);
        }
    }
}