一致性 Hash 实现

public interface HashAlgorithm {    public long hash(String originString);}
public class CRC32HashAlgorithm implements HashAlgorithm {    public long hash(String originString) {        CRC32 crc = new CRC32();        crc.update(originString.getBytes());        return crc.getValue();    }}
public class FNV132HashAlgorithm implements HashAlgorithm {    public long hash(String originString) {        final int p = 16777619;        long hash = 2166136261L;        for (int i = 0; i < originString.length(); i++)            hash = (hash ^ originString.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 class Node {    private String value;
    public Node(String value) {        this.value = value;    }
    public String getValue() {        return value;    }}
public class ConsistencyHash {
    private SortedMap<Long, Node> virtualNodeMap = new TreeMap<Long, Node>();
    private int virtualNodeNum;
    private HashAlgorithm hashAlgorithm;
    public ConsistencyHash(int virtualNodeNum, HashAlgorithm hashAlgorithm) {        this.virtualNodeNum = virtualNodeNum;        this.hashAlgorithm = hashAlgorithm;    }
    /**     * 将服务器节点加入一致性Hash环     * @param node     */    public void addNode(Node node) {        for (int i = 0; i < virtualNodeNum; i++) {            long hashValue = hashAlgorithm.hash(node.getValue() + "-" + i);            virtualNodeMap.put(hashValue, node);        }    }
    /**     * 计算key对应的服务器节点     * @param key     * @return     */    public Node getNode(String key) {        long hashValue = hashAlgorithm.hash(key);        SortedMap<Long, Node> map = virtualNodeMap.tailMap(hashValue);        Long resultKey = 0L;        //如果找不到，则说明在最后一个节点和第一个节点之间，则分配到第一个节点        if (map.size() == 0) {            resultKey = virtualNodeMap.firstKey();        } else {            resultKey = map.firstKey();        }        return virtualNodeMap.get(resultKey);    }}

public class Client {    public static void main(String[] args) {        String[] servers = new String[]{                "192.168.0.1:8080",                "192.168.0.2:8080",                "192.168.0.3:8080",                "192.168.0.4:8080",                "192.168.0.5:8080",                "192.168.0.6:8080",                "192.168.0.7:8080",                "192.168.0.8:8080",                "192.168.0.9:8080",                "192.168.0.10:8080"        };        //--------FNV132HashAlgorithm------------//        ConsistencyHash consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(80, new FNV132HashAlgorithm());        System.out.println("FNV132HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndFNV132HashAlgorithm)));
        ConsistencyHash consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(160, new FNV132HashAlgorithm());        System.out.println("FNV132HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndFNV132HashAlgorithm)));
        ConsistencyHash consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(200, new FNV132HashAlgorithm());        System.out.println("FNV132HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndFNV132HashAlgorithm)));
        ConsistencyHash consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm = new ConsistencyHash(320, new FNV132HashAlgorithm());        System.out.println("FNV132HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndFNV132HashAlgorithm)));
        //--------CRC32HashAlgorithm------------//        ConsistencyHash consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(80, new CRC32HashAlgorithm());        System.out.println("CRC32HashAlgorithm with 80 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith80VirtualNodeAndCRC32HashAlgorithm)));
        ConsistencyHash consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(160, new CRC32HashAlgorithm());        System.out.println("CRC32HashAlgorithm with 160 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith160VirtualNodeAndCRC32HashAlgorithm)));
        ConsistencyHash consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(200, new CRC32HashAlgorithm());        System.out.println("CRC32HashAlgorithm with 200 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith200VirtualNodeAndCRC32HashAlgorithm)));
        ConsistencyHash consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm = new ConsistencyHash(320, new CRC32HashAlgorithm());        System.out.println("CRC32HashAlgorithm with 320 virtual node, standard deviation is " + computeStandardDeviation(computeNodeAllocation(servers, consistencyHashWith320VirtualNodeAndCRC32HashAlgorithm)));
    }
    private static List<Long> computeNodeAllocation(String[] servers, ConsistencyHash consistencyHash) {        for (int i = 0; i < servers.length; i++) {            consistencyHash.addNode(new Node(servers[i]));        }
        Map<String, Long> result = new HashMap<String, Long>();        for (int i = 0; i < 1000000; i++) {            Random random = new Random();            String key = "test" + random.nextInt(10000);            Node node = consistencyHash.getNode(key);            if (result.get(node.getValue()) == null) {                result.put(node.getValue(), 1L);            } else {                result.put(node.getValue(), result.get(node.getValue()) + 1L);            }        }
        List<Long> resultNum = new ArrayList<Long>();        for (Map.Entry<String, Long> entry : result.entrySet()) {            resultNum.add(entry.getValue());        }        return resultNum;    }
    private static Double computeStandardDeviation(List<Long> resultNum) {        long sum = 0;        int length = resultNum.size();        for(int i = 0; i < resultNum.size(); i++){            sum += resultNum.get(i);      //求出数组的总和        }        double average = sum / length;  //求出数组的平均数        long total = 0;        for (int i = 0; i < length; i++) {            total += (resultNum.get(i) - average) * (resultNum.get(i) - average);   //求出方差，如果要计算方差的话这一步就可以了        }        double standardDeviation = Math.sqrt(total / length);   //求出标准差        return standardDeviation;    }}

FNV132HashAlgorithm with 80 virtual node, standard deviation is 45717.53488542443FNV132HashAlgorithm with 160 virtual node, standard deviation is 23627.90045687513FNV132HashAlgorithm with 200 virtual node, standard deviation is 19698.36820652919FNV132HashAlgorithm with 320 virtual node, standard deviation is 21673.15865304363CRC32HashAlgorithm with 80 virtual node, standard deviation is 27903.421080577198CRC32HashAlgorithm with 160 virtual node, standard deviation is 13226.479879393459CRC32HashAlgorithm with 200 virtual node, standard deviation is 13922.735435251221CRC32HashAlgorithm with 320 virtual node, standard deviation is 18066.353644274765