自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Java實(shí)現(xiàn)一致性Hash算法深入研究

開發(fā) 后端 算法
在寫本文的時(shí)候，很多知識(shí)我也是邊寫邊學(xué)，難免有很多寫得不好、理解得不透徹的地方，而且代碼整體也比較糙，未有考慮到可能的各種情況。拋磚引玉，一方面，寫得不對(duì)的地方，還望網(wǎng)友朋友們指正；另一方面，后續(xù)我也將通過自己的工作、學(xué)習(xí)不斷完善上面的代碼。

一致性Hash算法

關(guān)于一致性Hash算法，在我之前的博文中已經(jīng)有多次提到了，MemCache超詳細(xì)解讀一文中”一致性Hash算法”部分，對(duì)于為什么要使用一致性Hash算法和一致性Hash算法的算法原理做了詳細(xì)的解讀。

算法的具體原理這里再次貼上：

先構(gòu)造一個(gè)長(zhǎng)度為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ù)器的映射查找。

這種算法解決了普通余數(shù)Hash算法伸縮性差的問題，可以保證在上線、下線服務(wù)器的情況下盡量有多的請(qǐng)求命中原來路由到的服務(wù)器。

當(dāng)然，萬事不可能十全十美，一致性Hash算法比普通Hash算法更具有伸縮性，但是同時(shí)其算法實(shí)現(xiàn)也更為復(fù)雜，本文就來研究一下，如何利用Java代碼實(shí)現(xiàn)一致性Hash算法。在開始之前，先對(duì)一致性Hash算法中的幾個(gè)核心問題進(jìn)行一些探究。

數(shù)據(jù)結(jié)構(gòu)的選取

一致性Hash算法最先要考慮的一個(gè)問題是：構(gòu)造出一個(gè)長(zhǎng)度為2 32 的整數(shù)環(huán)，根據(jù)節(jié)點(diǎn)名稱的Hash值將服務(wù)器節(jié)點(diǎn)放置在這個(gè)Hash環(huán)上。

那么，整數(shù)環(huán)應(yīng)該使用何種數(shù)據(jù)結(jié)構(gòu)，才能使得運(yùn)行時(shí)的時(shí)間復(fù)雜度最低？首先說明一點(diǎn)，關(guān)于時(shí)間復(fù)雜度， 常見的時(shí)間復(fù)雜度與時(shí)間效率的關(guān)系有如下的經(jīng)驗(yàn)規(guī)則：

O(1) < O(log 2 N) < O(n) < O(N * log 2 N) < O(N 2 ) < O(N 3 ) < 2N < 3N < N!

一般來說，前四個(gè)效率比較高，中間兩個(gè)差強(qiáng)人意，后三個(gè)比較差（只要N比較大，這個(gè)算法就動(dòng)不了了）。OK，繼續(xù)前面的話題，應(yīng)該如何選取數(shù)據(jù)結(jié)構(gòu)，我認(rèn)為有以下幾種可行的解決方案。

1、解決方案一：排序+List

我想到的第一種思路是：算出所有待加入數(shù)據(jù)結(jié)構(gòu)的節(jié)點(diǎn)名稱的Hash值放入一個(gè)數(shù)組中，然后使用某種排序算法將其從小到大進(jìn)行排序，最后將排序后的數(shù)據(jù)放入List中，采用List而不是數(shù)組是為了結(jié)點(diǎn)的擴(kuò)展考慮。

之后，待路由的結(jié)點(diǎn)，只需要在List中找到第一個(gè)Hash值比它大的服務(wù)器節(jié)點(diǎn)就可以了 ，比如服務(wù)器節(jié)點(diǎn)的Hash值是[0,2,4,6,8,10]，帶路由的結(jié)點(diǎn)是7，只需要找到第一個(gè)比7大的整數(shù)，也就是8，就是我們最終需要路由過去的服務(wù)器節(jié)點(diǎn)。

如果暫時(shí)不考慮前面的排序，那么這種解決方案的時(shí)間復(fù)雜度：

（1）最好的情況是第一次就找到，時(shí)間復(fù)雜度為O(1)

