server點分佈在很大的一個circle上，circle的點數量可以是int.MAX個。
每個key同樣hash後，落到int.MAX個點的大circle上，尋找最近的server點。
加server時，或者移去server時，其它server落在circle上的位置不會變，所以最大限度避免瞭數據抖動。 如果是傳統方法的hash算法，任何一個server節點的增加或者刪除，都會導致整個系統的所有cache落點改變。
圖1， A、B、C為三個緩存Server所在的點。 1-4是cache item key的hash值。
圖2，移去C緩存、加入D緩存，1,2兩個點不會受到任何幹擾。
[java]
/**
* Consistent Hash Algorithm, see:
* https://weblogs.java.net/blog/2007/11/27/consistent-hashing
*/
public class ConsistentHash<T> {
private SortedMap<Integer, T> circle;
public ConsistentHash(SortedMap<Integer, T> serverMap) {
this.circle = serverMap;
}
public T get(String key) {
int hash = hash32(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
if (tailMap.isEmpty()) {
hash = circle.firstKey();
} else {
hash = tailMap.firstKey();
}
}
return circle.get(hash);
}
private static final int FNV_32_INIT = 0x711c9dc5;
private static final int FNV_32_PRIME = 0x01000193;
public static int hash32(final String k) {
int rv = FNV_32_INIT;
for(byte b : k.getBytes()) {
rv ^= b;
rv *= FNV_32_PRIME;
}
return rv;
}
}