一致性哈希演算法php

1. 如何理解c/c++和php語言的區別

一、編程語言

1.根據熟悉的語言，談談兩種語言的區別？

主要淺談下C/C++和PHP語言的區別:

1)PHP弱類型語言，一種腳本語言，對數據的類型不要求過多，較多的應用於Web應用開發，現在好多互聯網開發公司的主流web後台開發語言，主要框架為mvc模型，如smarty,yaf，升級的PHP7速度較快，對伺服器的壓力要小很多，在新浪微博已經有應用，對比很明顯。

2)C/C++開發語言，C語言更偏向硬體底層開發，C++語言是目前為止我認為語法內容最多的一種語言。C/C++在執行速度上要快很多，畢竟其他類型的語言大都是C開發的，更多應用於網路編程和嵌入式編程。

2.volatile是幹啥用的，（必須將cpu的寄存器緩存機制回答得很透徹），使用實例有哪些？（重點）

1） 訪問寄存器比訪問內存單元要快,編譯器會優化減少內存的讀取，可能會讀臟數據。聲明變數為volatile，編譯器不再對訪問該變數的代碼優化，仍然從內存讀取，使訪問穩定。

總結：volatile關鍵詞影響編譯器編譯的結果，用volatile聲明的變數表示該變數隨時可能發生變化，與該變數有關的運算，不再編譯優化，以免出錯。

2）使用實例如下( 區分C程序員和嵌入式系統程序員的最基本的問題。 )：

並行設備的硬體寄存器（如：狀態寄存器）
一個中斷服務子程序中會訪問到的非自動變數(Non-automatic variables)
多線程應用中被幾個任務共享的變數
3)一個參數既可以是const還可以是volatile嗎？解釋為什麼。

可以。一個例子是只讀的狀態寄存器。它是volatile因為它可能被意想不到地改變。它是const因為程序不應該試圖去修改它。
4）一個指針可以是volatile 嗎？解釋為什麼。
可以。盡管這並不是很常見。一個例子當中斷服務子程序修改一個指向一個buffer的指針時。

下面的函數有什麼錯誤：
int square(volatile int *ptr) {
return *ptr * *ptr;
}
下面是答案：
這段代碼有點變態。這段代碼的目的是用來返指針*ptr指向值的平方，但是，由於*ptr指向一個volatile型參數，編譯器將產生類似下面的代碼：
int square(volatile int *ptr){
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由於*ptr的值可能被意想不到地改變，因此a和b可能是不同的。結果，這段代碼可能並不是你所期望的平方值！正確的代碼如下：
long square(volatile int *ptr){
int a;
a = *ptr;
return a * a;
}

更多linux內核視頻教程文本資料免費獲取後台私信【 內核 】。

3.static const等等的用法，（能說出越多越好）（重點）

² 首先說說const的用法（絕對不能說是常數）

1）在定義的時候必須進行初始化

2）指針可以是const 指針，也可以是指向const對象的指針

3）定義為const的形參，即在函數內部是不能被修改的

4）類的成員函數可以被聲明為正常成員函數，不能修改類的成員變數

5）類的成員函數可以返回的是常對象，即被const聲明的對象

6）類的成員變數是指成員變數不能在聲明時初始化，必須在構造函數的列表裡進行初始化

（註：千萬不要說const是個常數，會被認為是外行人的！！！！哪怕說個只讀也行）

下面的聲明都是什麼意思？
const int a; a是一個正常整型數
int const a; a是一個正常整型數
const int *a; a是一個指向常整型數的指針，整型數是不可修改的，但指針可以
int * const a; a為指向整型數的常指針，指針指向的整型數可以修改，但指針是不可修改的
int const * a const; a是一個指向常整型數的常指針，指針指向的整型數是不可修改的，同時指針也是不可修改的
通過給優化器一些附加的信息，使用關鍵字const也許能產生更緊湊的代碼。合理地使用關鍵字const可以使編譯器很自然地保護那些不希望被改變的參數，防止其被無意的代碼修改。簡而言之，這樣可以減少bug的出現。

Const如何做到只讀？

這些在編譯期間完成，對於內置類型，如int， 編譯器可能使用常數直接替換掉對此變數的引用。而對於結構體不一定。

² 再說說static的用法（三個明顯的作用一定要答出來）

1）在函數體內，一個被聲明為靜態的變數在這一函數被調用過程中維持其值不變。
2）在模塊內（但在函數體外），一個被聲明為靜態的變數可以被模塊內所用函數訪問，但不能被模塊外其它函數訪問。它是一個本地的全局變數。
3）在模塊內，一個被聲明為靜態的函數只可被這一模塊內的其它函數調用。那就是，這個函數被限制在聲明它的模塊的本地范圍內使用

4）類內的static成員變數屬於整個類所擁有，不能在類內進行定義，只能在類的作用域內進行定義

5）類內的static成員函數屬於整個類所擁有，不能包含this指針，只能調用static成員函數

static全局變數與普通的全局變數有什麼區別?static局部變數和普通局部變數有什麼區別?static函數與普通函數有什麼區別?

static全局變數與普通的全局變數有什麼區別：static全局變數只初始化一次，防止在其他文件單元中被引用;
static局部變數和普通局部變數有什麼區別：static局部變數只被初始化一次，下一次依據上一次結果值；
static函數與普通函數有什麼區別：static函數在內存中只有一份，普通函數在每個被調用中維持一份拷貝

4.extern c 作用

告訴編譯器該段代碼以C語言進行編譯。

5.指針和引用的區別

1）引用是直接訪問，指針是間接訪問。

2）引用是變數的別名，本身不單獨分配自己的內存空間，而指針有自己的內存空間

3）引用綁定內存空間（必須賦初值），是一個變數別名不能更改綁定，可以改變對象的值。

總的來說：引用既具有指針的效率，又具有變數使用的方便性和直觀性

6. 關於靜態內存分配和動態內存分配的區別及過程

1) 靜態內存分配是在編譯時完成的，不佔用CPU資源；動態分配內存運行時完成，分配與釋放需要佔用CPU資源；

