简介
先构造一个长度为2^32的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2^32 - 1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2^32 - 1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
FNV1_32_HASH
分布相对均匀、效率中等
private static int getHash(String str)
{
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length();i ++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash ;
hash ^= hash >> 7;
hash += hash ;
hash ^= hash >> 17;
hash += hash ;
if (hash ) {
hash = Math.abs(hash);
}
return hash;
}
实现
为了保证即使增删节点也能均匀分布，增加虚拟节点的概念，虚拟节点需要映射到真实节点上
一种实现方式是：比如真实节点为192.168.1.1:9527，配置3个虚拟节点，那么需要向hash环添加的节点为
192.168.1.1:9527#1
192.168.1.1:9527#2
192.168.1.1:9527#3
数据结构存储使用TreeMap，红黑树实现，查询效率高，代码如下：
private static String getServer(String node) {
int hash = getHash(node);
# >= hash
int firstKey = sortedMap.tailMap(hash).firstKey();
String vNode = subMap.get(firstKey);
return vNode.subString(0, vNode.indexOf("#"));
}
