一致性 HASH 算法和相关测试

import java.util.*;

/**
 * 带虚拟节点的一致性hash算法
 */
public class ConsistentHashingWithVirtualNode {

    //每个真实的节点模拟10个虚拟节点
    private static final Integer VIRTUAL_NODES = 10;

    //服务器数组，10个
    private static String[] servers = new String[]{"192.168.0.0", "192.168.0.1", "192.168.0.2",
            "192.168.0.3", "192.168.0.4", "192.168.0.5", "192.168.0.6", "192.168.0.7", "192.168.0.8", "192.168.0.9"};

    //真实节点
    private static LinkedList<String> realNodes = new LinkedList<String>();


    //虚拟节点
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

    //用于统计
    private static Map<String, Integer> countMap = new HashMap<String, Integer>(16);


    static {

        for (int i = 0; i < servers.length; i++) {
            realNodes.add(servers[i]);
            //统计初始化
            countMap.put(servers[i], 0);
        }

        for (String node : realNodes) {
            for (int i = 0; i <= VIRTUAL_NODES; i++) {
                String virtualNodeName = node + "&&vm" + i;
                int hashCode = getHash(virtualNodeName);
                virtualNodes.put(hashCode, virtualNodeName);
                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hashCode);
            }
        }

    }


    /**
     * 获取被分配的节点名
     *
     * @param node
     * @return
     */
    public static String getServer(String node) {
        int hash = getHash(node);
        Integer key = null;
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        if (subMap.isEmpty()) {
            key = virtualNodes.lastKey();
        } else {
            key = subMap.firstKey();
        }
        String virtualNode = virtualNodes.get(key);
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }


    /**
     * FNV1_32_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;
    }


    public static void main(String[] args) {

        //模拟节点
        List<String> nodes = new ArrayList<>(200000);

        for(int i = 0 ;i < 256 ;i++){
            for(int j = 0 ;j<256;j++){
                for(int k = 0 ;k < 16 ;k++){
                    nodes.add("1."+i+"."+j+"."+k);
                }
            }
        }

        for (String node : nodes) {
            String realNode = getServer(node);
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + realNode + "]");
            countMap.put(realNode, countMap.get(realNode) + 1);
        }

        countMap.entrySet().stream().forEach((entry) -> {
            System.out.println("节点：" + entry.getKey() + "分配结果个数为：" + entry.getValue());
        });

    }
}