2)靜態內存分配是在棧上分配的，動態內存是堆上分配的；

3)動態內存分配需要指針或引用數據類型的支持，而靜態內存分配不需要；

4)靜態內存分配是按計劃分配，在編譯前確定內存塊的大小，動態內存分配運行時按需分配。

5)靜態分配內存是把內存的控制權交給了編譯器，動態內存把內存的控制權交給了程序員；

6)靜態分配內存的運行效率要比動態分配內存的效率要高，因為動態內存分配與釋放需要額外的開銷；動態內存管理水平嚴重依賴於程序員的水平，處理不當容易造成內存泄漏。

7. 頭文件中的 ifndef/define/endif 干什麼用 ？

預處理，防止頭文件被重復使用，包括pragma once都是這樣的

8. 宏定義求兩個元素的最小值

#define MIN(A,B) （（A） next;

}

else

{

return NULL;

}

}

Node* pFind = pHead;

while (pCurrent) {

pFind = pFind->next;

pCurrent = pCurrent->next;

}

return pFind;

}

2. 給定一個單向鏈表（長度未知），請遍歷一次就找到中間的指針，假設該鏈表存儲在只讀存儲器，不能被修改

設置兩個指針，一個每次移動兩個位置，一個每次移動一個位置，當第一個指針到達尾節點時，第二個指針就達到了中間節點的位置

處理鏈表問題時，」快行指針「是一種很常見的技巧，快行指針指的是同時用兩個指針來迭代訪問鏈表，只不過其中一個比另一個超前一些。快指針往往先行幾步，或與慢指針相差固定的步數。

node *create() {

node *p1, *p2, *head;

int cycle = 1, x;

head = (node*)malloc(sizeof(node));

p1 = head;

while (cycle)

{

cout > x;

if (x != 0)

{

p2 = (node*)malloc(sizeof(node));

p2->data = x;

p1->next = p2;

p1 = p2;

}

else

{

cycle = 0;

}

}

head = head->next;

p1->next = NULL;

return head;

}

void findmid(node* head) {

node *p1, *p2, *mid;

p1 = head;

p2 = head;

while (p1->next->next != NULL)

{

p1 = p1->next->next;

p2 = p2->next;

mid = p2;

}

}

3. 將一個數組生成二叉排序樹

