一致性哈希算法 Java实现

import java.util.*;

public class ConsistencyHash {
    private static final int VIRTUAL_MACHINE_NUMBER = 5 ;
    private SortedMap<Integer,String> virtualNodeMap = new TreeMap<Integer, String>();
    private  List<String> trueNodeList = new ArrayList<String>();
    public void addNode(String node){
        if(trueNodeList.contains(node)){
            return;
        }
        trueNodeList.add(node);
        for(int i=0;i<VIRTUAL_MACHINE_NUMBER;i++){
            String virtualNodeName = node + i;
            int hash = getHash(virtualNodeName);
            virtualNodeMap.put(hash,virtualNodeName);
        }
    }

    /**
     * 删除某个节点
     * @param node
     */
    public void delNode(String node){
        trueNodeList.remove(node);
        for(int i=0;i<VIRTUAL_MACHINE_NUMBER;i++){
            String virtualNodeName = node + i;
            int hash = getHash(virtualNodeName);
            virtualNodeMap.remove(hash);
        }
    }

    /**
     * FNV哈希算法
     * @param key
     * @return
     */
    public int getHash(String key){
        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;
        return hash>0?hash:Math.abs(hash);
    }

    public String getServer(String key){
        int hash = getHash(key);
        SortedMap<Integer, String> tailMap = virtualNodeMap.tailMap(hash);
        int nodeKey;
        if(tailMap.isEmpty()){
            nodeKey=virtualNodeMap.firstKey();
        }else{
            nodeKey=tailMap.firstKey();
        }
        String virtualNodeName = virtualNodeMap.get(nodeKey);
        return virtualNodeName.substring(0,virtualNodeName.length()-1);
    }

    public static void main(String[] args) {
        ConsistencyHash consistencyHash = new ConsistencyHash();
        String[] nodes = {"192.168.1.1","192.168.1.2","192.168.1.3"};
        for(String node:nodes){
            consistencyHash.addNode(node);
        }
        Map<String,List<Integer>> taskDistributionMap = new HashMap();
        for(int i=0;i<100;i++){
            String server = consistencyHash.getServer("abc"+i + "def" );
            List<Integer> list = taskDistributionMap.get(server);
            if(list==null){
                list = new ArrayList<>();
                taskDistributionMap.put(server,list);
            }
            list.add(i);
        }
        for(Map.Entry<String,List<Integer>> entry:taskDistributionMap.entrySet()){
            System.out.print(entry.getKey()+" "+entry.getValue().size()+" tasks:");
            for(int t:entry.getValue()){
                System.out.print(t+" ");
            }
            System.out.println();
        }
        consistencyHash.addNode("192.168.1.4");
        taskDistributionMap = new HashMap();
        for(int i=0;i<100;i++){
            String server = consistencyHash.getServer("abc"+i + "def" );
            List<Integer> list = taskDistributionMap.get(server);
            if(list==null){
                list = new ArrayList<>();
                taskDistributionMap.put(server,list);
            }
            list.add(i);
        }
        for(Map.Entry<String,List<Integer>> entry:taskDistributionMap.entrySet()){
            System.out.print(entry.getKey()+" "+entry.getValue().size()+" tasks:");
            for(int t:entry.getValue()){
                System.out.print(t+" ");
            }
            System.out.println();
        }

    }
}