簡介

先構(gòu)造一個(gè)長度為2^32的整數(shù)環(huán)（這個(gè)環(huán)被稱為一致性Hash環(huán)），根據(jù)節(jié)點(diǎn)名稱的Hash值（其分布為[0, 2^32 - 1]）將服務(wù)器節(jié)點(diǎn)放置在這個(gè)Hash環(huán)上，然后根據(jù)數(shù)據(jù)的Key值計(jì)算得到其Hash值（其分布也為[0, 2^32 - 1]），接著在Hash環(huán)上順時(shí)針查找距離這個(gè)Key值的Hash值最近的服務(wù)器節(jié)點(diǎn)，完成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;
  }

實(shí)現(xiàn)

為了保證即使增刪節(jié)點(diǎn)也能均勻分布，增加虛擬節(jié)點(diǎn)的概念，虛擬節(jié)點(diǎn)需要映射到真實(shí)節(jié)點(diǎn)上
一種實(shí)現(xiàn)方式是：比如真實(shí)節(jié)點(diǎn)為192.168.1.1:9527，配置3個(gè)虛擬節(jié)點(diǎn)，那么需要向hash環(huán)添加的節(jié)點(diǎn)為

192.168.1.1:9527#1
192.168.1.1:9527#2
192.168.1.1:9527#3

數(shù)據(jù)結(jié)構(gòu)存儲使用TreeMap，紅黑樹實(shí)現(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("#"));
  }