排序，選數組中間的一個元素作為根節點，左邊的元素構造左子樹，右邊的節點構造有子樹。

4. 查找數組中第k大的數字？

因為快排每次將數組劃分為兩組加一個樞紐元素，每一趟劃分你只需要將k與樞紐元素的下標進行比較，如果比樞紐元素下標大就從右邊的子數組中找，如果比樞紐元素下標小從左邊的子數組中找，如果一樣則就是樞紐元素，找到，如果需要從左邊或者右邊的子數組中再查找的話，只需要遞歸一邊查找即可，無需像快排一樣兩邊都需要遞歸，所以復雜度必然降低。

最差情況如下：假設快排每次都平均劃分，但是都不在樞紐元素上找到第k大第一趟快排沒找到，時間復雜度為O(n)，第二趟也沒找到，時間復雜度為O(n/2)，第k趟找到，時間復雜度為O(n/2k)，所以總的時間復雜度為O(n(1+1/2+....+1/2k))=O(n)，明顯比冒泡快，雖然遞歸深度是一樣的，但是每一趟時間復雜度降低。

5. 紅黑樹的定義和解釋？B樹的基本性質？

紅黑樹：

性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3. 每個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵），如果一個結點n的只有一個左孩子，那麼n的右孩子是一個黑哨兵；如果結點n只有一個右孩子，那麼n的左孩子是一個黑哨兵。
性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

B樹：

1.所有非葉子結點至多擁有兩個兒子（Left和Right）；

2.所有結點存儲一個關鍵字；

3.非葉子結點的左指針指向小於其關鍵字的子樹，右指針指向大於其關鍵字的子樹；

6. 常見的加密演算法？

對稱式加密就是加密和解密使用同一個密鑰。
非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為「公鑰」和「私鑰」，它們兩個必需配對使用。
DES：對稱演算法，數據加密標准，速度較快，適用於加密大量數據的場合；
MD5的典型應用是對一段Message產生fingerprint(指紋)，以防止被「篡改」。
RSA是第一個既能用於數據加密也能用於數字簽名的演算法。

7. https?

HTTP下加入SSL層，HTTPS的安全基礎是SSL。

8.有一個IP庫，給你一個IP,如何能夠快速的從中查找到對應的IP段？不用資料庫如何實現？要求省空間
9.簡述一致性hash演算法。

1）首先求memcached伺服器（節點）的哈希值，並將其配置到0 232的圓（continuum）。

2）然後採用同樣的方法求出存儲數據的鍵的哈希值，並映射到相同的圓上。

3）然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器上。如果超過232仍然找不到伺服器，就會保存到第一台memcached伺服器上。
11.描述一種hash table的實現方法

1） 除法散列法: p ，令 h(k ) = k mod p ，這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。最直觀的一種，上圖使用的就是這種散列法，公式： index = value % 16，求模數其實是通過一個除法運算得到的。

2） 平方散列法 :求index頻繁的操作，而乘法的運算要比除法來得省時。公式： index = (value * value) >> 28 （右移，除以2^28。記法：左移變大，是乘。右移變小，是除）

3） 數字選擇法:如果關鍵字的位數比較多，超過長整型範圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。

4） 斐波那契（Fibonacci）散列法:平方散列法的缺點是顯而易見的，通過找到一個理想的乘數index = (value * 2654435769) >> 28

沖突處理：令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。

12、各類樹結構的實現和應用

13、hash，任何一個技術面試官必問（例如為什麼一般hashtable的桶數會取一個素數？如何有效避免hash結果值的碰撞）

不選素數的話可能會造成hash出值的范圍和原定義的不一致

14.什麼是平衡二叉樹?

左右子樹都是平衡二叉樹，而且左右子樹的深度差值的約對值不大於1。

15．數組和鏈表的優缺點

數組，在內存上給出了連續的空間。鏈表，內存地址上可以是不連續的，每個鏈表的節點包括原來的內存和下一個節點的信息(單向的一個，雙向鏈表的話，會有兩個)。

數組優於鏈表的:

A. 內存空間佔用的少。

B. 數組內的數據可隨機訪問，但鏈表不具備隨機訪問性。

C. 查找速度快

鏈表優於數組的:

A. 插入與刪除的操作方便。

