一致性 hash 算法的实现

public class ConsistentHashTest{
/**
     * 服务器列表,一共有10台服务器提供服务, 将根据性能分配虚拟节点
     */
    private static String[] servers = "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,192.168.0.10".split(",");
    private static int virtualNodeNum = 100;//虚拟节点个数
    private static int requestNum=1000000;//100万个请求数据
    /**
     * 真实服务器列表, 由于增加与删除的频率比遍历高, 用链表存储
     */
    private static List<String> realNodes = new LinkedList<>();
    /**
     * 虚拟节点
     */
    private static TreeMap<Integer, String> virtualNodes = new TreeMap<>();
   /*
    1、通过TreeMap构造虚拟节点哈希环 构造虚拟节点如此结构 <FVNHash(192.168.0.1@1),192.168.0.1@1>
    */
    static {
        for (String name : servers) {
            //把服务器加入真实服务器列表中
            realNodes.add(name);
            //根据服务器性能给每台真实服务器分配虚拟节点, 并把虚拟节点放到虚拟节点列表中.
            for (int i = 1; i <= virtualNodeNum; i++) {
                //虚拟节点与实际节点对应关系，不过这个实际节点是hash值-方便请求的hash的对应
                virtualNodes.put(FVNHash(name + "@" + i), name + "@" + i);
            }
        }
    }
    public static void main(String[] args) {
        new Thread(new RequestProcess()).start();
    }
    static class RequestProcess implements Runnable {
        @Override
        public void run() {
            long startTime=System.currentTimeMillis();   //获取开始时间
            String client = null;
            Map<String, Integer> map = new HashMap<String, Integer>();
            for (String key : servers) {
                map.put(key, 0);
            }
            int num = 0;
            while (num < requestNum) {
                num++;
                //2、模拟100万个ip地址的请求
                client = getN() + "." + getN() + "." + getN() + "." + getN() + ":" + (1000 + (int) (Math.random() * 9000));
                //3、getServer(client)请求转发 判断计算出client的hash 与虚拟节点hash比较（顺时针就近的节点）请求将由哪台真实节点处理
                System.out.println(client + " 的请求将由 " + getServer(client) + " 处理");
                //4、聚合每台真实节点处理的总次数
                String key = getServer(client);
                if (map.containsKey(key)) {
                    map.put(key, map.get(key) + 1);
                }
            }
            //5、输出最终结果
            Set<String> keySet = map.keySet();//获取对象
            Iterator<String> ter = keySet.iterator();
            while (ter.hasNext()) {
                String name = ter.next();
                Integer value = map.get(name);
                System.out.println(name + "出现了" + value + "次" + "平均占比" + value*100 /requestNum+"%");
            }
              System.out.println("程序运行时间： "+(System.currentTimeMillis()-startTime)+"ms");
        }
    }
    //请求转发 客户端请求的hash与虚拟节点上的hash比较，找到比该值大的第一个虚拟节点, 如果没有比它大的虚拟节点, 根据哈希环, 则返回第一个节点
    private static String getServer(String client) {
        //3.1 计算客户端请求的哈希值
        int hash = FVNHash(client);
        //得到大于该哈希值的所有map集合
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        //3.2找到比该值大的第一个虚拟节点, 如果没有比它大的虚拟节点, 根据哈希环, 则返回第一个节点.
        Integer targetKey = subMap.size() == 0 ? virtualNodes.firstKey() : subMap.firstKey();
        //通过该虚拟节点获得真实节点的名称
        String virtualNodeName = virtualNodes.get(targetKey);
        String realNodeName = virtualNodeName.split("@")[0];
        return realNodeName;
    }
    public static int getN() {
        return (int) (Math.random() * 128);
    }
    //FNV hash算法
    public static int FVNHash(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash < 0 ? Math.abs(hash) : hash;
    }
}