（2）最壞的情況是最后一次才找到，時(shí)間復(fù)雜度為O(N)

平均下來時(shí)間復(fù)雜度為O(0.5N+0.5)，忽略首項(xiàng)系數(shù)和常數(shù)，時(shí)間復(fù)雜度為O(N)。

但是如果考慮到之前的排序，我在網(wǎng)上找了張圖，提供了各種排序算法的時(shí)間復(fù)雜度：

 

看得出來，排序算法要么穩(wěn)定但是時(shí)間復(fù)雜度高、要么時(shí)間復(fù)雜度低但不穩(wěn)定，看起來最好的歸并排序法的時(shí)間復(fù)雜度仍然有O(N * logN)，稍微耗費(fèi)性能了一些。

2、解決方案二：遍歷+List

既然排序操作比較耗性能，那么能不能不排序？可以的，所以進(jìn)一步的，有了第二種解決方案。

解決方案使用List不變，不過可以采用遍歷的方式：

（1）服務(wù)器節(jié)點(diǎn)不排序，其Hash值全部直接放入一個(gè)List中

（2）帶路由的節(jié)點(diǎn)，算出其Hash值，由于指明了”順時(shí)針”，因此遍歷List，比待路由的節(jié)點(diǎn)Hash值大的算出差值并記錄，比待路由節(jié)點(diǎn)Hash值小的忽略

（3）算出所有的差值之后，最小的那個(gè)，就是最終需要路由過去的節(jié)點(diǎn)

在這個(gè)算法中，看一下時(shí)間復(fù)雜度：

1、最好情況是只有一個(gè)服務(wù)器節(jié)點(diǎn)的Hash值大于帶路由結(jié)點(diǎn)的Hash值，其時(shí)間復(fù)雜度是O(N)+O(1)=O(N+1)，忽略常數(shù)項(xiàng)，即O(N)

2、最壞情況是所有服務(wù)器節(jié)點(diǎn)的Hash值都大于帶路由結(jié)點(diǎn)的Hash值，其時(shí)間復(fù)雜度是O(N)+O(N)=O(2N)，忽略首項(xiàng)系數(shù)，即O(N)

所以，總的時(shí)間復(fù)雜度就是O(N)。其實(shí)算法還能更改進(jìn)一些：給一個(gè)位置變量X，如果新的差值比原差值小，X替換為新的位置，否則X不變。這樣遍歷就減少了一輪，不過經(jīng)過改進(jìn)后的算法時(shí)間復(fù)雜度仍為O(N)。

總而言之，這個(gè)解決方案和解決方案一相比，總體來看，似乎更好了一些。

3、解決方案三：二叉查找樹

拋開List這種數(shù)據(jù)結(jié)構(gòu)，另一種數(shù)據(jù)結(jié)構(gòu)則是使用 二叉查找樹 。對(duì)于樹不是很清楚的朋友可以簡(jiǎn)單看一下這篇文章樹形結(jié)構(gòu)。

當(dāng)然我們不能簡(jiǎn)單地使用二叉查找樹，因?yàn)榭赡艹霈F(xiàn)不平衡的情況。平衡二叉查找樹有AVL樹、紅黑樹等，這里使用紅黑樹，選用紅黑樹的原因有兩點(diǎn)：

1、紅黑樹主要的作用是用于存儲(chǔ)有序的數(shù)據(jù)，這其實(shí)和第一種解決方案的思路又不謀而合了，但是它的效率非常高

2、JDK里面提供了紅黑樹的代碼實(shí)現(xiàn)TreeMap和TreeSet

另外，以TreeMap為例，TreeMap本身提供了一個(gè)tailMap(K fromKey)方法，支持從紅黑樹中查找比fromKey大的值的集合，但并不需要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)。

使用紅黑樹，可以使得查找的時(shí)間復(fù)雜度降低為O(logN)，比上面兩種解決方案，效率大大提升。