B. 內存地址的利用率方面鏈表好。

C. 方便內存地址擴展。

17.最小堆插入，刪除編程實現

18. 4G的long型整數中找到一個最大的，如何做？

每次從磁碟上盡量多讀一些數到內存區，然後處理完之後再讀入一批。減少IO次數，自然能夠提高效率。分批讀入選取最大數，再對緩存的最大數進行快排。

19. 有千萬個string在內存怎麼高速查找，插入和刪除？

對千萬個string做hash，可以實現高速查找，找到了，插入和刪除就很方便了。關鍵是如何做hash，對string做hash，要減少碰撞頻率。

在內存中維護一個大小為10000的最小堆，每次從文件讀一個數，與最小堆的堆頂元素比較，若比堆頂元素大，則替換掉堆頂元素，然後調整堆。最後剩下的堆內元素即為最大的1萬個數，演算法復雜度為O(NlogN)

（1）全局洗牌法

a）首先生成一個數組，大小為54，初始化為1~54

b）按照索引1到54，逐步對每一張索引牌進行洗牌，首先生成一個余數 value = rand %54，那麼我們的索引牌就和這個余數牌進行交換處理

c）等多索引到54結束後，一副牌就洗好了

（2）局部洗牌法：索引牌從1開始，到54結束。這一次索引牌只和剩下還沒有洗的牌進行交換， value = index + rand（） %（54 - index）

演算法復雜度是O(n)

22．請分別用遞歸和非遞歸方法，先序遍歷二叉樹

24.其他各種排序方法

25.哈希表沖突解決方法？

常見的hash演算法如下：

解決沖突的方法：

也叫散列法，主要思想是當出現沖突的時候，以關鍵字的結果值作為key值輸入，再進行處理，依次直到沖突解決

線性地址再散列法

當沖突發生時，找到一個空的單元或者全表

二次探測再散列

沖突發生時，在表的左右兩側做跳躍式的探測

偽隨機探測再散列

同時構造不同的哈希函數

將同樣的哈希地址構造成一個同義詞的鏈表

建立一個基本表和溢出區，凡是和基本元素發生沖突都填入溢出區

六、系統架構

1.設計一個服務，提供遞增的SessionID服務，要求保證服務的高可靠性，有哪些方案？集中式/非集中式/分布式

2.多台伺服器要執行計劃任務，但只有拿到鎖的任務才能執行，有一個中心伺服器來負責分配鎖，但要保證服務的高可靠性。

3.如何有效的判斷伺服器是否存活？伺服器是否踢出集群的決策如何產生？

4.兩個伺服器如何在同一時刻獲取同一數據的時候保證只有一個伺服器能訪問到數據？

可以採用隊列進行處理，寫一個隊列介面保證同一時間只有一個進程能夠訪問到數據，或者對於存取資料庫的來說，資料庫也是可以加鎖處理的

5. 編寫高效伺服器程序，需要考慮的因素

性能對伺服器程序來說是至關重要的了，畢竟每個客戶都期望自己的請求能夠快速的得到響應並處理。那麼影響伺服器性能的首要因素應該是：

（1）系統的硬體資源，比如說CPU個數，速度，內存大小等。不過由於硬體技術的飛速發展，現代伺服器都不缺乏硬體資源。因此，需要考慮的主要問題是如何從「軟環境」來提升伺服器的性能。

伺服器的」軟環境「

（2）一方面是指系統的軟體資源，比如操作系統允許用戶打開的最大文件描述符數量

（3）另一方面指的就是伺服器程序本身，即如何從編程的角度來確保伺服器的性能。

