一致性哈希算法

一致性哈希算法是分布式系统中常用的算法。具体的原理我也不再描述了。

只把完成hash的算法代码记下来,以备使用

一致性哈希算法
public class ConsistentHash<T> {
    private final int virtualNodeNum;
    private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
    
    public ConsistentHash(int virtualNodeNum, Collection<T> nodes) {
        this.virtualNodeNum = virtualNodeNum;
        for (T node : nodes) {
            add(node);
        }
    }
    
    public void add(T node) {
        for (int i = 0; i < virtualNodeNum; i++) {
            circle.put(hash(node.toString() + i), node);
        }
    }
    
    public void remove(T node) {
        for (int i = 0; i < virtualNodeNum; i++) {
            circle.remove(hash(node.toString() + i));
        }
    }
    
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        Long hash = hash(key.toString());
        if (!circle.containsKey(hash)) {
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
    
    /**
     * MurMurHash算法,是非加密HASH算法,性能很高,
     * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
     * 等HASH算法要快很多,而且据说这个算法的碰撞率很低. http://murmurhash.googlepages.com/
     */
    private Long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;

        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);

        long m = 0xc6a4a7935bd1e995L;
        int r = 47;

        long h = seed ^ (buf.remaining() * m);

        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }
        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(
                    ByteOrder.LITTLE_ENDIAN);
            // for big-endian version, do this first:
            // finish.position(8-buf.remaining());
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;
        buf.order(byteOrder);
        return h;
    }
}
一致性哈希算法

参考资料 

https://weblogs.java.net/blog/2007/11/27/consistent-hashing

一致性哈希算法

上一篇:一些资料链接地址..随时更新[2014.1.14]


下一篇:CPP-STL:vector中的size和capacity