為了驗(yàn)證這個(gè)說法，我做了一次測(cè)試，從大量數(shù)據(jù)中查找第一個(gè)大于其中間值的那個(gè)數(shù)據(jù)，比如10000數(shù)據(jù)就找第一個(gè)大于5000的數(shù)據(jù)（模擬平均的情況）?？匆幌翺(N)時(shí)間復(fù)雜度和O(logN)時(shí)間復(fù)雜度運(yùn)行效率的對(duì)比：

 

50000

100000

500000

1000000

4000000

ArrayList

1ms

1ms

4ms

4ms

5ms

LinkedList

4ms

7ms

11ms

13ms

17ms

TreeMap

0ms

0ms

0ms

0ms

0ms

因?yàn)樵俅缶蛢?nèi)存溢出了，所以只測(cè)試到4000000數(shù)據(jù)?？梢钥吹剑瑪?shù)據(jù)查找的效率，TreeMap是完勝的，其實(shí)再增大數(shù)據(jù)測(cè)試也是一樣的，紅黑樹的數(shù)據(jù)結(jié)構(gòu)決定了任何一個(gè)大于N的最小數(shù)據(jù)，它都只需要幾次至幾十次查找就可以查到。

當(dāng)然，明確一點(diǎn)，有利必有弊，根據(jù)我另外一次測(cè)試得到的結(jié)論是， 為了維護(hù)紅黑樹，數(shù)據(jù)插入效率TreeMap在三種數(shù)據(jù)結(jié)構(gòu)里面是最差的，且插入要慢上5~10倍 。

Hash值重新計(jì)算

服務(wù)器節(jié)點(diǎn)我們肯定用字符串來表示，比如”192.168.1.1″、”192.168.1.2″，根據(jù)字符串得到其Hash值，那么另外一個(gè)重要 的問題就是 Hash值要重新計(jì)算，這個(gè)問題是我在測(cè)試String的hashCode()方法的時(shí)候發(fā)現(xiàn)的，不妨來看一下為什么要重新計(jì)算Hash值：

  1. /** 
  2. * String的hashCode()方法運(yùn)算結(jié)果查看 
  3. * @author 五月的倉頡 http://www.cnblogs.com/xrq730/ 
  4. * 
  5. */ 
  6. public class StringHashCodeTest 
  7. { 
  8.     public static void main(String[] args) 
  9.     { 
  10.         System.out.println("192.168.0.0:111的哈希值：" + "192.168.0.0:1111".hashCode()); 
  11.         System.out.println("192.168.0.1:111的哈希值：" + "192.168.0.1:1111".hashCode()); 
  12.         System.out.println("192.168.0.2:111的哈希值：" + "192.168.0.2:1111".hashCode()); 
  13.         System.out.println("192.168.0.3:111的哈希值：" + "192.168.0.3:1111".hashCode()); 
  14.         System.out.println("192.168.0.4:111的哈希值：" + "192.168.0.4:1111".hashCode()); 
  15.     } 
  16. } 

我們?cè)谧黾旱臅r(shí)候，集群點(diǎn)的IP以這種連續(xù)的形式存在是很正常的?？匆幌逻\(yùn)行結(jié)果為：

  1. 192.168.0.0:111的哈希值：1845870087 
  2. 192.168.0.1:111的哈希值：1874499238 
  3. 192.168.0.2:111的哈希值：1903128389 
  4. 192.168.0.3:111的哈希值：1931757540 
  5. 192.168.0.4:111的哈希值：1960386691 

這個(gè)就問題大了，[0,2 32 -1]的區(qū)間之中，5個(gè)HashCode值卻只分布在這么小小的一個(gè)區(qū)間，什么概念？[0,2 32 -1]中有4294967296個(gè)數(shù)字，而我們的區(qū)間只有122516605，從概率學(xué)上講這將導(dǎo)致97%待路由的服務(wù)器都被路由到”192.168.0.1″這個(gè)集群點(diǎn)上，簡(jiǎn)直是糟糕透了！

另外還有一個(gè)不好的地方：規(guī)定的區(qū)間是非負(fù)數(shù)，String的hashCode()方法卻會(huì)產(chǎn)生負(fù)數(shù)（不信用”192.168.1.0:1111″試試看就知道了）。不過這個(gè)問題好解決，取絕對(duì)值就是一種解決的辦法。