主要就要考慮大量並發的處理這涉及到使用進程池或線程池實現高效的並發模式（半同步/半非同步和領導者/追隨者模式），以及高效的邏輯處理方式--有限狀態機內存的規劃使用比如使用內存池，以空間換時間，被事先創建好，避免動態分配，減少了伺服器對內核的訪問頻率，數據的復制，伺服器程序還應該避免不必要的數據復制，尤其是當數據復制發生在用戶空間和內核空間之間時。如果內核可以直接處理從socket或者文件讀入的數據，則應用程序就沒必要將這些數據從內核緩沖區拷貝到應用程序緩沖區中。這里所謂的「直接處理」，是指應用程序不關心這些數據的具體內容是什麼，不需要對它們作任何分析。比如說ftp伺服器，當客戶請求一個文件時，伺服器只需要檢測目標文件是否存在，以及是否有許可權讀取就可以了，不需要知道這個文件的具體內容，這樣的話ftp伺服器就不需要把目標文件讀入應用程序緩沖區然後調用send函數來發送，而是直接使用「零拷貝」函數sendfile直接將其發送給客戶端。另外，用戶代碼空間的數據賦值也應該盡可能的避免復制。當兩個工作進程之間需要傳遞大量的數據時，我們就應該考慮使用共享內存來在他們直接直接共享這些數據，而不是使用管道或者消息隊列來傳遞。上下文切換和鎖：並發程序必須考慮上下文的切換問題，即進程切換或線程切換所導致的系統開銷。即時I/O密集型伺服器也不應該使用過多的工作線程（或工作進程），否則進程間切換將佔用大量的CPU時間，伺服器真正處理業務邏輯的CPU時間比重就下降了。因此為每個客戶連接都創建一個工作線程是不可取的。應該使用某種高效的並發模式。（半同步半非同步或者說領導者追隨者模式）另一個問題就是共享資源的加鎖保護。鎖通常被認為是導致伺服器效率低下的一個因素，因為由他引入的代碼不僅不處理業務邏輯，而且需要訪問內核資源，因此如果伺服器有更好的解決方案，應該盡量避免使用鎖。或者說伺服器一定非要使用鎖的話，盡量使用細粒度的鎖，比如讀寫鎖，當工作線程都只讀一塊內存區域時，讀寫鎖不會增加系統開銷，而只有當需要寫時才真正需要鎖住這塊內存區域。對於高峰和低峰的伸縮處理，適度的緩存。

6. QQ飛車新用戶注冊時，如何判斷新注冊名字是否已存在？（數量級：幾億)

可以試下先將用戶名通過編碼方式轉換，如轉換64位整型。然後設置N個區間，每個區間為2^64/N的大小。對於新的用戶名，先通過2分尋找該用戶名屬於哪個區間，然後在在這個區間，做一個hash。對於不同的時間復雜度和內存要求可以設置不同N的大小~

加一些基礎的技術面試之外的職業素養的面試問題

1.你在工作中犯了個錯誤，有同事打你小報告，你如何處理？

a.同事之間應該培養和形成良好的同事關系，就是要互相支持而不是互相拆台，互相學習，互相幫助，共同進步。

b.如果小報告里邊的事情都是事實也就是說確實是本人做的不好不對的方面，那麼自己應該有則改之，提高自己。如果小報告里邊的事

情全部不是事實，就是說確實誣陷，那麼應該首先堅持日久見人心的態度，持之以恆的把本職工作做好，然後在必要的時候通過適當的

方式和領導溝通，相信領導會知道的。

2.你和同事合作完成一個任務，結果任務錯過了截止日期，你如何處理？

3.職業規劃？

4.離職原因？

5. 項目中遇到的難題，你是如何解決的?

A．時間 b要求 c.方法

2. 演算法簡述：一致性hash環，與redis 槽道原理

1.哈希演算法 對伺服器個數進行模餘存儲，

（下圖）

傳統新增節點 （下圖）

2、哈希環，應用於數據的分布式存儲，在增刪節點之間，能夠盡可能少的遷移數據，保證多數數據的一致性。（下圖）每個節點代表一個數據存儲伺服器。伺服器在通過哈希演算法過後，得到一個固定長度數值a, 由a/65535 模余 得0~65535之間正整數，散列分布在hash環上（下圖）

藍色代表數據，綠色代表數據存儲庫，每個數據存儲庫 管理順時針 ，上個節點之間的區域。（下圖）圖中數字 因該是對65536取余數

在新增節點4  後，只有數據a需要遷移（下圖）

3，槽道原理，綜上所述 ，哈希環減少了 數據在存儲節點增刪 過程中對數據產生的影響。redis 提出的hash槽道，則讓數據遷移變得更為靈活

3. php的memcached分布式hash演算法,如何解決分布不均crc32這個演算法沒辦法把key值均勻的分布出去

