https://blog.csdn.net/lihao21/article/details/54193868
https://blog.csdn.net/sparkliang/article/details/5279393 這個大神講得超級詳細，可以搞定和一緻性hash相關的一切問題。
引入
在業務開發中，我們常把資料持久化到資料庫中。如果需要讀取這些資料，除了直接從資料庫中讀取外，為了減輕資料庫的通路壓力以及提高通路速度，我們更多地引入緩存來對資料進行存取。讀取資料的過程一般為：
圖1：加入緩存的資料讀取過程
對于分布式緩存，不同機器上存儲不同對象的資料。為了實作這些緩存機器的負載均衡，可以使用式子1來定位對象緩存的存儲機器：
m = hash(o) mod n ——式子1
其中，
o
為對象的名稱，
n
為機器的數量，
m
為機器的編号，
hash
為一hash函數。圖2中的負載均衡器（load balancer）正是使用式子1來将用戶端對不同對象的請求分派到不同的機器上執行，例如，對于對象o，經過式子1的計算，得到
m
的值為3，那麼所有對對象o的讀取和存儲的請求都被發往機器3執行。
圖2：如何利用Hash取模實作負載均衡
式子1在大部分時候都可以工作得很好，然而，當機器需要擴容或者機器出現當機的情況下，事情就比較棘手了。
當機器擴容，需要增加一台緩存機器時，負載均衡器使用的式子變成：
m = hash(o) mod (n + 1) ——式子2
當機器當機，機器數量減少一台時，負載均衡器使用的式子變成：
m = hash(o) mod (n - 1) ——式子3
我們以機器擴容的情況為例，說明簡單的取模方法會導緻什麼問題。假設機器由3台變成4台，對象o1由式子1計算得到的m值為2，由式子2計算得到的m值卻可能為0，1，2，3（一個 3t + 2的整數對4取模，其值可能為0，1，2，3，讀者可以自行驗證），大約有75%（3/4)的可能性出現緩存通路不命中的現象。随着機器叢集規模的擴大，這個比例線性上升。當99台機器再加入1台機器時，不命中的機率是99%（99/100）。這樣的結果顯然是不能接受的，因為這會導緻資料庫通路的壓力陡增，嚴重情況，還可能導緻資料庫當機。
一緻性hash算法正是為了解決此類問題的方法，它可以保證當機器增加或者減少時，對緩存通路命中的機率影響減至很小。下面我們來詳細說一下一緻性hash算法的具體過程。
一緻性Hash環
一緻性hash算法通過一個叫作一緻性hash環的資料結構實作。這個環的起點是0，終點是2^32 - 1，并且起點與終點連接配接，環的中間的整數按逆時針分布，故這個環的整數分布範圍是[0, 2^32-1]，如下圖3所示：
圖3：一緻性Hash環
将對象放置到Hash環
假設現在我們有4個對象，分别為o1，o2，o3，o4，使用hash函數計算這4個對象的hash值（範圍為0 ~ 2^32-1）:
hash(o1) = m1
hash(o2) = m2
hash(o3) = m3
hash(o4) = m4
把m1，m2，m3，m4這4個值放置到hash環上，得到如下圖4：
圖4：放置了對象的一緻性Hash環
将機器放置到Hash環
使用同樣的hash函數，我們将機器也放置到hash環上。假設我們有三台緩存機器，分别為 c1，c2，c3，使用hash函數計算這3台機器的hash值：
hash(c1) = t1
hash(c2) = t2
hash(c3) = t3
把t1，t2，t3 這3個值放置到hash環上，得到如下圖5：
圖5：放置了機器的一緻性Hash環
為對象選擇機器
将對象和機器都放置到同一個hash環後，在hash環上順時針查找距離這個對象的hash值最近的機器，即是這個對象所屬的機器。
例如，對于對象o2，順序針找到最近的機器是c1，故機器c1會緩存對象o2。而機器c2則緩存o3，o4，機器c3則緩存對象o1。
圖6：在一緻性Hash環上為對象選擇機器
處理機器增減的情況
對于線上的業務，增加或者減少一台機器的部署是常有的事情。
例如，增加機器c4的部署并将機器c4加入到hash環的機器c3與c2之間。這時，隻有機器c3與c4之間的對象需要重新配置設定新的機器。對于我們的例子，隻有對象o4被重新配置設定到了c4，其他對象仍在原有機器上。如圖7所示：
圖7：增加機器後的一緻性Hash環的結構
如上文前面所述，使用簡單的求模方法，當新添加機器後會導緻大部分緩存失效的情況，使用一緻性hash算法後這種情況則會得到大大的改善。前面提到3台機器變成4台機器後，緩存命中率隻有25%（不命中率75%）。而使用一緻性hash算法，理想情況下緩存命中率則有75%，而且，随着機器規模的增加，命中率會進一步提高，99台機器增加一台後，命中率達到99%，這大大減輕了增加緩存機器帶來的資料庫通路的壓力。
再例如，将機器c1下線（當然，也有可能是機器c1當機），這時，隻有原有被配置設定到機器c1對象需要被重新配置設定到新的機器。對于我們的例子，隻有對象o2被重新配置設定到機器c3，其他對象仍在原有機器上。如圖8所示：
圖8：減少機器後的一緻性Hash環的結構
虛拟節點
上面提到的過程基本上就是一緻性hash的基本原理了，不過還有一個小小的問題。新加入的機器c4隻分擔了機器c2的負載，機器c1與c3的負載并沒有因為機器c4的加入而減少負載壓力。如果4台機器的性能是一樣的，那麼這種結果并不是我們想要的。
為此，我們引入虛拟節點來解決負載不均衡的問題。
将每台實體機器虛拟為一組虛拟機器，将虛拟機器放置到hash環上，如果需要确定對象的機器，先确定對象的虛拟機器，再由虛拟機器确定實體機器。
說得有點複雜，其實過程也很簡單。
還是使用上面的例子，假如開始時存在緩存機器c1，c2，c3，對于每個緩存機器，都有3個虛拟節點對應，其一緻性hash環結構如圖9所示：
圖9：機器c1，c2，c3的一緻性Hash環結構
假設對于對象o1，其對應的虛拟節點為c11，而虛拟節點c11對象緩存機器c1，故對象o1被配置設定到機器c1中。
新加入緩存機器c4，其對應的虛拟節點為c41，c42，c43，将這三個虛拟節點添加到hash環中，得到的hash環結構如圖10所示：
圖10：機器c1，c2，c3，c4的一緻性Hash環結構
新加入的緩存機器c4對應一組虛拟節點c41，c42，c43，加入到hash環後，影響的虛拟節點包括c31，c22，c11（順時針查找到第一個節點），而這3個虛拟節點分别對應機器c3，c2，c1。即新加入的一台機器，同時影響到原有的3台機器。理想情況下，新加入的機器平等地分擔了原有機器的負載，這正是虛拟節點帶來的好處。而且新加入機器c4後，隻影響25%（1/4）對象配置設定，也就是說，命中率仍然有75%，這跟沒有使用虛拟節點的一緻性hash算法得到的結果是相同的。
總結
一緻性hash算法解決了分布式環境下機器增加或者減少時，簡單的取模運算無法擷取較高命中率的問題。通過虛拟節點的使用，一緻性hash算法可以均勻分擔機器的負載，使得這一算法更具現實的意義。正因如此，一緻性hash算法被廣泛應用于分布式系統中。
參考資料
- https://en.wikipedia.org/wiki/Consistent_hashing
- https://www.codeproject.com/articles/56138/consistent-hashing
- 《大型網站技術架構——核心原理與安全分析》，李智慧著，電子工業出版社
例題
海量資料處理
海量資料處理政策之一—Hash映射 + Hash_map統計 + 堆/快速/歸并排序。
所謂海量資料處理，就是基于海量資料的查找、統計、運算等操作。所謂海量資料，就是資料量太大，導緻要麼無法在較短時間内迅速解決，要麼資料太大，導緻無法一次性裝入記憶體。進而導緻傳統的操作無法實作。
一、問題描述
海量日志資料，提取出某日通路百度次數最多的那個IP。
思路：由于資料集很大，我們的政策是先用哈希映射将海量資料集映射為适當數量的非海量資料集，這個非海量資料集的大小足夠我們的計算機吃下。然後我們可用hash_map去對資料進行統計，最後根據統計資料采用堆/快速/歸并排序等方式找出最值。
1.在這裡步驟一即哈希映射是将海量資料的大檔案分割成小檔案，因為記憶體受限，計算機一口吃不下。
2.利用hash_map去對劃分後的小檔案進行頻率統計.
3.統計完成後在利用排序算法找出通路頻率最大值的IP
具體實作：理論上的2的32次方個IP，我們可以采用哈希映射的方法，比如将IP換成整數去對1000取模，取模的值将會落在集合[0…999]中，每個值對應着一個集合，于是将由1000個集合，我們把取模後得到這個值的IP追加劃分到該集合中去。接下來就是對每個小IP集合檔案利用hash_map進行頻率統計，利用排序算法找出各個檔案中的最大值，最後對這些所謂的最大值再找出真正的最大值。
二、為什麼要用哈希映射
為了能在有限的計算機記憶體資源下處理海量大資料，我們必須通過某種機制将大檔案映射為小檔案，這種機制就是散列，他通常将資料均勻地散列到各個子檔案中去，這種映射散列的方式叫做哈希函數，好的哈希函數通常還能将資料均勻分布減少沖突。
三、題目
題目：每一個ip通路百度，其ip位址都會被記錄到背景日志檔案中，假設一天的通路日志有100G，求出一天中通路百度次數最多的ip位址，可以使用的記憶體大小是1G。
首先，我們将檔案分解成小檔案，題目說可使用大小我們不能就恰恰分成100個檔案，因為計算機上還有運作程式或存儲其他必要的資源，為了友善計算，我們将資料分成大小為100M一個的檔案，這樣即分成1024個檔案：[FILE 0……FILE1023]，100M大小我們說是這麼說，但實際上并不會很均勻，一個好的哈希函數會大概将資料均分配置設定到各個子檔案中去。于是這樣就解決了因為計算機記憶體有些而資料海量不能一次性讀入計算機的問題。
然後，我們對小檔案中的IP利用hash_map進行統計，求出每個檔案中IP出現次數最大的值。
最後，對這1024個子檔案中的IP出現次數最多的再來一輪IP次數出現最多的求法，即可求得整個海量資料下出現次數最多的IP。
第一部分、十道海量資料處理面試題
1、海量日志資料，提取出某日通路百度次數最多的那個IP。
首先是這一天，并且是通路百度的日志中的IP取出來，逐個寫入到一個大檔案中。注意到IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大檔案映射為1000個小檔案，再找出每個小文中出現頻率最大的IP（可以采用hash_map進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。然後再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。
或者如下闡述（雪域之鷹）：
算法思想：分而治之+Hash
1.IP位址最多有2^32=4G種取值情況，是以不能完全加載到記憶體中處理；
2.可以考慮采用“分而治之”的思想，按照IP位址的Hash(IP)24值，把海量IP日志分别存儲到1024個小檔案中。這樣，每個小檔案最多包含4MB個IP位址；
3.對于每一個小檔案，可以建構一個IP為key，出現次數為value的Hash map，同時記錄目前出現次數最多的那個IP位址；
4.可以得到1024個小檔案中的出現次數最多的IP，再依據正常的排序算法得到總體上出現次數最多的IP；
2、搜尋引擎會通過日志檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。
假設目前有一千萬個記錄（這些查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就是越熱門。），請你統計最熱門的10個查詢串，要求使用的記憶體不能超過1G。
典型的Top K算法，還是在這篇文章裡頭有所闡述，詳情請參見：十一、從頭到尾徹底解析Hash表算法。
文中，給出的最終算法是：
第一步、先對這批海量資料預處理，在O（N）的時間内用Hash表完成統計（之前寫成了排序，特此訂正。July、2011.04.27）；
第二步、借助堆這個資料結構，找出Top K，時間複雜度為N‘logK。
即，借助堆結構，我們可以在log量級的時間内查找和調整/移動。是以，維護一個K(該題目中是10)大小的小根堆，然後周遊300萬的Query，分别和根元素進行對比是以，我們最終的時間複雜度是：O（N） + N’*O（logK），（N為1000萬，N’為300萬）。ok，更多，詳情，請參考原文。
或者：采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最後用10個元素的最小推來對出現頻率進行排序。
3、有一個1G大小的一個檔案，裡面每一行是一個詞，詞的大小不超過16位元組，記憶體限制大小是1M。傳回頻數最高的100個詞。
方案：順序讀檔案中，對于每個詞x，取hash(x)P00，然後按照該值存到5000個小檔案（記為x0,x1,…x4999）中。這樣每個檔案大概是200k左右。
如果其中的有的檔案超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小檔案的大小都不超過1M。
對每個小檔案，統計每個檔案中出現的詞以及相應的頻率（可以采用trie樹/hash_map等），并取出出現頻率最大的100個詞（可以用含100個結點的最小堆），并把100個詞及相應的頻率存入檔案，這樣又得到了5000個檔案。下一步就是把這5000個檔案進行歸并（類似與歸并排序）的過程了。
4、有10個檔案，每個檔案1G，每個檔案的每一行存放的都是使用者的query，每個檔案的query都可能重複。要求你按照query的頻度排序。
還是典型的TOP K算法，解決方案如下：
方案1：
順序讀取10個檔案，按照hash(query)的結果将query寫入到另外10個檔案（記為）中。這樣新生成的檔案每個的大小大約也1G（假設hash函數是随機的）。
找一台記憶體在2G左右的機器，依次對用hash_map(query, query_count)來統計每個query出現的次數。利用快速/堆/歸并排序按照出現次數進行排序。将排序好的query和對應的query_cout輸出到檔案中。這樣得到了10個排好序的檔案（記為）。
對這10個檔案進行歸并排序（内排序與外排序相結合）。
方案2：
一般query的總量是有限的，隻是重複的次數比較多而已，可能對于所有的query，一次性就可以加入到記憶體了。這樣，我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數，然後按出現次數做快速/堆/歸并排序就可以了。
方案3：
與方案1類似，但在做完hash，分成多個檔案後，可以交給多個檔案來處理，采用分布式的架構來處理（比如MapReduce），最後再進行合并。
5、 給定a、b兩個檔案，各存放50億個url，每個url各占64位元組，記憶體限制是4G，讓你找出a、b檔案共同的url？
方案1：可以估計每個檔案安的大小為5G×64=320G，遠遠大于記憶體限制的4G。是以不可能将其完全加載到記憶體中處理。考慮采取分而治之的方法。
周遊檔案a，對每個url求取hash(url)00，然後根據所取得的值将url分别存儲到1000個小檔案（記為a0,a1,…,a999）中。這樣每個小檔案的大約為300M。
周遊檔案b，采取和a相同的方式将url分别存儲到1000小檔案（記為b0,b1,…,b999）。這樣處理後，所有可能相同的url都在對應的小檔案（a0vsb0,a1vsb1,…,a999vsb999）中，不對應的小檔案不可能有相同的url。然後我們隻要求出1000對小檔案中相同的url即可。
求每對小檔案中相同的url時，可以把其中一個小檔案的url存儲到hash_set中。然後周遊另一個小檔案的每個url，看其是否在剛才建構的hash_set中，如果是，那麼就是共同的url，存到檔案裡面就可以了。
方案2：如果允許有一定的錯誤率，可以使用Bloom filter，4G記憶體大概可以表示340億bit。将其中一個檔案中的url使用Bloom filter映射為這340億bit，然後挨個讀取另外一個檔案的url，檢查是否與Bloom filter，如果是，那麼該url應該是共同的url（注意會有一定的錯誤率）。
Bloom filter日後會在本BLOG内詳細闡述。
6、在2.5億個整數中找出不重複的整數，注，記憶體不足以容納這2.5億個整數。
方案1：采用2-Bitmap（每個數配置設定2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需記憶體2^32 * 2 bit=1 GB記憶體，還可以接受。然後掃描這2.5億個整數，檢視Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事後，檢視bitmap，把對應位是01的整數輸出即可。
方案2：也可采用與第1題類似的方法，進行劃分小檔案的方法。然後在小檔案中找出不重複的整數，并排序。然後再進行歸并，注意去除重複的元素。
7、騰訊面試題：給40億個不重複的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中？
與上第6題類似，我的第一反應時快速排序+二分查找。以下是其它更好的方法：
方案1：oo，申請512M的記憶體，一個bit位代表一個unsigned int值。讀入40億個數，設定相應的bit位，讀入要查詢的數，檢視相應bit位是否為1，為1表示存在，為0表示不存在。
dizengrong：
方案2：這個問題在《程式設計珠玑》裡有很好的描述，大家可以參考下面的思路，探讨一下：
又因為2^32為40億多，是以給定一個數可能在，也可能不在其中；
這裡我們把40億個數中的每一個用32位的二進制來表示
假設這40億個數開始放在一個檔案中。
然後将這40億個數分成兩類:
1.最高位為0
2.最高位為1
并将這兩類分别寫入到兩個檔案中，其中一個檔案中數的個數<=20億，而另一個>=20億（這相當于折半了）；
與要查找的數的最高位比較并接着進入相應的檔案再查找
再然後把這個檔案為又分成兩類:
1.次最高位為0
2.次最高位為1
并将這兩類分别寫入到兩個檔案中，其中一個檔案中數的個數<=10億，而另一個>=10億（這相當于折半了）；
與要查找的數的次最高位比較并接着進入相應的檔案再查找。
…….
以此類推，就可以找到了,而且時間複雜度為O(logn)，方案2完。
附：這裡，再簡單介紹下，位圖方法：
使用位圖法判斷整形數組是否存在重複
判斷集合中存在重複是常見程式設計任務之一，當集合中資料量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。
位圖法比較适合于這種情況，它的做法是按照集合中最大元素max建立一個長度為max+1的新數組，然後再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的資料肯定和以前的資料存在着重複。這種給新數組初始化時置零其後置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。