綜上，String重寫的hashCode()方法在一致性Hash算法中沒有任何實(shí)用價(jià)值，得找個(gè)算法重新計(jì)算HashCode。這種重新計(jì)算 Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默認(rèn)的 MemCache推薦的一致性Hash算法，用別的Hash算法也可以，比如FNV1_32_HASH算法的計(jì)算效率就會(huì)高一些。

一致性Hash算法實(shí)現(xiàn)版本1：不帶虛擬節(jié)點(diǎn)

使用一致性Hash算法，盡管增強(qiáng)了系統(tǒng)的伸縮性，但是也有可能導(dǎo)致負(fù)載分布不均勻，解決辦法就是使用 虛擬節(jié)點(diǎn)代替真實(shí)節(jié)點(diǎn) ，第一個(gè)代碼版本，先來個(gè)簡(jiǎn)單的，不帶虛擬節(jié)點(diǎn)。

下面來看一下不帶虛擬節(jié)點(diǎn)的一致性Hash算法的Java代碼實(shí)現(xiàn)：

  1. /** 
  2. * 不帶虛擬節(jié)點(diǎn)的一致性Hash算法 
  3. * @author 五月的倉頡http://www.cnblogs.com/xrq730/ 
  4. * 
  5. */ 
  6. public class ConsistentHashingWithoutVirtualNode 
  7. { 
  8.     /** 
  9.      * 待添加入Hash環(huán)的服務(wù)器列表 
  10.      */ 
  11.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", 
  12.             "192.168.0.3:111", "192.168.0.4:111"}; 
  13.     
  14.     /** 
  15.      * key表示服務(wù)器的hash值，value表示服務(wù)器的名稱 
  16.      */ 
  17.     private static SortedMap<Integer, String> sortedMap = 
  18.             new TreeMap<Integer, String>(); 
  19.     
  20.     /** 
  21.      * 程序初始化，將所有的服務(wù)器放入sortedMap中 
  22.      */ 
  23.     static 
  24.     { 
  25.         for (int i = 0; i < servers.length; i++) 
  26.         { 
  27.             int hash = getHash(servers[i]); 
  28.             System.out.println("[" + servers[i] + "]加入集合中, 其Hash值為" + hash); 
  29.             sortedMap.put(hash, servers[i]); 
  30.         } 
  31.         System.out.println(); 
  32.     } 
  33.     
  34.     /** 
  35.      * 使用FNV1_32_HASH算法計(jì)算服務(wù)器的Hash值,這里不使用重寫hashCode的方法，最終效果沒區(qū)別 
  36.      */ 
  37.     private static int getHash(String str) 
  38.     { 
  39.         final int p = 16777619; 
  40.         int hash = (int)2166136261L; 
  41.         for (int i = 0; i < str.length(); i++) 
  42.             hash = (hash ^ str.charAt(i)) * p; 
  43.         hash += hash << 13; 
  44.         hash ^= hash >> 7; 
  45.         hash += hash << 3; 
  46.         hash ^= hash >> 17; 
  47.         hash += hash << 5; 
  48.         
  49.         // 如果算出來的值為負(fù)數(shù)則取其絕對(duì)值 
  50.         if (hash < 0) 
  51.             hash = Math.abs(hash); 
  52.         return hash; 
  53.     } 
  54.     
  55.     /** 
  56.      * 得到應(yīng)當(dāng)路由到的結(jié)點(diǎn) 
  57.      */ 
  58.     private static String getServer(String node) 
  59.     { 
  60.         // 得到帶路由的結(jié)點(diǎn)的Hash值 
  61.         int hash = getHash(node); 
  62.         // 得到大于該Hash值的所有Map 
  63.         SortedMap<Integer, String> subMap = 
  64.                 sortedMap.tailMap(hash); 
  65.         // 第一個(gè)Key就是順時(shí)針過去離node最近的那個(gè)結(jié)點(diǎn) 
  66.         Integer i = subMap.firstKey(); 
  67.         // 返回對(duì)應(yīng)的服務(wù)器名稱 
  68.         return subMap.get(i); 
  69.     } 
  70.     
  71.     public static void main(String[] args) 
  72.     { 
  73.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; 
  74.         for (int i = 0; i < nodes.length; i++) 
  75.             System.out.println("[" + nodes[i] + "]的hash值為" + 
  76.                     getHash(nodes[i]) + ", 被路由到結(jié)點(diǎn)[" + getServer(nodes[i]) + "]"); 
  77.     } 
  78. } 

