• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 200, comments - 8, trackbacks - 0, articles - 0

            第十六~第二十章:全排列,跳臺階,奇偶排序,第一個只出現一次等問題

            作者:July、2011.10.16。
            出處:http://blog.csdn.net/v_JULY_v

            引言

                最近這幾天閑職在家,一忙著投簡歷,二為準備面試而搜集整理各種面試題。故常常關注個人所建的Algorithms1-14群內朋友關于筆試,面試,宣講會,offer,薪資的討論以及在群內發布的各種筆/面試題,常感言道:咱們這群人之前已經在學校受夠了學校的那種應試教育,如今出來找工作又得東奔西走去參加各種筆試/面試,著實亦不輕松。幻想,如果在企業與求職者之間有個中間面試服務平臺就更好了。

                ok,閑話少扯。在上一篇文章中,已經說過,“個人正在針對那100題一題一題的寫文章,多種思路,不斷優化,即成程序員編程藝術系列。”現本編程藝術系列繼續開始創作,你而后自會和我有同樣的感慨:各種面試題千變萬化,層出不窮,但基本類型,解決問題的思路基本一致。

                本文為程序員編程藝術第十六章~第二十章,包含以下5個問題:

            1. 全排列;
            2. 跳臺階;
            3. 奇偶排序;
            4. 第一個只出現一次的字符;
            5. 一致性哈希算法。

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

            第十六章、全排列問題

            53.字符串的排列。
            題目:輸入一個字符串,打印出該字符串中字符的所有排列。
            例如輸入字符串abc,則輸出由字符a、b、c 所能排列出來的所有字符串
            abc、acb、bac、bca、cab 和cba。

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

            • 一、遞歸實現
              從集合中依次選出每一個元素,作為排列的第一個元素,然后對剩余的元素進行全排列,如此遞歸處理,從而得到所有元素的全排列。以對字符串abc進行全排列為例,我們可以這么做:以abc為例
              固定a,求后面bc的排列:abc,acb,求好后,a和b交換,得到bac
              固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
              固定c,求后面ba的排列:cba,cab。代碼可如下編寫所示:
            1. template <typename T>  
            2. void CalcAllPermutation_R(T perm[], int first, int num)  
            3. {  
            4.     if (num <= 1) {  
            5.         return;  
            6.     }  
            7.       
            8.     for (int i = first; i < first + num; ++i) {  
            9.         swap(perm[i], perm[first]);  
            10.         CalcAllPermutation_R(perm, first + 1, num - 1);  
            11.         swap(perm[i], perm[first]);  
            12.     }  
            13. }  
                或者如此編寫,亦可:
            1. void Permutation(char* pStr, char* pBegin);  
            2.   
            3. void Permutation(char* pStr)  
            4. {  
            5.       Permutation(pStr, pStr);  
            6. }  
            7.   
            8. void Permutation(char* pStr, char* pBegin)  
            9. {  
            10.     if(!pStr || !pBegin)  
            11.         return;  
            12.       
            13.     if(*pBegin == '\0')  
            14.     {  
            15.         printf("%s\n", pStr);  
            16.     }  
            17.     else  
            18.     {  
            19.         for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)  
            20.         {  
            21.             // swap pCh and pBegin  
            22.             char temp = *pCh;  
            23.             *pCh = *pBegin;  
            24.             *pBegin = temp;  
            25.               
            26.             Permutation(pStr, pBegin + 1);    
            27.             // restore pCh and pBegin  
            28.             temp = *pCh;  
            29.             *pCh = *pBegin;  
            30.             *pBegin = temp;  
            31.         }  
            32.     }  
            33. }  
            • 二、字典序排列
              把升序的排列(當然,也可以實現為降序)作為當前排列開始,然后依次計算當前排列的下一個字典序排列。
              對當前排列從后向前掃描,找到一對為升序的相鄰元素,記為i和j(i < j)。如果不存在這樣一對為升序的相鄰元素,則所有排列均已找到,算法結束;否則,重新對當前排列從后向前掃描,找到第一個大于i的元素k,交換i和k,然后對從j開始到結束的子序列反轉,則此時得到的新排列就為下一個字典序排列。這種方式實現得到的所有排列是按字典序有序的,這也是C++ STL算法next_permutation的思想。算法實現如下:
            1. template <typename T>  
            2. void CalcAllPermutation(T perm[], int num)  
            3. {  
            4.     if (num < 1)  
            5.         return;  
            6.           
            7.     while (true) {  
            8.         int i;  
            9.         for (i = num - 2; i >= 0; --i) {  
            10.             if (perm[i] < perm[i + 1])  
            11.                 break;  
            12.         }  
            13.           
            14.         if (i < 0)  
            15.             break;  // 已經找到所有排列  
            16.       
            17.         int k;  
            18.         for (k = num - 1; k > i; --k) {  
            19.             if (perm[k] > perm[i])  
            20.                 break;  
            21.         }  
            22.           
            23.         swap(perm[i], perm[k]);  
            24.         reverse(perm + i + 1, perm + num);  
            25.          
            26.     }  
            27. }  
              擴展:如果不是求字符的所有排列,而是求字符的所有組合,應該怎么辦呢?當輸入的字符串中含有相同的字符串時,相同的字符交換位置是不同的排列,但是同一個組合。舉個例子,如果輸入abc,它的組合有a、b、c、ab、ac、bc、abc。

            第十七章、跳臺階問題

            27.跳臺階問題
            題目:一個臺階總共有n 級,如果一次可以跳1 級,也可以跳2 級。
            求總共有多少總跳法,并分析算法的時間復雜度。

                分析:在九月騰訊,創新工場,淘寶等公司最新面試十三題中第23題又出現了這個問題,題目描述如下:23、人人筆試1:一個人上臺階可以一次上1個,2個,或者3個,問這個人上n層的臺階,總共有幾種走法?咱們先撇開這個人人筆試的問題(其實差別就在于人人筆試題中多了一次可以跳三級的情況而已),先來看這個第27題。

                首先考慮最簡單的情況。如果只有1級臺階,那顯然只有一種跳法。如果有2級臺階,那就有兩種跳的方法了:一種是分兩次跳,每次跳1級;另外一種就是一次跳2級。

                現在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數,記為f(n)。當n>2時,第一次跳的時候就有兩種不同的選擇:一是第一次只跳1級,此時跳法數目等于后面剩下的n-1級臺階的跳法數目,即為f(n-1);另外一種選擇是第一次跳2級,此時跳法數目等于后面剩下的n-2級臺階的跳法數目,即為f(n-2)。因此n級臺階時的不同跳法的總數f(n)=f(n-1)+(f-2)。

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

                原來上述問題就是我們平常所熟知的Fibonacci數列問題。可編寫代碼,如下:

            1. long long Fibonacci_Solution1(unsigned int n)  
            2. {  
            3.     int result[2] = {0, 1};  
            4.     if(n < 2)  
            5.         return result[n];  
            6.       
            7.     return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);  
            8. }  

                 那么,如果是人人筆試那道題呢?一個人上臺階可以一次上1個,2個,或者3個,豈不是可以輕而易舉的寫下如下公式:

                    /      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

                行文至此,你可能會認為問題已經解決了,但事實上沒有:

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

              第十八章、奇偶調序

              54.調整數組順序使奇數位于偶數前面。
              題目:輸入一個整數數組,調整數組中數字的順序,使得所有奇數位于數組的前半部分,
              所有偶數位于數組的后半部分。要求時間復雜度為O(n)。

              分析:

              1. 你當然可以從頭掃描這個數組,每碰到一個偶數時,拿出這個數字,并把位于這個數字后面的所有數字往前挪動一位。挪完之后在數組的末尾有一個空位,這時把該偶數放入這個空位。由于碰到一個偶數,需要移動O(n)個數字,只是這種方法總的時間復雜度是O(n),不符合要求,pass
              2. 很簡單,維護兩個指針,一個指針指向數組的第一個數字,向后移動;一個個指針指向最后一個數字,向前移動。如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數,我們就交換這兩個數字。
                  思路有了,接下來,寫代碼實現:
              1. //思路,很簡答,倆指針,一首一尾  
              2. //如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數,  
              3. //我們就交換這兩個數字  
              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. //如果限制空間復雜度為O(1),時間為O(N),且奇偶數之間相對順序不變,就相當于正負數間順序調整的那道題了。  
              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))   //偶數  
              31.         {  
              32.             pBegin ++;  
              33.             continue;  
              34.         }  
              35.           
              36.         // if *pEnd does not satisfy func, move backward  
              37.         if(func(*pEnd))      //奇數  
              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. }  
                  細心的讀者想必注意到了上述程序注釋中所說的“如果限制空間復雜度為O(1),時間為O(N)就相當于正負數間順序調整的那道題了”,沒錯,它與個人之前整理的一文中的第5題極其類似:5、一個未排序整數數組,有正負數,重新排列使負數排在正數前面,并且要求不改變原來的正負數之間相對順序 比如: input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求時間復雜度O(N),空間O(1) 。此題一直沒看到令我滿意的答案,一般達不到題目所要求的:時間復雜度O(N),空間O(1),且保證原來正負數之間的相對位置不變
                  如果你想到了絕妙的解決辦法,不妨在本文評論下告知于我,或者來信指導(zhoulei0907@yahoo.cn),謝謝。

              第十九章、第一個只出現一次的字符

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

              代碼,可編寫如下:

              1. #include <iostream>  
              2. using namespace std;  
              3.   
              4. //查找第一個只出現一次的字符,第1個程序  
              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));    //數組元素先全部初始化為0  
              16.     p = str;  
              17.     while (*p != '\0')  
              18.         data[(unsigned char)*p++]++;  //遍歷字符串,在相應位置++,(同時,下標強制轉換)  
              19.       
              20.     while (*str != '\0')  
              21.     {  
              22.         if (data[(unsigned char)*str] == 1)  //最后,輸出那個第一個只出現次數為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. }  
                當然,代碼也可以這么寫(測試正確): 
              1. //查找第一個只出現一次的字符,第2個程序  
              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}; //存入數組,并初始化為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筆試題附加題
                  問題描述: 例如手機朋友網有n個服務器,為了方便用戶的訪問會在服務器上緩存數據,因此用戶每次訪問的時候最好能保持同一臺服務器。
              已有的做法是根據ServerIPIndex[QQNUM%n]得到請求的服務器,這種方法很方便將用戶分到不同的服務器上去。但是如果一臺服務器死掉了,那么n就變為了n-1,那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%(n-1)]基本上都不一樣了,所以大多數用戶的請求都會轉到其他服務器,這樣會發生大量訪問錯誤。

                  問: 如何改進或者換一種方法,使得:
              (1)一臺服務器死掉后,不會造成大面積的訪問錯誤,
              (2)原有的訪問基本還是停留在同一臺服務器上;
              (3)盡量考慮負載均衡。(思路:往分布式一致哈希算法方面考慮。

               

              1. 最土的辦法還是用模余方法:做法很簡單,假設有N臺服務器,現在完好的是M(M<=N),先用N求模,如果不落在完好的機器上,然后再用N-1求模,直到M.這種方式對于壞的機器不多的情況下,具有更好的穩定性。
              2. 一致性哈希算法。

               

                  下面,本文剩下部分重點來講講這個一致性哈希算法。

              應用場景

               

                  在做服務器負載均衡時候可供選擇的負載均衡的算法有很多,包括:  輪循算法(Round Robin)、哈希算法(HASH)、最少連接算法(Least Connection)、響應速度算法(Response Time)、加權法(Weighted )等。其中哈希算法是最為常用的算法.

                  典型的應用場景是: 有N臺服務器提供緩存服務,需要對服務器進行負載均衡,將請求平均分發到每臺服務器上,每臺機器負責1/N的服務。

                  常用的算法是對hash結果取余數 (hash() mod N):對機器編號從0到N-1,按照自定義的hash()算法,對每個請求的hash()值按N取模,得到余數i,然后將請求分發到編號為i的機器。但這樣的算法方法存在致命問題,如果某一臺機器宕機,那么應該落在該機器的請求就無法得到正確的處理,這時需要將當掉的服務器從算法從去除,此時候會有(N-1)/N的服務器的緩存數據需要重新進行計算;如果新增一臺機器,會有N /(N+1)的服務器的緩存數據需要進行重新計算。對于系統而言,這通常是不可接受的顛簸(因為這意味著大量緩存的失效或者數據需要轉移)。那么,如何設計一個負載均衡策略,使得受到影響的請求盡可能的少呢?
                  在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法,可以說Consistent Hashing 是分布式系統負載均衡的首選算法。

              Consistent Hashing算法描述

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

                  consistent hashing 算法早在 1997 年就在論文 Consistent hashing and random trees 中被提出,目前在 cache 系統中應用越來越廣泛;

              1 基本場景

              比如你有 N 個 cache 服務器(后面簡稱 cache ),那么如何將一個對象 object 映射到 N 個 cache 上呢,你很可能會采用類似下面的通用方法計算 object 的 hash 值,然后均勻的映射到到 N 個 cache ;

              hash(object)%N

              一切都運行正常,再考慮如下的兩種情況;

              1. 一個 cache 服務器 m down 掉了(在實際應用中必須要考慮這種情況),這樣所有映射到 cache m 的對象都會失效,怎么辦,需要把 cache m 從 cache 中移除,這時候 cache 是 N-1 臺,映射公式變成了 hash(object)%(N-1) ;
              2. 由于訪問加重,需要添加 cache ,這時候 cache 是 N+1 臺,映射公式變成了 hash(object)%(N+1) ;

                  1 和 2 意味著什么?這意味著突然之間幾乎所有的 cache 都失效了。對于服務器而言,這是一場災難,洪水般的訪問都會直接沖向后臺服務器;再來考慮第三個問題,由于硬件能力越來越強,你可能想讓后面添加的節點多做點活,顯然上面的 hash 算法也做不到。

                    有什么方法可以改變這個狀況呢,這就是consistent hashing。

              2 hash 算法和單調性

                Hash 算法的一個衡量指標是單調性( Monotonicity ),定義如下:

                單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中,又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去,而不會被映射到舊的緩沖集合中的其他緩沖區。

                  容易看到,上面的簡單 hash 算法 hash(object)%N 難以滿足單調性要求。

              3 consistent hashing 算法的原理

                  consistent hashing 是一種 hash 算法,簡單的說,在移除 / 添加一個 cache 時,它能夠盡可能小的改變已存在 key 映射關系,盡可能的滿足單調性的要求。

                  下面就來按照 5 個步驟簡單講講 consistent hashing 算法的基本原理。

              3.1 環形hash 空間

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


              3.2 把對象映射到hash 空間

                  接下來考慮 4 個對象 object1~object4 ,通過 hash 函數計算出的 hash 值 key 在環上的分布如圖 2 所示。

              hash(object1) = key1;

              … …

              hash(object4) = key4;

              3.3 把cache 映射到hash 空間

                  Consistent hashing 的基本思想就是將對象和 cache 都映射到同一個 hash 數值空間中,并且使用相同的hash 算法。

                  假設當前有 A,B 和 C 共 3 臺 cache ,那么其映射結果將如圖 3 所示,他們在 hash 空間中,以對應的 hash值排列。

              hash(cache A) = key A;

              … …

              hash(cache C) = key C;


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

              3.4 把對象映射到cache

                  現在 cache 和對象都已經通過同一個 hash 算法映射到 hash 數值空間中了,接下來要考慮的就是如何將對象映射到 cache 上面了。

                  在這個環形空間中,如果沿著順時針方向從對象的 key 值出發,直到遇見一個 cache ,那么就將該對象存儲在這個 cache 上,因為對象和 cache 的 hash 值是固定的,因此這個 cache 必然是唯一和確定的。這樣不就找到了對象和 cache 的映射方法了嗎?!

                  依然繼續上面的例子(參見圖 3 ),那么根據上面的方法,對象 object1 將被存儲到 cache A 上; object2和 object3 對應到 cache C ; object4 對應到 cache B ;

              3.5 考察cache 的變動

                  前面講過,通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調性,當 cache 有所變動時,cache 會失效,進而對后臺服務器造成巨大的沖擊,現在就來分析分析 consistent hashing 算法。

              3.5.1 移除 cache

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

                  因此這里僅需要變動對象 object4 ,將其重新映射到 cache C 上即可;參見圖 4 。


              3.5.2 添加 cache

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

                  因此這里僅需要變動對象 object2 ,將其重新映射到 cache D 上;參見圖 5 。

              4 虛擬節點

              考量 Hash 算法的另一個指標是平衡性 (Balance) ,定義如下:

              平衡性

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

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

                  為了解決這種情況, consistent hashing 引入了“虛擬節點”的概念,它可以如下定義:

              “虛擬節點”( virtual node )是實際節點在 hash 空間的復制品( replica ),一實際個節點對應了若干個“虛擬節點”,這個對應個數也成為“復制個數”,“虛擬節點”在 hash 空間中以 hash 值排列。

                  仍以僅部署 cache A 和 cache C 的情況為例,在圖 4 中我們已經看到, cache 分布并不均勻。現在我們引入虛擬節點,并設置“復制個數”為 2 ,這就意味著一共會存在 4 個“虛擬節點”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假設一種比較理想的情況,參見圖 6 。


               此時,對象到“虛擬節點”的映射關系為:

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

                  因此對象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。

                  引入“虛擬節點”后,映射關系就從 { 對象 -> 節點 } 轉換到了 { 對象 -> 虛擬節點 } 。查詢物體所在 cache時的映射關系如圖 7 所示。

                “虛擬節點”的 hash 計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 cache A 的 IP 地址為202.168.14.241 。

                  引入“虛擬節點”前,計算 cache A 的 hash 值:

              Hash(“202.168.14.241”);

                  引入“虛擬節點”后,計算“虛擬節”點 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. 行文倉促,若有任何問題或漏洞,歡迎不吝指正或賜教。謝謝。轉載,請注明出處。完。

               

               

               

            久久精品夜色噜噜亚洲A∨| 成人综合久久精品色婷婷| 国产精品99久久久久久董美香| 深夜久久AAAAA级毛片免费看| 伊人久久大香线蕉av不卡| 久久亚洲天堂| 国产综合免费精品久久久| 一级做a爰片久久毛片看看| 日批日出水久久亚洲精品tv| 夜夜亚洲天天久久| 99久久精品无码一区二区毛片| 青青草国产成人久久91网| 亚洲va久久久噜噜噜久久狠狠 | 亚洲精品乱码久久久久久蜜桃图片 | 久久99热这里只有精品国产| 国产aⅴ激情无码久久| 久久精品人妻一区二区三区| 久久久久人妻一区精品果冻| 日韩精品久久久久久| 久久国产精品国产自线拍免费| 91精品国产9l久久久久| 国产AⅤ精品一区二区三区久久| 久久久国产精华液| 久久国产精品一区| 久久综合亚洲色HEZYO社区| 久久夜色精品国产网站| 欧美精品福利视频一区二区三区久久久精品| 日韩一区二区三区视频久久| 国产91色综合久久免费| 精品无码久久久久久午夜| 亚洲欧美日韩中文久久| 久久精品黄AA片一区二区三区| 久久影院午夜理论片无码 | 色妞色综合久久夜夜| 国内精品久久久久久久久| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 国产V亚洲V天堂无码久久久| 少妇无套内谢久久久久| 看久久久久久a级毛片| 伊人精品久久久久7777| 亚洲第一永久AV网站久久精品男人的天堂AV|