簡介
先構(gòu)造一個長度為2^32的整數(shù)環(huán)（這個環(huán)被稱為一致性Hash環(huán)）隆嗅，根據(jù)節(jié)點名稱的Hash值（其分布為[0, 2^32 - 1]）將服務(wù)器節(jié)點放置在這個Hash環(huán)上，然后根據(jù)數(shù)據(jù)的Key值計算得到其Hash值（其分布也為[0, 2^32 - 1]）箩做，接著在Hash環(huán)上順時針查找距離這個Key值的Hash值最近的服務(wù)器節(jié)點婉宰，完成Key到服務(wù)器的映射查找貌笨。
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;
}
實現(xiàn)
為了保證即使增刪節(jié)點也能均勻分布，增加虛擬節(jié)點的概念盆顾，虛擬節(jié)點需要映射到真實節(jié)點上
一種實現(xiàn)方式是：比如真實節(jié)點為192.168.1.1:9527怠褐，配置3個虛擬節(jié)點，那么需要向hash環(huán)添加的節(jié)點為
192.168.1.1:9527#1
192.168.1.1:9527#2
192.168.1.1:9527#3
數(shù)據(jù)結(jié)構(gòu)存儲使用TreeMap您宪，紅黑樹實現(xiàn)奈懒，查詢效率高奠涌，代碼如下：
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("#"));
}