可以運(yùn)行一下看一下結(jié)果：

  1. [192.168.0.0:111]加入集合中, 其Hash值為575774686 
  2. [192.168.0.1:111]加入集合中, 其Hash值為8518713 
  3. [192.168.0.2:111]加入集合中, 其Hash值為1361847097 
  4. [192.168.0.3:111]加入集合中, 其Hash值為1171828661 
  5. [192.168.0.4:111]加入集合中, 其Hash值為1764547046 
  6.  
  7. [127.0.0.1:1111]的hash值為380278925, 被路由到結(jié)點(diǎn)[192.168.0.0:111] 
  8. [221.226.0.1:2222]的hash值為1493545632, 被路由到結(jié)點(diǎn)[192.168.0.4:111] 
  9. [10.211.0.1:3333]的hash值為1393836017, 被路由到結(jié)點(diǎn)[192.168.0.4:111] 

看到經(jīng)過FNV1_32_HASH算法重新計(jì)算過后的Hash值，就比原來String的hashCode()方法好多了。從運(yùn)行結(jié)果來看，也沒有問題，三個(gè)點(diǎn)路由到的都是順時(shí)針離他們Hash值最近的那臺(tái)服務(wù)器上。

使用虛擬節(jié)點(diǎn)來改善一致性Hash算法

上面的一致性Hash算法實(shí)現(xiàn)，可以在很大程度上解決很多分布式環(huán)境下不好的路由算法導(dǎo)致系統(tǒng)伸縮性差的問題，但是會(huì)帶來另外一個(gè)問題：負(fù)載不均。

比如說有Hash環(huán)上有A、B、C三個(gè)服務(wù)器節(jié)點(diǎn)，分別有100個(gè)請(qǐng)求會(huì)被路由到相應(yīng)服務(wù)器上?，F(xiàn)在在A與B之間增加了一個(gè)節(jié)點(diǎn)D，這導(dǎo)致了原來會(huì) 路由到B上的部分節(jié)點(diǎn)被路由到了D上，這樣A、C上被路由到的請(qǐng)求明顯多于B、D上的，原來三個(gè)服務(wù)器節(jié)點(diǎn)上均衡的負(fù)載被打破了。 某種程度上來說，這失去了負(fù)載均衡的意義，因?yàn)樨?fù)載均衡的目的本身就是為了使得目標(biāo)服務(wù)器均分所有的請(qǐng)求 。

解決這個(gè)問題的辦法是引入虛擬節(jié)點(diǎn)，其工作原理是： 將一個(gè)物理節(jié)點(diǎn)拆分為多個(gè)虛擬節(jié)點(diǎn)，并且同一個(gè)物理節(jié)點(diǎn)的虛擬節(jié)點(diǎn)盡量均勻分布在Hash環(huán)上 。采取這樣的方式，就可以有效地解決增加或減少節(jié)點(diǎn)時(shí)候的負(fù)載不均衡的問題。

至于一個(gè)物理節(jié)點(diǎn)應(yīng)該拆分為多少虛擬節(jié)點(diǎn)，下面可以先看一張圖：

橫軸表示需要為每臺(tái)福利服務(wù)器擴(kuò)展的虛擬節(jié)點(diǎn)倍數(shù)，縱軸表示的是實(shí)際物理服務(wù)器數(shù)。可以看出，物理服務(wù)器很少，需要更大的虛擬節(jié)點(diǎn)；反之物理服務(wù)器 比較多，虛擬節(jié)點(diǎn)就可以少一些。比如有10臺(tái)物理服務(wù)器，那么差不多需要為每臺(tái)服務(wù)器增加100~200個(gè)虛擬節(jié)點(diǎn)才可以達(dá)到真正的負(fù)載均衡。

