一致性哈希算法是分布式系统中常用的算法。具体的原理我也不再描述了。
只把完成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; } }
参考资料