mysileng

第十六~第二十章：全排列，跳臺(tái)階，奇偶排序，第一個(gè)只出現(xiàn)一次等問題

引言

    最近這幾天閑職在家，一忙著投簡(jiǎn)歷，二為準(zhǔn)備面試而搜集整理各種面試題。故常常關(guān)注個(gè)人所建的Algorithms1-14群內(nèi)朋友關(guān)于筆試，面試，宣講會(huì)，offer，薪資的討論以及在群內(nèi)發(fā)布的各種筆/面試題，常感言道：咱們這群人之前已經(jīng)在學(xué)校受夠了學(xué)校的那種應(yīng)試教育，如今出來找工作又得東奔西走去參加各種筆試/面試，著實(shí)亦不輕松。幻想，如果在企業(yè)與求職者之間有個(gè)中間面試服務(wù)平臺(tái)就更好了。

    ok，閑話少扯。在上一篇文章中，已經(jīng)說過，“個(gè)人正在針對(duì)那100題一題一題的寫文章，多種思路，不斷優(yōu)化，即成程序員編程藝術(shù)系列。”現(xiàn)本編程藝術(shù)系列繼續(xù)開始創(chuàng)作，你而后自會(huì)和我有同樣的感慨：各種面試題千變?nèi)f化，層出不窮，但基本類型，解決問題的思路基本一致。

    本文為程序員編程藝術(shù)第十六章~第二十章，包含以下5個(gè)問題：

1. 全排列；
2. 跳臺(tái)階；
3. 奇偶排序；
4. 第一個(gè)只出現(xiàn)一次的字符；
5. 一致性哈希算法。

    同時(shí)，本文會(huì)在解答去年微軟面試100題的部分題目時(shí)，盡量結(jié)合今年最近各大IT公司最新的面試題來講解，兩相對(duì)比，彼此對(duì)照，相信你會(huì)更加贊同我上面的話。且本文也不奢望讀者能從中學(xué)到什么高深技術(shù)之類的東西，只求讀者看此文看著舒服便可，通順流暢以致一口氣讀完而無任何壓力。ok，有任何問題，歡迎不吝指正。謝謝。

第十六章、全排列問題

53.字符串的排列。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來的所有字符串
abc、acb、bac、bca、cab 和cba。

    分析：此題最初整理于去年的微軟面試100題中第53題，第二次整理于微軟、Google等公司非常好的面試題及解答[第61-70題] 第67題。無獨(dú)有偶，這個(gè)問題今年又出現(xiàn)于今年的2011.10.09百度筆試題中。ok，接下來，咱們先好好分析這個(gè)問題。

• 一、遞歸實(shí)現(xiàn)
  從集合中依次選出每一個(gè)元素，作為排列的第一個(gè)元素，然后對(duì)剩余的元素進(jìn)行全排列，如此遞歸處理，從而得到所有元素的全排列。以對(duì)字符串a(chǎn)bc進(jìn)行全排列為例，我們可以這么做：以abc為例
  固定a，求后面bc的排列：abc，acb，求好后，a和b交換，得到bac
  固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
  固定c，求后面ba的排列：cba，cab。代碼可如下編寫所示：

27.跳臺(tái)階問題
題目：一個(gè)臺(tái)階總共有n 級(jí)，如果一次可以跳1 級(jí)，也可以跳2 級(jí)。
求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。

    分析：在九月騰訊，創(chuàng)新工場(chǎng)，淘寶等公司最新面試十三題中第23題又出現(xiàn)了這個(gè)問題，題目描述如下：23、人人筆試1：一個(gè)人上臺(tái)階可以一次上1個(gè)，2個(gè)，或者3個(gè)，問這個(gè)人上n層的臺(tái)階，總共有幾種走法？咱們先撇開這個(gè)人人筆試的問題（其實(shí)差別就在于人人筆試題中多了一次可以跳三級(jí)的情況而已），先來看這個(gè)第27題。

    首先考慮最簡(jiǎn)單的情況。如果只有1級(jí)臺(tái)階，那顯然只有一種跳法。如果有2級(jí)臺(tái)階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級(jí)；另外一種就是一次跳2級(jí)。

    現(xiàn)在我們?cè)賮碛懻撘话闱闆r。我們把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目，即為f(n-2)。因此n級(jí)臺(tái)階時(shí)的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。

    我們把上面的分析用一個(gè)公式總結(jié)如下：
        /     1                              n=1