memcached的總結和分布式一致性hash
當前很多大型的web系統為了減輕資料庫伺服器負載，會採用memchached作為緩存系統以提高響應速度。
目錄： （http://hounwang.com/lesson.html）
memchached簡介
hash
取模
一致性hash
虛擬節點
源碼解析
參考資料
1. memchached簡介
memcached是一個開源的高性能分布式內存對象緩存系統。
其實思想還是比較簡單的，實現包括server端（memcached開源項目一般只單指server端）和client端兩部分:
server端本質是一個in-memory key-value store，通過在內存中維護一個大的hashmap用來存儲小塊的任意數據，對外通過統一的簡單介面（memcached protocol）來提供操作。
client端是一個library，負責處理memcached protocol的網路通信細節，與memcached server通信，針對各種語言的不同實現分裝了易用的API實現了與不同語言平台的集成。
web系統則通過client庫來使用memcached進行對象緩存。
2. hash
memcached的分布式主要體現在client端，對於server端，僅僅是部署多個memcached server組成集群，每個server獨自維護自己的數據（互相之間沒有任何通信），通過daemon監聽埠等待client端的請求。
而在client端，通過一致的hash演算法，將要存儲的數據分布到某個特定的server上進行存儲，後續讀取查詢使用同樣的hash演算法即可定位。
client端可以採用各種hash演算法來定位server：
取模
最簡單的hash演算法
targetServer = serverList[hash(key) % serverList.size]
直接用key的hash值（計算key的hash值的方法可以自由選擇，比如演算法CRC32、MD5,甚至本地hash系統，如java的hashcode）模上server總數來定位目標server。這種演算法不僅簡單，而且具有不錯的隨機分布特性。
但是問題也很明顯，server總數不能輕易變化。因為如果增加/減少memcached server的數量，對原先存儲的所有key的後續查詢都將定位到別的server上，導致所有的cache都不能被命中而失效。
一致性hash
為了解決這個問題，需要採用一致性hash演算法（consistent hash）
相對於取模的演算法，一致性hash演算法除了計算key的hash值外，還會計算每個server對應的hash值，然後將這些hash值映射到一個有限的值域上（比如0~2^32）。通過尋找hash值大於hash(key)的最小server作為存儲該key數據的目標server。如果找不到，則直接把具有最小hash值的server作為目標server。
為了方便理解，可以把這個有限值域理解成一個環，值順時針遞增。
如上圖所示，集群中一共有5個memcached server，已通過server的hash值分布到環中。
如果現在有一個寫入cache的請求，首先計算x=hash(key)，映射到環中，然後從x順時針查找，把找到的第一個server作為目標server來存儲cache，如果超過了2^32仍然找不到，則命中第一個server。比如x的值介於A~B之間，那麼命中的server節點應該是B節點
可以看到，通過這種演算法，對於同一個key，存儲和後續的查詢都會定位到同一個memcached server上。
那麼它是怎麼解決增/刪server導致的cache不能命中的問題呢？
假設，現在增加一個server F，如下圖
此時，cache不能命中的問題仍然存在，但是只存在於B~F之間的位置（由C變成了F），其他位置（包括F~C）的cache的命中不受影響（刪除server的情況類似）。盡管仍然有cache不能命中的存在，但是相對於取模的方式已經大幅減少了不能命中的cache數量。
虛擬節點
但是，這種演算法相對於取模方式也有一個缺陷：當server數量很少時，很可能他們在環中的分布不是特別均勻，進而導致cache不能均勻分布到所有的server上。
如圖，一共有3台server – 1，2，4。命中4的幾率遠遠高於1和2。
為解決這個問題，需要使用虛擬節點的思想：為每個物理節點（server）在環上分配100～200個點，這樣環上的節點較多，就能抑制分布不均勻。
當為cache定位目標server時，如果定位到虛擬節點上，就表示cache真正的存儲位置是在該虛擬節點代表的實際物理server上。
另外，如果每個實際server的負載能力不同，可以賦予不同的權重，根據權重分配不同數量的虛擬節點。
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 用MD5來計算key的hash值
MessageDigest md5 = MD5.get();
md5.reset();
md5.update( key.getBytes() );
byte[] bKey = md5.digest();