一致性Hash算法實(shí)現(xiàn)版本2：帶虛擬節(jié)點(diǎn)

在理解了使用虛擬節(jié)點(diǎn)來改善一致性Hash算法的理論基礎(chǔ)之后，就可以嘗試開發(fā)代碼了。編程方面需要考慮的問題是：

1、一個(gè)真實(shí)結(jié)點(diǎn)如何對(duì)應(yīng)成為多個(gè)虛擬節(jié)點(diǎn)？

2、虛擬節(jié)點(diǎn)找到后如何還原為真實(shí)結(jié)點(diǎn)？

這兩個(gè)問題其實(shí)有很多解決辦法，我這里使用了一種簡(jiǎn)單的辦法，給每個(gè)真實(shí)結(jié)點(diǎn)后面根據(jù)虛擬節(jié)點(diǎn)加上后綴再取Hash值，比 如”192.168.0.0:111″就把它變成”192.168.0.0:111&&VN0″ 到”192.168.0.0:111&&VN4″，VN就是virtual Node的縮寫，還原的時(shí)候只需要從頭截取字符串到”&&”的位置就可以了。

下面來看一下帶虛擬節(jié)點(diǎn)的一致性Hash算法的Java代碼實(shí)現(xiàn)：

  1. /** 
  2. * 帶虛擬節(jié)點(diǎn)的一致性Hash算法 
  3. * @author 五月的倉頡 http://www.cnblogs.com/xrq730/ 
  4. */ 
  5. public class ConsistentHashingWithVirtualNode 
  6. { 
  7.     /** 
  8.      * 待添加入Hash環(huán)的服務(wù)器列表 
  9.      */ 
  10.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", 
  11.             "192.168.0.3:111", "192.168.0.4:111"}; 
  12.     
  13.     /** 
  14.      * 真實(shí)結(jié)點(diǎn)列表,考慮到服務(wù)器上線、下線的場(chǎng)景，即添加、刪除的場(chǎng)景會(huì)比較頻繁，這里使用LinkedList會(huì)更好 
  15.      */ 
  16.     private static List<String> realNodes = new LinkedList<String>(); 
  17.     
  18.     /** 
  19.      * 虛擬節(jié)點(diǎn)，key表示虛擬節(jié)點(diǎn)的hash值，value表示虛擬節(jié)點(diǎn)的名稱 
  20.      */ 
  21.     private static SortedMap<Integer, String> virtualNodes = 
  22.             new TreeMap<Integer, String>(); 
  23.     
  24.     /** 
  25.      * 虛擬節(jié)點(diǎn)的數(shù)目，這里寫死，為了演示需要，一個(gè)真實(shí)結(jié)點(diǎn)對(duì)應(yīng)5個(gè)虛擬節(jié)點(diǎn) 
  26.      */ 
  27.     private static final int VIRTUAL_NODES = 5; 
  28.     
  29.     static 
  30.     { 
  31.         // 先把原始的服務(wù)器添加到真實(shí)結(jié)點(diǎn)列表中 
  32.         for (int i = 0; i < servers.length; i++) 
  33.             realNodes.add(servers[i]); 
  34.         
  35.         // 再添加虛擬節(jié)點(diǎn)，遍歷LinkedList使用foreach循環(huán)效率會(huì)比較高 
  36.         for (String str : realNodes) 
  37.         { 
  38.             for (int i = 0; i < VIRTUAL_NODES; i++) 
  39.             { 
  40.                 String virtualNodeName = str + "&&VN" + String.valueOf(i); 
  41.                 int hash = getHash(virtualNodeName); 
  42.                 System.out.println("虛擬節(jié)點(diǎn)[" + virtualNodeName + "]被添加, hash值為" + hash); 
  43.                 virtualNodes.put(hash, virtualNodeName); 
  44.             } 
  45.         } 
  46.         System.out.println(); 
  47.     } 
  48.     
  49.     /** 
  50.      * 使用FNV1_32_HASH算法計(jì)算服務(wù)器的Hash值,這里不使用重寫hashCode的方法，最終效果沒區(qū)別 
  51.      */ 
  52.     private static int getHash(String str) 
  53.     { 
  54.         final int p = 16777619; 
  55.         int hash = (int)2166136261L; 
  56.         for (int i = 0; i < str.length(); i++) 
  57.             hash = (hash ^ str.charAt(i)) * p; 
  58.         hash += hash << 13; 
  59.         hash ^= hash >> 7; 
  60.         hash += hash << 3; 
  61.         hash ^= hash >> 17; 
  62.         hash += hash << 5; 
  63.         
  64.         // 如果算出來的值為負(fù)數(shù)則取其絕對(duì)值 
  65.         if (hash < 0) 
  66.             hash = Math.abs(hash); 
  67.         return hash; 
  68.     } 
  69.     
  70.     /** 
  71.      * 得到應(yīng)當(dāng)路由到的結(jié)點(diǎn) 
  72.      */ 
  73.     private static String getServer(String node) 
  74.     { 
  75.         // 得到帶路由的結(jié)點(diǎn)的Hash值 
  76.         int hash = getHash(node); 
  77.         // 得到大于該Hash值的所有Map 
  78.         SortedMap<Integer, String> subMap = 
  79.                 virtualNodes.tailMap(hash); 
  80.         // 第一個(gè)Key就是順時(shí)針過去離node最近的那個(gè)結(jié)點(diǎn) 
  81.         Integer i = subMap.firstKey(); 
  82.         // 返回對(duì)應(yīng)的虛擬節(jié)點(diǎn)名稱，這里字符串稍微截取一下 
  83.         String virtualNode = subMap.get(i); 
  84.         return virtualNode.substring(0, virtualNode.indexOf("&&")); 
  85.     } 
  86.     
  87.     public static void main(String[] args) 
  88.     { 
  89.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; 
  90.         for (int i = 0; i < nodes.length; i++) 
  91.             System.out.println("[" + nodes[i] + "]的hash值為" + 
  92.                     getHash(nodes[i]) + ", 被路由到結(jié)點(diǎn)[" + getServer(nodes[i]) + "]"); 
  93.     } 
  94. } 

