第十六~第二十章：全排列，跳臺(tái)階，奇偶排序，第一個(gè)只出現(xiàn)一次等問(wèn)題
作者：July、2011.10.16。
出處： http://blog.csdn.net/v_JULY_v 。
引言
最近這幾天閑職在家，一忙著投簡(jiǎn)歷，二為準(zhǔn)備面試而搜集整理各種面試題。故常常關(guān)注個(gè)人所建的Algorithms1-14群內(nèi)朋友關(guān)于筆試，面試，宣講會(huì)，offer，薪資的討論以及在群內(nèi)發(fā)布的各種筆/面試題，常感言道：咱們這群人之前已經(jīng)在學(xué)校受夠了學(xué)校的那種應(yīng)試教育，如今出來(lái)找工作又得東奔西走去參加各種筆試/面試，著實(shí)亦不輕松。幻想，如果在企業(yè)與求職者之間有個(gè)中間面試服務(wù)平臺(tái)就更好了。
ok，閑話(huà)少扯。在上一篇文章中，已經(jīng)說(shuō)過(guò)，“個(gè)人正在針對(duì)那100題一題一題的寫(xiě)文章，多種思路，不斷優(yōu)化，即成程序員編程藝術(shù)系列。”現(xiàn)本編程藝術(shù)系列繼續(xù)開(kāi)始創(chuàng)作，你而后自會(huì)和我有同樣的感慨：各種面試題千變?nèi)f化，層出不窮，但基本類(lèi)型，解決問(wèn)題的思路基本一致。
本文為程序員編程藝術(shù)第十六章~第二十章，包含以下5個(gè)問(wèn)題：
- 全排列；
- 跳臺(tái)階；
- 奇偶排序；
- 第一個(gè)只出現(xiàn)一次的字符；
- 一致性哈希算法。
同時(shí)，本文會(huì)在解答去年微軟面試100題的部分題目時(shí)，盡量結(jié)合今年最近各大IT公司最新的面試題來(lái)講解，兩相對(duì)比，彼此對(duì)照，相信你會(huì)更加贊同我上面的話(huà)。且本文也不奢望讀者能從中學(xué)到什么高深技術(shù)之類(lèi)的東西，只求讀者看此文看著 舒服 便可 ， 通順流暢以致一口氣讀完而無(wú)任何壓力。ok，有任何問(wèn)題，歡迎不吝指正。謝謝。
第十六章、全排列問(wèn)題
53.字符串的排列。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來(lái)的所有字符串
abc、acb、bac、bca、cab 和cba。
分析：此題最初整理于去年的微軟面試100題中第53題，第二次整理于
微軟、Google等公司非常好的面試題及解答[第61-70題]
第67題。無(wú)獨(dú)有偶，這個(gè)問(wèn)題今年又出現(xiàn)于今年的2011.10.09百度筆試題中。ok，接下來(lái)，咱們先好好分析這個(gè)問(wèn)題。
-
一、遞歸實(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。代碼可如下編寫(xiě)所示：
- template < typename T>
- void CalcAllPermutation_R(Tperm[], int first, int num)
- {
- if (num<=1){
- return ;
- }
- for ( int i=first;i<first+num;++i){
- swap(perm[i],perm[first]);
- CalcAllPermutation_R(perm,first+1,num-1);
- swap(perm[i],perm[first]);
- }
- }
-
二、字典序排列
把升序的排列（當(dāng)然，也可以實(shí)現(xiàn)為降序）作為當(dāng)前排列開(kāi)始，然后依次計(jì)算當(dāng)前排列的下一個(gè)字典序排列。
對(duì)當(dāng)前排列從后向前掃描，找到一對(duì)為升序的相鄰元素，記為i和j（i < j）。如果不存在這樣一對(duì)為升序的相鄰元素，則所有排列均已找到，算法結(jié)束；否則，重新對(duì)當(dāng)前排列從后向前掃描，找到第一個(gè)大于i的元素k，交換i和k，然后對(duì)從j開(kāi)始到結(jié)束的子序列反轉(zhuǎn)，則此時(shí)得到的新排列就為下一個(gè)字典序排列。這種方式實(shí)現(xiàn)得到的所有排列是按字典序有序的，這也是C++ STL算法next_permutation的思想。算法實(shí)現(xiàn)如下：
- template < typename T>
- void CalcAllPermutation(Tperm[], int num)
- {
- if (num<1)
- return ;
- while ( true ){
- int i;
- for (i=num-2;i>=0;--i){
- if (perm[i]<perm[i+1])
- break ;
- }
- if (i<0)
- break ; //已經(jīng)找到所有排列
- int k;
- for (k=num-1;k>i;--k){
- if (perm[k]>perm[i])
- break ;
- }
- swap(perm[i],perm[k]);
- reverse(perm+i+1,perm+num);
- }
- }
第十七章、跳臺(tái)階問(wèn)題
27.跳臺(tái)階問(wèn)題
題目：一個(gè)臺(tái)階總共有n 級(jí)，如果一次可以跳1 級(jí)，也可以跳2 級(jí)。
求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。
分析：在 九月騰訊，創(chuàng)新工場(chǎng)，淘寶等公司最新面試十三題 中第23題又出現(xiàn)了這個(gè)問(wèn)題，題目描述如下：23、人人筆試1：一個(gè)人上臺(tái)階可以一次上1個(gè)，2個(gè)，或者3個(gè)，問(wèn)這個(gè)人上n層的臺(tái)階，總共有幾種走法？咱們先撇開(kāi)這個(gè)人人筆試的問(wèn)題（其實(shí)差別就在于人人筆試題中多了一次可以跳三級(jí)的情況而已），先來(lái)看這個(gè)第27題。
首先考慮最簡(jiǎn)單的情況。如果只有1級(jí)臺(tái)階，那顯然只有一種跳法。如果有2級(jí)臺(tái)階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級(jí)；另外一種就是一次跳2級(jí)。
現(xiàn)在我們?cè)賮?lái)討論一般情況。我們把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-2) n>2
原來(lái)上述問(wèn)題就是我們平常所熟知的 Fibonacci 數(shù)列問(wèn)題。 可編寫(xiě)代碼，如下：
那么，如果是人人筆試那道題呢?一個(gè)人上臺(tái)階可以一次上1個(gè)，2個(gè)，或者3個(gè)，豈不是可以輕而易舉的寫(xiě)下如下公式：
/ 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)為問(wèn)題已經(jīng)解決了，但事實(shí)上沒(méi)有：
-
用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以
n
的指數(shù)的方式遞增的，我們可以嘗試用遞推方法解決。具體如何操作，讀者自行思考。
- 有一種方法，能在O(logn)的時(shí)間復(fù)雜度內(nèi)求解Fibonacci數(shù)列問(wèn)題，你能想到么?
-
同時(shí)，有朋友指出對(duì)于這個(gè)臺(tái)階問(wèn)題只需求冪就可以了（求復(fù)數(shù)冪C++庫(kù)里有），不用任何循環(huán)且復(fù)雜度為O（1），如下圖所示，是否真如此?：
第十八章、奇偶調(diào)序
題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。
分析：
-
你當(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
。
-
很簡(jiǎn)單，維護(hù)兩個(gè)指針，一個(gè)指針指向數(shù)組的第一個(gè)數(shù)字，向后移動(dòng)；一個(gè)個(gè)指針指向最后一個(gè)數(shù)字，向前移動(dòng)。如果第一個(gè)指針指向的數(shù)字是偶數(shù)而第二個(gè)指針指向的數(shù)字是奇數(shù)，我們就交換這兩個(gè)數(shù)字。
第十九章、第一個(gè)只出現(xiàn)一次的字符
代碼，可編寫(xiě)如下：
- #include<iostream>
- using namespace std;
- //查找第一個(gè)只出現(xiàn)一次的字符，第1個(gè)程序
- //copyright@Sorehead&&July
- //July、updated，2011.04.24.
- char find_first_unique_char( char *str)
- {
- int data[256];
- char *p;
- if (str==NULL)
- return '\0' ;
- memset(data,0, sizeof (data)); //數(shù)組元素先全部初始化為0
- p=str;
- while (*p!= '\0' )
- data[(unsigned char )*p++]++; //遍歷字符串，在相應(yīng)位置++，（同時(shí)，下標(biāo)強(qiáng)制轉(zhuǎn)換）
- while (*str!= '\0' )
- {
- if (data[(unsigned char )*str]==1) //最后，輸出那個(gè)第一個(gè)只出現(xiàn)次數(shù)為1的字符
- return *str;
- str++;
- }
- return '\0' ;
- }
- int main()
- {
- char *str= "afaccde" ;
- cout<<find_first_unique_char(str)<<endl;
- return 0;
- }
- //查找第一個(gè)只出現(xiàn)一次的字符，第2個(gè)程序
- //copyright@yansha
- //July、updated，2011.04.24.
- char FirstNotRepeatChar( char *pString)
- {
- if (!pString)
- return '\0' ;
- const int tableSize=256;
- int hashTable[tableSize]={0}; //存入數(shù)組，并初始化為0
- char *pHashKey=pString;
- while (*(pHashKey)!= '\0' )
- hashTable[*(pHashKey++)]++;
- while (*pString!= '\0' )
- {
- if (hashTable[*pString]==1)
- return *pString;
- pString++;
- }
- return '\0' ; //沒(méi)有找到滿(mǎn)足條件的字符，退出
- }
第二十章、一致性哈希算法
tencent2012筆試題附加題
問(wèn)題描述： 例如手機(jī)朋友網(wǎng)有n個(gè)服務(wù)器，為了方便用戶(hù)的訪(fǎng)問(wèn)會(huì)在服務(wù)器上緩存數(shù)據(jù)，因此用戶(hù)每次訪(fǎng)問(wèn)的時(shí)候最好能保持同一臺(tái)服務(wù)器。
已有的做法是根據(jù)ServerIPIndex[QQNUM%n]得到請(qǐng)求的服務(wù)器，這種方法很方便將用戶(hù)分到不同的服務(wù)器上去。但是如果一臺(tái)服務(wù)器死掉了，那么n就變?yōu)榱薾-1，那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%（n-1）]基本上都不一樣了，所以大多數(shù)用戶(hù)的請(qǐng)求都會(huì)轉(zhuǎn)到其他服務(wù)器，這樣會(huì)發(fā)生大量訪(fǎng)問(wèn)錯(cuò)誤。
問(wèn)： 如何改進(jìn)或者換一種方法，使得：
（1）一臺(tái)服務(wù)器死掉后，不會(huì)造成大面積的訪(fǎng)問(wèn)錯(cuò)誤，
（2）原有的訪(fǎng)問(wèn)基本還是停留在同一臺(tái)服務(wù)器上；
（3）盡量考慮負(fù)載均衡。（
思路：往分布式一致哈希算法方面考慮。
）
-
最土的辦法還是用模余方法：做法很簡(jiǎn)單，假設(shè)有N臺(tái)服務(wù)器，現(xiàn)在完好的是M（M<=N),先用N求模，如果不落在完好的機(jī)器上，然后再用N-1求模，直到M.這種方式對(duì)于壞的機(jī)器不多的情況下，具有更好的穩(wěn)定性。
- 一致性哈希算法。
下面，本文剩下部分重點(diǎn)來(lái)講講這個(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ī)器。但這樣的算法方法存在致命問(wèn)題，如果某一臺(tái)機(jī)器宕機(jī)，那么應(yīng)該落在該機(jī)器的請(qǐng)求就無(wú)法得到正確的處理，這時(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算法，可以說(shuō)Consistent Hashing 是分布式系統(tǒng)負(fù)載均衡的首選算法。
Consistent Hashing算法描述
下面以Memcached中的Consisten Hashing算法為例說(shuō)明。
consistent hashing算法早在1997年就在論文 Consistent hashing and random trees 中被提出，目前在cache系統(tǒng)中應(yīng)用越來(lái)越廣泛；
1基本場(chǎng)景
比如你有N個(gè)cache服務(wù)器（后面簡(jiǎn)稱(chēng)cache），那么如何將一個(gè)對(duì)象object映射到N個(gè)cache上呢，你很可能會(huì)采用類(lèi)似下面的通用方法計(jì)算object的hash值，然后均勻的映射到到N個(gè)cache；
hash(object)%N
一切都運(yùn)行正常，再考慮如下的兩種情況；
- 一個(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)；
- 由于訪(fǎng)問(wèn)加重，需要添加cache，這時(shí)候cache是N+1臺(tái)，映射公式變成了hash(object)%(N+1)；
1和2意味著什么？這意味著突然之間幾乎所有的cache都失效了。對(duì)于服務(wù)器而言，這是一場(chǎng)災(zāi)難，洪水般的訪(fǎng)問(wèn)都會(huì)直接沖向后臺(tái)服務(wù)器；再來(lái)考慮第三個(gè)問(wèn)題，由于硬件能力越來(lái)越強(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)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。
容易看到，上面的簡(jiǎn)單hash算法hash(object)%N難以滿(mǎn)足單調(diào)性要求。
3 consistent hashing算法的原理
consistent hashing是一種hash算法，簡(jiǎn)單的說(shuō)，在移除/添加一個(gè)cache時(shí)，它能夠盡可能小的改變已存在key映射關(guān)系，盡可能的滿(mǎn)足單調(diào)性的要求。
下面就來(lái)按照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所示的那樣。
圖1環(huán)形hash空間
3.2把對(duì)象映射到hash空間
接下來(lái)考慮4個(gè)對(duì)象object1~object4，通過(guò)hash函數(shù)計(jì)算出的hash值key在環(huán)上的分布如圖2所示。
hash(object1) = key1;
… …
hash(object4) = key4;
圖2 4個(gè)對(duì)象的key值分布
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è)趆ash空間中，以對(duì)應(yīng)的hash值排列。
hash(cache A) = key A;
… …
hash(cache C) = key C;
圖3 cache和對(duì)象的key值分布
說(shuō)到這里，順便提一下cache的hash計(jì)算，一般的方法可以使用cache機(jī)器的IP地址或者機(jī)器名作為hash輸入。
3.4把對(duì)象映射到cache
現(xiàn)在cache和對(duì)象都已經(jīng)通過(guò)同一個(gè)hash算法映射到hash數(shù)值空間中了，接下來(lái)要考慮的就是如何將對(duì)象映射到cache上面了。
在這個(gè)環(huán)形空間中，如果沿著順時(shí)針?lè)较驈膶?duì)象的key值出發(fā)，直到遇見(jiàn)一個(gè)cache，那么就將該對(duì)象存儲(chǔ)在這個(gè)cache上，因?yàn)閷?duì)象和cache的hash值是固定的，因此這個(gè)cache必然是唯一和確定的。這樣不就找到了對(duì)象和cache的映射方法了嗎？！
依然繼續(xù)上面的例子（參見(jiàn)圖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)
前面講過(guò)，通過(guò)hash然后求余的方法帶來(lái)的最大問(wèn)題就在于不能滿(mǎn)足單調(diào)性，當(dāng)cache有所變動(dòng)時(shí)，cache會(huì)失效，進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊，現(xiàn)在就來(lái)分析分析consistent hashing算法。
3.5.1移除cache
考慮假設(shè)cache B掛掉了，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅是那些沿cache B逆時(shí)針遍歷直到下一個(gè)cache（cache C）之間的對(duì)象，也即是本來(lái)映射到cache B上的那些對(duì)象。
因此這里僅需要變動(dòng)對(duì)象object4，將其重新映射到cache C上即可；參見(jiàn)圖4。
圖4 Cache B被移除后的cache映射
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ì)象（它們是也本來(lái)映射到cache C上對(duì)象的一部分），將這些對(duì)象重新映射到cache D上即可。
因此這里僅需要變動(dòng)對(duì)象object2，將其重新映射到cache D上；參見(jiàn)圖5。
圖5添加cache D后的映射關(guān)系
4虛擬節(jié)點(diǎn)
考量Hash算法的另一個(gè)指標(biāo)是平衡性(Balance)，定義如下：
平衡性
平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
hash算法并不是保證絕對(duì)的平衡，如果cache較少的話(huà)，對(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值排列。
仍以?xún)H部署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è)一種比較理想的情況，參見(jiàn)圖6。
圖6引入“虛擬節(jié)點(diǎn)”后的映射關(guān)系
此時(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)換到了{(lán)對(duì)象->虛擬節(jié)點(diǎn)}。查詢(xún)物體所在cache時(shí)的映射關(guān)系如圖7所示。
圖7查詢(xún)對(duì)象所在cache
“虛擬節(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
后記
- 以上部分代碼思路有參考自此博客： http://zhedahht.blog.163.com/blog/ 。特此注明下。
-
上文第五部分來(lái)源：
http://blog.csdn.net/sparkliang/article/details/5279393
；
- 行文倉(cāng)促，若有任何問(wèn)題或漏洞，歡迎不吝指正或賜教。謝謝。轉(zhuǎn)載，請(qǐng)注明出處。完。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