// 取MD5值的低32位作為key的hash值
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);

// hv的tailMap的第一個虛擬節點對應的即是目標server
SortedMap tmap = this.consistentBuckets.tailMap( hv );
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();
更多問題到問題求助專區（http://bbs.hounwang.com/）

4. 一致性哈希演算法怎麼保證數據的一致性

環割法（一致性 hash）環割法的原理如下：

1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字元串的所有 hash 值。

2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。

3. 輸入字元串的時候計算輸入字元串的 hash 值，查看 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為數據的分片。

數據比較

下面將通過測試對環割法和跳躍法的性能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。

• 數據源：現場數據 350595 條

• 測試經過：

  1. 通過各自的測試方法執行對於測試數據的分片任務。

  2. 測試方法：記錄分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。

  3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。

5. 一致性hash演算法是什麼

一致性哈希演算法是在1997年由麻省理工學院提出的一種分布式哈希（DHT）演算法。其設計目標是為了解決網際網路中的熱點（Hot spot)問題，初衷和CARP十分類似。

一致性Hash是一種特殊的Hash演算法，由於其均衡性、持久性的映射特點，被廣泛的應用於負載均衡領域，如nginx和memcached都採用了一致性Hash來作為集群負載均衡的方案。

一致性哈希演算法的目標是，當K個請求key發起請求時。後台增減節點，只會引起K/N的key發生重新映射。即一致性哈希演算法，在後台節點穩定時，同一key的每次請求映射到的節點是一樣的。而當後台節點增減時，該演算法盡量將K個key映射到與之前相同的節點上。

構成哈希演算法的條件：

從哈希值不能反向推導出原始數據（所以哈希演算法也叫單向哈希演算法）。

對輸入數據非常敏感，哪怕原始數據只修改了一個 Bit，最後得到的哈希值也大不相同。

散列沖突的概率要很小，對於不同的原始數據，哈希值相同的概率非常小。

哈希演算法的執行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。

6. 哈希表、哈希演算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。

  優點：

        哈希表可以提供快速的操作。

缺點：

        哈希表通常是基於數組的，數組創建後難於擴展。

        也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。

    綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。

        1. 使用哈希函數將被查找的鍵轉換為數組的索引。

        2. 處理哈希碰撞沖突。

    若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。

    若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。

散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。

一個好的散列函數一般應該考慮下列因素 ：

    1.計算簡單，以便提高轉換速度。

    2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。

1.   直接定址法

    取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。

2.   數字分析法

    數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。

3.   平方取中法

    取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。

4.   折疊法

    折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。

    數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。

    該方法適用於關鍵字特別多的情況。

5.   隨機數法

    選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。

6.   除留余數法

    取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。

    對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。

    通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。

下面以創建哈希表為例，說明解決沖突的方法。

1.開放定址法

    這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：

    (1) 線性探測再散列

        di=1，2，3，…，m-1

        這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。

    (2)二次探測再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

    (3)偽隨機探測再散列

        di=偽隨機數序列。

    線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。

    其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）

2.再哈希法

    這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。

    當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

 3.鏈地址法(拉鏈法)

    這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。

     拉鏈法的優點

        與開放定址法相比，拉鏈法有如下幾個優點：

            (1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；

            (2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；

            (3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）

註：HashMap默認裝填因子是0.75。

            (4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

     拉鏈法的缺點

        拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，此時將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

4、建立公共溢出區

    這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。

    散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

    查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。

影響產生沖突多少有以下三個因素:

    1. 散列函數是否均勻;

    2. 處理沖突的方法;

    3. 散列表的裝填因子。

     散列表的裝填因子

        定義為:α= 填入表中的元素個數 / 散列表的長度

        α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。

        實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。

    這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。

Hash演算法在信息安全方面的應用主要體現在以下的3個方面:

     ⑴  文件校驗

        我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。

        MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。

     ⑵  數字簽名

        Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。

     ⑶ 鑒權協議

        如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

    一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。

判定哈希演算法好壞的四個定義 ：

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

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

    3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。

    4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。

    在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。

以SpyMemcached的ketama演算法來說，思路是這樣的：

把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。

如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：

這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。

為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。