f(n)=      2                              n=2
        \  f(n-1) + f(n-2)            n>2

    原來上述問題就是我們平常所熟知的Fibonacci數(shù)列問題。可編寫代碼，如下：

     那么，如果是人人筆試那道題呢?一個(gè)人上臺(tái)階可以一次上1個(gè)，2個(gè)，或者3個(gè)，豈不是可以輕而易舉的寫下如下公式：

        /      1                                      n=1
f(n)=      2                                      n=2

              4                                      n=3       //111, 12, 21, 3
        \  f(n-1)+(f-2)+f(n-3)            n>3

    行文至此，你可能會(huì)認(rèn)為問題已經(jīng)解決了，但事實(shí)上沒有：

1. 用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的，我們可以嘗試用遞推方法解決。具體如何操作，讀者自行思考。
   
2. 有一種方法，能在O(logn)的時(shí)間復(fù)雜度內(nèi)求解Fibonacci數(shù)列問題，你能想到么?
   
   

   第十八章、奇偶調(diào)序

   54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。
   題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
   所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。

   分析：

   1. 你當(dāng)然可以從頭掃描這個(gè)數(shù)組，每碰到一個(gè)偶數(shù)時(shí)，拿出這個(gè)數(shù)字，并把位于這個(gè)數(shù)字后面的所有數(shù)字往前挪動(dòng)一位。挪完之后在數(shù)組的末尾有一個(gè)空位，這時(shí)把該偶數(shù)放入這個(gè)空位。由于碰到一個(gè)偶數(shù)，需要移動(dòng)O(n)個(gè)數(shù)字，只是這種方法總的時(shí)間復(fù)雜度是O(n^２)，不符合要求，pass。
      
   2. 很簡(jiǎn)單，維護(hù)兩個(gè)指針，一個(gè)指針指向數(shù)組的第一個(gè)數(shù)字，向后移動(dòng)；一個(gè)個(gè)指針指向最后一個(gè)數(shù)字，向前移動(dòng)。如果第一個(gè)指針指向的數(shù)字是偶數(shù)而第二個(gè)指針指向的數(shù)字是奇數(shù)，我們就交換這兩個(gè)數(shù)字。
      
       思路有了，接下來，寫代碼實(shí)現(xiàn)：

   1. //思路，很簡(jiǎn)答，倆指針，一首一尾  
   2. //如果第一個(gè)指針指向的數(shù)字是偶數(shù)而第二個(gè)指針指向的數(shù)字是奇數(shù)，  
   3. //我們就交換這兩個(gè)數(shù)字  
   4.   
   5. // 2 1 3 4 6 5 7   
   6. // 7 1 3 4 6 5 2  
   7. // 7 1 3 5 6 4 2  
   8.   
   9. //如果限制空間復(fù)雜度為O（1），時(shí)間為O（N），且奇偶數(shù)之間相對(duì)順序不變，就相當(dāng)于正負(fù)數(shù)間順序調(diào)整的那道題了。  
   10.   
   11. //copyright@2010 zhedahht。  
   12. void Reorder(int *pData, unsigned int length, bool (*func)(int));  
   13. bool isEven(int n);  
   14. void ReorderOddEven(int *pData, unsigned int length)  
   15. {  
   16.     if(pData == NULL || length == 0)  
   17.         return;  
   18.       
   19.     Reorder(pData, length, isEven);  
   20. }  
   21. void Reorder(int *pData, unsigned int length, bool (*func)(int))  
   22. {  
   23.     if(pData == NULL || length == 0)  
   24.         return;  
   25.     int *pBegin = pData;  
   26.     int *pEnd = pData + length - 1;  
   27.     while(pBegin < pEnd)  
   28.     {  
   29.         // if *pBegin does not satisfy func, move forward  
   30.         if(!func(*pBegin))   //偶數(shù)  
   31.         {  
   32.             pBegin ++;  
   33.             continue;  
   34.         }  
   35.           
   36.         // if *pEnd does not satisfy func, move backward  
   37.         if(func(*pEnd))      //奇數(shù)  
   38.         {  
   39.             pEnd --;  
   40.             continue;  
   41.         }  
   42.         // if *pBegin satisfy func while *pEnd does not,  
   43.         // swap these integers  
   44.         int temp = *pBegin;  
   45.         *pBegin = *pEnd;  
   46.         *pEnd = temp;  
   47.     }  
   48. }  
   49. bool isEven(int n)  
   50. {  
   51.     return (n & 1) == 0;  
   52. }  
       細(xì)心的讀者想必注意到了上述程序注釋中所說的“如果限制空間復(fù)雜度為O（1），時(shí)間為O（N）就相當(dāng)于正負(fù)數(shù)間順序調(diào)整的那道題了”，沒錯(cuò)，它與個(gè)人之前整理的一文中的第5題極其類似：5、一個(gè)未排序整數(shù)數(shù)組，有正負(fù)數(shù)，重新排列使負(fù)數(shù)排在正數(shù)前面，并且要求不改變?cè)瓉淼恼?fù)數(shù)之間相對(duì)順序 比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求時(shí)間復(fù)雜度O(N),空間O(1) 。（此題一直沒看到令我滿意的答案，一般達(dá)不到題目所要求的：時(shí)間復(fù)雜度O(N),空間O(1)，且保證原來正負(fù)數(shù)之間的相對(duì)位置不變）。
       如果你想到了絕妙的解決辦法，不妨在本文評(píng)論下告知于我，或者來信指導(dǎo)（zhoulei0907@yahoo.cn），謝謝。

   第十九章、第一個(gè)只出現(xiàn)一次的字符

   第17 題：題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
   
       分析：這道題是2006 年google 的一道筆試題。它在今年又出現(xiàn)了，不過換了一種形式。即最近的搜狐筆試大題：數(shù)組非常長(zhǎng)，如何找到第一個(gè)只出現(xiàn)一次的數(shù)字，說明算法復(fù)雜度。此問題已經(jīng)在程序員編程藝術(shù)系列第二章中有所闡述，在此不再作過多講解。

   代碼，可編寫如下：

   1. #include <iostream>  
   2. using namespace std;  
   3.   
   4. //查找第一個(gè)只出現(xiàn)一次的字符，第1個(gè)程序  
   5. //copyright@ Sorehead && July  
   6. //July、updated，2011.04.24.  
   7. char find_first_unique_char(char *str)  
   8. {  
   9.     int data[256];  
   10.     char *p;  
   11.       
   12.     if (str == NULL)  
   13.         return '\0';  
   14.       
   15.     memset(data, 0, sizeof(data));    //數(shù)組元素先全部初始化為0  
   16.     p = str;  
   17.     while (*p != '\0')  
   18.         data[(unsigned char)*p++]++;  //遍歷字符串，在相應(yīng)位置++，（同時(shí)，下標(biāo)強(qiáng)制轉(zhuǎn)換）  
   19.       
   20.     while (*str != '\0')  
   21.     {  
   22.         if (data[(unsigned char)*str] == 1)  //最后，輸出那個(gè)第一個(gè)只出現(xiàn)次數(shù)為1的字符  
   23.             return *str;  
   24.           
   25.         str++;  
   26.     }  
   27.       
   28.     return '\0';  
   29. }  
   30.   
   31. int main()  
   32. {  
   33.     char *str = "afaccde";  
   34.     cout << find_first_unique_char(str) << endl;  
   35.     return 0;  
   36. }  

     當(dāng)然，代碼也可以這么寫（測(cè)試正確）： 

   1. //查找第一個(gè)只出現(xiàn)一次的字符，第2個(gè)程序  
   2. //copyright@ yansha  
   3. //July、updated，2011.04.24.  
   4. char FirstNotRepeatChar(char* pString)  
   5. {  
   6.     if(!pString)  
   7.         return '\0';  
   8.       
   9.     const int tableSize = 256;  
   10.     int hashTable[tableSize] = {0}; //存入數(shù)組，并初始化為0  
   11.       
   12.     char* pHashKey = pString;  
   13.     while(*(pHashKey) != '\0')  
   14.         hashTable[*(pHashKey++)]++;  
   15.       
   16.     while(*pString != '\0')  
   17.     {  
   18.         if(hashTable[*pString] == 1)  
   19.             return *pString;  
   20.           
   21.         pString++;  
   22.     }  
   23.     return '\0';  //沒有找到滿足條件的字符，退出  
   24. }  

   第二十章、一致性哈希算法

   tencent2012筆試題附加題
       問題描述： 例如手機(jī)朋友網(wǎng)有n個(gè)服務(wù)器，為了方便用戶的訪問會(huì)在服務(wù)器上緩存數(shù)據(jù)，因此用戶每次訪問的時(shí)候最好能保持同一臺(tái)服務(wù)器。
   已有的做法是根據(jù)ServerIPIndex[QQNUM%n]得到請(qǐng)求的服務(wù)器，這種方法很方便將用戶分到不同的服務(wù)器上去。但是如果一臺(tái)服務(wù)器死掉了，那么n就變?yōu)榱薾-1，那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%（n-1）]基本上都不一樣了，所以大多數(shù)用戶的請(qǐng)求都會(huì)轉(zhuǎn)到其他服務(wù)器，這樣會(huì)發(fā)生大量訪問錯(cuò)誤。

       問： 如何改進(jìn)或者換一種方法，使得：
   （1）一臺(tái)服務(wù)器死掉后，不會(huì)造成大面積的訪問錯(cuò)誤，
   （2）原有的訪問基本還是停留在同一臺(tái)服務(wù)器上；
   （3）盡量考慮負(fù)載均衡。（思路：往分布式一致哈希算法方面考慮。）

    

   1. 最土的辦法還是用模余方法：做法很簡(jiǎn)單，假設(shè)有N臺(tái)服務(wù)器，現(xiàn)在完好的是M（M<=N),先用N求模，如果不落在完好的機(jī)器上，然后再用N-1求模，直到M.這種方式對(duì)于壞的機(jī)器不多的情況下，具有更好的穩(wěn)定性。
      
   2. 一致性哈希算法。

    

       下面，本文剩下部分重點(diǎn)來講講這個(gè)一致性哈希算法。
   

   應(yīng)用場(chǎng)景

    

       在做服務(wù)器負(fù)載均衡時(shí)候可供選擇的負(fù)載均衡的算法有很多，包括：  輪循算法（Round Robin）、哈希算法（HASH）、最少連接算法（Least Connection）、響應(yīng)速度算法（Response Time）、加權(quán)法（Weighted ）等。其中哈希算法是最為常用的算法.

       典型的應(yīng)用場(chǎng)景是： 有N臺(tái)服務(wù)器提供緩存服務(wù)，需要對(duì)服務(wù)器進(jìn)行負(fù)載均衡，將請(qǐng)求平均分發(fā)到每臺(tái)服務(wù)器上，每臺(tái)機(jī)器負(fù)責(zé)1/N的服務(wù)。

       常用的算法是對(duì)hash結(jié)果取余數(shù) (hash() mod N)：對(duì)機(jī)器編號(hào)從0到N-1，按照自定義的hash()算法，對(duì)每個(gè)請(qǐng)求的hash()值按N取模，得到余數(shù)i，然后將請(qǐng)求分發(fā)到編號(hào)為i的機(jī)器。但這樣的算法方法存在致命問題，如果某一臺(tái)機(jī)器宕機(jī)，那么應(yīng)該落在該機(jī)器的請(qǐng)求就無法得到正確的處理，這時(shí)需要將當(dāng)?shù)舻姆?wù)器從算法從去除，此時(shí)候會(huì)有(N-1)/N的服務(wù)器的緩存數(shù)據(jù)需要重新進(jìn)行計(jì)算；如果新增一臺(tái)機(jī)器，會(huì)有N /(N+1)的服務(wù)器的緩存數(shù)據(jù)需要進(jìn)行重新計(jì)算。對(duì)于系統(tǒng)而言，這通常是不可接受的顛簸（因?yàn)檫@意味著大量緩存的失效或者數(shù)據(jù)需要轉(zhuǎn)移）。那么，如何設(shè)計(jì)一個(gè)負(fù)載均衡策略，使得受到影響的請(qǐng)求盡可能的少呢？
       在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以說Consistent Hashing 是分布式系統(tǒng)負(fù)載均衡的首選算法。

   Consistent Hashing算法描述

       下面以Memcached中的Consisten Hashing算法為例說明。

       consistent hashing 算法早在 1997 年就在論文 Consistent hashing and random trees 中被提出，目前在 cache 系統(tǒng)中應(yīng)用越來越廣泛；

   1 基本場(chǎng)景

   比如你有 N 個(gè) cache 服務(wù)器（后面簡(jiǎn)稱 cache ），那么如何將一個(gè)對(duì)象 object 映射到 N 個(gè) cache 上呢，你很可能會(huì)采用類似下面的通用方法計(jì)算 object 的 hash 值，然后均勻的映射到到 N 個(gè) cache ；

   hash(object)%N

   一切都運(yùn)行正常，再考慮如下的兩種情況；

   1. 一個(gè) cache 服務(wù)器 m down 掉了（在實(shí)際應(yīng)用中必須要考慮這種情況），這樣所有映射到 cache m 的對(duì)象都會(huì)失效，怎么辦，需要把 cache m 從 cache 中移除，這時(shí)候 cache 是 N-1 臺(tái)，映射公式變成了 hash(object)%(N-1) ；
   2. 由于訪問加重，需要添加 cache ，這時(shí)候 cache 是 N+1 臺(tái)，映射公式變成了 hash(object)%(N+1) ；

       1 和 2 意味著什么？這意味著突然之間幾乎所有的 cache 都失效了。對(duì)于服務(wù)器而言，這是一場(chǎng)災(zāi)難，洪水般的訪問都會(huì)直接沖向后臺(tái)服務(wù)器；再來考慮第三個(gè)問題，由于硬件能力越來越強(qiáng)，你可能想讓后面添加的節(jié)點(diǎn)多做點(diǎn)活，顯然上面的 hash 算法也做不到。

         有什么方法可以改變這個(gè)狀況呢，這就是consistent hashing。

   2 hash 算法和單調(diào)性

   　 Hash 算法的一個(gè)衡量指標(biāo)是單調(diào)性（ Monotonicity ），定義如下：

   　 單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。

       容易看到，上面的簡(jiǎn)單 hash 算法 hash(object)%N 難以滿足單調(diào)性要求。

   3 consistent hashing 算法的原理

       consistent hashing 是一種 hash 算法，簡(jiǎn)單的說，在移除 / 添加一個(gè) cache 時(shí)，它能夠盡可能小的改變已存在 key 映射關(guān)系，盡可能的滿足單調(diào)性的要求。

       下面就來按照 5 個(gè)步驟簡(jiǎn)單講講 consistent hashing 算法的基本原理。

   3.1 環(huán)形hash 空間

       考慮通常的 hash 算法都是將 value 映射到一個(gè) 32 為的 key 值，也即是 0~2^32-1 次方的數(shù)值空間；我們可以將這個(gè)空間想象成一個(gè)首（ 0 ）尾（ 2^32-1 ）相接的圓環(huán)，如下面圖 1 所示的那樣。

   
   

   3.2 把對(duì)象映射到hash 空間

       接下來考慮 4 個(gè)對(duì)象 object1~object4 ，通過 hash 函數(shù)計(jì)算出的 hash 值 key 在環(huán)上的分布如圖 2 所示。

   hash(object1) = key1;

   … …

   hash(object4) = key4;
   
   

   3.3 把cache 映射到hash 空間

       Consistent hashing 的基本思想就是將對(duì)象和 cache 都映射到同一個(gè) hash 數(shù)值空間中，并且使用相同的hash 算法。

       假設(shè)當(dāng)前有 A,B 和 C 共 3 臺(tái) cache ，那么其映射結(jié)果將如圖 3 所示，他們?cè)?nbsp;hash 空間中，以對(duì)應(yīng)的 hash值排列。

   hash(cache A) = key A;

   … …

   hash(cache C) = key C;

   
   

   說到這里，順便提一下 cache 的 hash 計(jì)算，一般的方法可以使用 cache 機(jī)器的 IP 地址或者機(jī)器名作為hash 輸入。

   3.4 把對(duì)象映射到cache

       現(xiàn)在 cache 和對(duì)象都已經(jīng)通過同一個(gè) hash 算法映射到 hash 數(shù)值空間中了，接下來要考慮的就是如何將對(duì)象映射到 cache 上面了。

       在這個(gè)環(huán)形空間中，如果沿著順時(shí)針方向從對(duì)象的 key 值出發(fā)，直到遇見一個(gè) cache ，那么就將該對(duì)象存儲(chǔ)在這個(gè) cache 上，因?yàn)閷?duì)象和 cache 的 hash 值是固定的，因此這個(gè) cache 必然是唯一和確定的。這樣不就找到了對(duì)象和 cache 的映射方法了嗎？！

       依然繼續(xù)上面的例子（參見圖 3 ），那么根據(jù)上面的方法，對(duì)象 object1 將被存儲(chǔ)到 cache A 上； object2和 object3 對(duì)應(yīng)到 cache C ； object4 對(duì)應(yīng)到 cache B ；

   3.5 考察cache 的變動(dòng)

       前面講過，通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調(diào)性，當(dāng) cache 有所變動(dòng)時(shí)，cache 會(huì)失效，進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊，現(xiàn)在就來分析分析 consistent hashing 算法。

   3.5.1 移除 cache

       考慮假設(shè) cache B 掛掉了，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅是那些沿 cache B 順時(shí)針遍歷直到下一個(gè) cache （ cache C ）之間的對(duì)象，也即是本來映射到 cache B 上的那些對(duì)象。

       因此這里僅需要變動(dòng)對(duì)象 object4 ，將其重新映射到 cache C 上即可；參見圖 4 。

   
   

   3.5.2 添加 cache

       再考慮添加一臺(tái)新的 cache D 的情況，假設(shè)在這個(gè)環(huán)形 hash 空間中， cache D 被映射在對(duì)象 object2 和object3 之間。這時(shí)受影響的將僅是那些沿 cache D 逆時(shí)針遍歷直到下一個(gè) cache （ cache B ）之間的對(duì)象（它們是也本來映射到 cache C 上對(duì)象的一部分），將這些對(duì)象重新映射到 cache D 上即可。

       因此這里僅需要變動(dòng)對(duì)象 object2 ，將其重新映射到 cache D 上；參見圖 5 。
   
   

   4 虛擬節(jié)點(diǎn)

   考量 Hash 算法的另一個(gè)指標(biāo)是平衡性 (Balance) ，定義如下：

   平衡性

   　　平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

       hash 算法并不是保證絕對(duì)的平衡，如果 cache 較少的話，對(duì)象并不能被均勻的映射到 cache 上，比如在上面的例子中，僅部署 cache A 和 cache C 的情況下，在 4 個(gè)對(duì)象中， cache A 僅存儲(chǔ)了 object1 ，而 cache C 則存儲(chǔ)了 object2 、 object3 和 object4 ；分布是很不均衡的。

       為了解決這種情況， consistent hashing 引入了“虛擬節(jié)點(diǎn)”的概念，它可以如下定義：

   “虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品（ replica ），一實(shí)際個(gè)節(jié)點(diǎn)對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以 hash 值排列。

       仍以僅部署 cache A 和 cache C 的情況為例，在圖 4 中我們已經(jīng)看到， cache 分布并不均勻。現(xiàn)在我們引入虛擬節(jié)點(diǎn)，并設(shè)置“復(fù)制個(gè)數(shù)”為 2 ，這就意味著一共會(huì)存在 4 個(gè)“虛擬節(jié)點(diǎn)”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假設(shè)一種比較理想的情況，參見圖 6 。

   
   

    此時(shí)，對(duì)象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為：

   objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

       因此對(duì)象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。

       引入“虛擬節(jié)點(diǎn)”后，映射關(guān)系就從 { 對(duì)象 -> 節(jié)點(diǎn) } 轉(zhuǎn)換到了 { 對(duì)象 -> 虛擬節(jié)點(diǎn) } 。查詢物體所在 cache時(shí)的映射關(guān)系如圖 7 所示。
   
   

     “虛擬節(jié)點(diǎn)”的 hash 計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的 IP 地址加數(shù)字后綴的方式。例如假設(shè) cache A 的 IP 地址為202.168.14.241 。

       引入“虛擬節(jié)點(diǎn)”前，計(jì)算 cache A 的 hash 值：

   Hash(“202.168.14.241”);

       引入“虛擬節(jié)點(diǎn)”后，計(jì)算“虛擬節(jié)”點(diǎn) cache A1 和 cache A2 的 hash 值：

   Hash(“202.168.14.241#1”);  // cache A1

   Hash(“202.168.14.241#2”);  // cache A2

   后記

   1. 以上部分代碼思路有參考自此博客：http://zhedahht.blog.163.com/blog/。特此注明下。     
   2. 上文第五部分來源：http://blog.csdn.net/sparkliang/article/details/5279393；
      
   3. 行文倉(cāng)促，若有任何問題或漏洞，歡迎不吝指正或賜教。謝謝。轉(zhuǎn)載，請(qǐng)注明出處。完。