關(guān)注一下運(yùn)行結(jié)果：

  1. 虛擬節(jié)點(diǎn)[192.168.0.0:111&&VN0]被添加, hash值為1686427075 
  2. 虛擬節(jié)點(diǎn)[192.168.0.0:111&&VN1]被添加, hash值為354859081 
  3. 虛擬節(jié)點(diǎn)[192.168.0.0:111&&VN2]被添加, hash值為1306497370 
  4. 虛擬節(jié)點(diǎn)[192.168.0.0:111&&VN3]被添加, hash值為817889914 
  5. 虛擬節(jié)點(diǎn)[192.168.0.0:111&&VN4]被添加, hash值為396663629 
  6. 虛擬節(jié)點(diǎn)[192.168.0.1:111&&VN0]被添加, hash值為1032739288 
  7. 虛擬節(jié)點(diǎn)[192.168.0.1:111&&VN1]被添加, hash值為707592309 
  8. 虛擬節(jié)點(diǎn)[192.168.0.1:111&&VN2]被添加, hash值為302114528 
  9. 虛擬節(jié)點(diǎn)[192.168.0.1:111&&VN3]被添加, hash值為36526861 
  10. 虛擬節(jié)點(diǎn)[192.168.0.1:111&&VN4]被添加, hash值為848442551 
  11. 虛擬節(jié)點(diǎn)[192.168.0.2:111&&VN0]被添加, hash值為1452694222 
  12. 虛擬節(jié)點(diǎn)[192.168.0.2:111&&VN1]被添加, hash值為2023612840 
  13. 虛擬節(jié)點(diǎn)[192.168.0.2:111&&VN2]被添加, hash值為697907480 
  14. 虛擬節(jié)點(diǎn)[192.168.0.2:111&&VN3]被添加, hash值為790847074 
  15. 虛擬節(jié)點(diǎn)[192.168.0.2:111&&VN4]被添加, hash值為2010506136 
  16. 虛擬節(jié)點(diǎn)[192.168.0.3:111&&VN0]被添加, hash值為891084251 
  17. 虛擬節(jié)點(diǎn)[192.168.0.3:111&&VN1]被添加, hash值為1725031739 
  18. 虛擬節(jié)點(diǎn)[192.168.0.3:111&&VN2]被添加, hash值為1127720370 
  19. 虛擬節(jié)點(diǎn)[192.168.0.3:111&&VN3]被添加, hash值為676720500 
  20. 虛擬節(jié)點(diǎn)[192.168.0.3:111&&VN4]被添加, hash值為2050578780 
  21. 虛擬節(jié)點(diǎn)[192.168.0.4:111&&VN0]被添加, hash值為586921010 
  22. 虛擬節(jié)點(diǎn)[192.168.0.4:111&&VN1]被添加, hash值為184078390 
  23. 虛擬節(jié)點(diǎn)[192.168.0.4:111&&VN2]被添加, hash值為1331645117 
  24. 虛擬節(jié)點(diǎn)[192.168.0.4:111&&VN3]被添加, hash值為918790803 
  25. 虛擬節(jié)點(diǎn)[192.168.0.4:111&&VN4]被添加, hash值為1232193678 
  26.  
  27. [127.0.0.1:1111]的hash值為380278925, 被路由到結(jié)點(diǎn)[192.168.0.0:111] 
  28. [221.226.0.1:2222]的hash值為1493545632, 被路由到結(jié)點(diǎn)[192.168.0.0:111] 
  29. [10.211.0.1:3333]的hash值為1393836017, 被路由到結(jié)點(diǎn)[192.168.0.2:111] 

