import java.util.SortedMap;import java.util.TreeMap;
public class ConsistentHashing {    private static String[] nodes = {"node001", "node002", "node003", "node004"};
    private static SortedMap virtualNodes;    private static final int VIRTUAL_NODE_NUM = 4;
    static {        virtualNodes = new TreeMap<Integer, String>();        for (int i = 0, len = nodes.length ; i < len; i++) {            int hashCode;            String virtualNode;            for (int j = 0; j < VIRTUAL_NODE_NUM; j++) {                virtualNode = nodes[i] + "_" + j;                hashCode = getHashCode(virtualNode);                virtualNodes.putIfAbsent(hashCode, virtualNode);            }        }    }
    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;    }
    public static String routeServer(String key) {        int hashCode = getHashCode(key);        SortedMap subMap = virtualNodes.tailMap(hashCode);        int firstKey = (Integer)subMap.firstKey();        String virtualNode = (String)subMap.get(firstKey);        String actualNode = virtualNode.substring(0, virtualNode.length() - 3);        System.out.println(key + " mapped to " + actualNode);        return actualNode;    }
    public static void main(String[] args) {        String[] keys = {"123", "bbb", "12bb"};        for (int i = 0, len = keys.length; i < len; i++) {            routeServer(keys[i]);        }    }}