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<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;
    }

}

补充：软件开发 , Java ,