從代碼運(yùn)行結(jié)果看，每個(gè)點(diǎn)路由到的服務(wù)器都是Hash值順時(shí)針離它最近的那個(gè)服務(wù)器節(jié)點(diǎn)，沒有任何問題。

通過采取虛擬節(jié)點(diǎn)的方法，一個(gè)真實(shí)結(jié)點(diǎn)不再固定在Hash換上的某個(gè)點(diǎn)，而是大量地分布在整個(gè)Hash環(huán)上，這樣即使上線、下線服務(wù)器，也不會(huì)造成整體的負(fù)載不均衡。

后記

在寫本文的時(shí)候，很多知識(shí)我也是邊寫邊學(xué)，難免有很多寫得不好、理解得不透徹的地方，而且代碼整體也比較糙，未有考慮到可能的各種情況。拋磚引玉，一方面，寫得不對(duì)的地方，還望網(wǎng)友朋友們指正；另一方面，后續(xù)我也將通過自己的工作、學(xué)習(xí)不斷完善上面的代碼。

 

責(zé)任編輯：王雪燕 來源： 五月的倉頡
JavaHash算法
相關(guān)推薦

2022-11-10 07:49:09

hash算法代碼

2022-03-22 09:54:22

Hash算法

2016-12-19 18:41:09

哈希算法Java數(shù)據(jù)

2021-05-19 21:50:46

Hash算法測(cè)試

2021-02-05 08:00:48

哈希算法?機(jī)器

2018-08-08 15:51:44

Hash分布式算法

2017-07-25 14:38:56

數(shù)據(jù)庫一致性非鎖定讀一致性鎖定讀

2020-11-24 09:03:41

一致性MySQLMVCC

2022-01-11 17:23:51

算法負(fù)載均衡Hash

2020-03-16 11:55:28

PaxosRaft協(xié)議

2019-10-11 23:27:19

分布式一致性算法開發(fā)

2020-07-20 08:30:37

算法哈希分布式系統(tǒng)

2021-08-13 07:56:13

Raft算法日志

2021-07-27 08:57:10

算法一致性哈希哈希算法

2022-12-14 08:23:30

2019-12-09 10:37:27

Hash算法面試

2021-09-18 08:54:19

zookeeper一致性算法CAP

2021-02-02 12:40:50

哈希算法數(shù)據(jù)

2023-12-12 08:00:50

節(jié)點(diǎn)哈希算法

2018-07-05 09:41:08

一致性哈希算法
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)