ConsistentHash

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:
* http://weblogs.java.net/blog/2007/11/27/consistent-hashing
*/
public class ConsistentHash {

private SortedMap circle;

public ConsistentHash(SortedMap serverMap) {
this.circle = serverMap;
}

public T get(String key) {

int hash = hash32(key);
if (!circle.containsKey(hash)) {
SortedMap 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;
}

}