一、概述
本文将粗略講述一下Hash算法的概念特性，裡邊會結合分布式系統負載均衡執行個體對Hash的一緻性做深入探讨。另外，探讨一下Hash算法在海量資料處理方案中的通用性。最後，從源代碼出發，具體分析一下Hash算法在MapReduce架構的中的應用。
二、Hash算法
Hash可以通過散列函數将任意長度的輸入變成固定長度的輸出，也可以将不同的輸入映射成為相同的相同的輸出，而且這些輸出範圍也是可控制的，是以起到了很好的壓縮映射和等價映射功能。這些特性被應用到了資訊安全領域中加密算法，其中等價映射這一特性在海量資料解決方案中起到相當大的作用，特别是在整個MapReduce架構中，下面章節會對這二方面詳細說。話說，Hash為什麼會有這種壓縮映射和等價映射功能，主要是因為Hash函數在實作上都使用到了取模。下面看看幾種常用的Hash函數：
·直接取餘法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一個質數。
·乘法取整法：f(x):=trunc((x/maxX)*maxlongit) mod maxM，主要用于實數。
·平方取中法：f(x):=(x*x div 1000 ) mod 1000000); 平方後取中間的，每位包含資訊比較多。
三、Hash算法在海量資料處理方案中的應用
單機處理海量資料的大體主流思想是和MapReduce架構一樣，都是采取分而治之的方法，将海量資料切分為若幹小份來進行處理，并且在處理的過程中要兼顧記憶體的使用情況和處理并發量情況。而更加仔細的處理流程大體上分為幾步（對大多數情況都使用，其中少部分情況要根據你自己的實際情況和其他解決方法做比較采用最符合實際的方法）：
第一步：分而治之。
采用Hash取模進行等價映射。采用這種方法可以将巨大的檔案進行等價分割（注意：符合一定規律的資料要被分割到同一個小檔案）變成若幹個小檔案再進行處理。這個方法針對資料量巨大，記憶體受到限制時十分有效。
第二步：利用hashMap在記憶體中進行統計。
我們通過Hash映射将大檔案分割為小檔案後，就可以采用HashMap這樣的存儲結構來對小檔案中的關注項進行頻率統計。具體的做法是将要進行統計的Item作為HashMap的key，此Item出現的次數作為value。
第三步：在上一步進行統計完畢之後根據場景需求往往需要對存儲在HashMap中的資料根據出現的次數來進行排序。其中排序我們可以采用堆排序、快速排序、歸并排序等方法。
現在我們來看看具體的例子:
【例子1】海量日志資料，提取出某日通路百度次數最多的那個IP
思路：當看到這樣的業務場景，我們腦子裡應該立馬會想到這些海量網關日志資料量有多大？這些IP有多少中組合情況，最大情況下占多少存儲空間？解決這樣的問題前我們最重要的先要知道資料的規模，這樣才能從大體上制定解決方案。是以現在假設這些這些網關日志量有3T。下面大體按照我們上面的步驟來對解決此場景進行分析：
（1）首先，從這些海量資料中過濾出指定一天通路百度的使用者IP,并逐個寫到一個大檔案中。
（2）采用“分而治之”的思想用Hash映射将大檔案進行分割降低資料規模。按照IP位址的Hash(IP)%1024值，把海量IP日志分别存儲到1024個小檔案中，其中Hash函數得出值為分割後小檔案的編号。
（3）逐個讀小檔案，對于每一個小檔案建構一個IP為key，出現次數為value的HashMap。對于怎麼利用HashMap記錄IP出現的次數這個比較簡單，因為我們可以通過程式讀小檔案将IP放到HashMap中key的之後可以先判斷此IP是否已經存在如果不存在直接放進去，其出現次數記錄為1，如果此IP已經存儲則過得其對應的value值也就是出現的次數然後加1就ok。最後，按照IP出現的次數采用排序算法對HashMap中的資料進行排序，同時記錄目前出現次數最多的那個IP位址；
（4）走到這步，我們可以得到1024個小檔案中出現次數最多的IP了，再采用正常的排序算法找出總體上出現次數最多的IP就ok了。
這個我們需要特别地明确知道一下幾點内容：
第一：我們通過Hash函數:Hash(IP)%1024将大檔案映射分割為了1024個小檔案，那麼這1024個小檔案的大小是否均勻？另外，我們采用HashMap來進行IP頻率的統計，記憶體消耗是否合适？
首先是第一個問題，被分割的小檔案的大小的均勻程度是取決于我們使用怎麼樣的Hash函數，對本場景而言就是：Hash(IP)%1024。設計良好的Hash函數可以減少沖突，使資料均勻的分割到1024個小檔案中。但是盡管資料映射到了另外一些不同的位置，但資料還是原來的資料，隻是代替和表示這些原始資料的形式發生了變化而已。
另外，看看第二個問題：用HashMap統計IP出現頻率的記憶體使用情況。
要想知道HashMap在統計IP出現的頻率，那麼我們必須對IP組合的情況有所了解。32Bit的IP最多可以有2^32種的組合方式，也就是說去所有IP最多占4G存儲空間。在此場景中，我們已經根據IP的hash值将大檔案分割出了1024個小檔案，也就是說這4G的IP已經被分散到了1024個檔案中。那麼在Hash函數設計合理最perfect的情況下針對每個小檔案的HashMap占的記憶體大小最多為4G/1024+存儲IP對應的次數所占的空間，是以記憶體絕對夠用。
第二：Hash取模是一種等價映射，換句話說通過映射分割之後相同的元素隻會分到同一個小檔案中去的。就本場景而言，相同的IP通過Hash函數後隻會被分割到這1024個小檔案中的其中一個檔案。
【例子2】給定a、b兩個檔案，各存放50億個url，每個url各占64位元組，記憶體限制是4G，讓你找出a、b檔案共同的url？
思路:還是老一套，先Hash映射降低資料規模，然後統計排序。
具體做法：
（1）分析現有資料的規模。
按照每個url64位元組來算，每個檔案有50億個url，那麼每個檔案大小為5G*64=320G。320G遠遠超出記憶體限定的4G，是以不能将其全部加載到記憶體中來進行處理，需要采用分而治之的方法進行處理。
(2)Hash映射分割檔案。逐行讀取檔案a，采用hash函數：Hash(url)%1000将url分割到1000個小檔案中，檔案即為f1_1,f1_2,f1_3,...,f1_1000。那麼理想情況下每個小檔案的大小大約為300m左右。再以相同的方法對大檔案b進行相同的操作再得到1000個小檔案，記為：f2_1,f2_2,f2_3,...,f2_1000。
經過一番折騰後我們将大檔案進行了分割并且将相同url都分割到了這2組小檔案中下标相同的兩個檔案中,其實我們可以将這2組檔案看成一個整體：f1_1&f2_1，f1_2&,f2_2,f1_3&f2_3,...,f1_1000&f2_1000。那麼我們就可以将問題轉化成為求這1000對小檔案中相同的url就可以了。接下來，求每對小檔案中的相同url，首先将每對對小檔案中較小的那個的url放到HashSet結構中，然後周遊對應這對小檔案中的另一個檔案，看其是否存才剛剛建構的HashSet中，如果存在說明是一樣的url，将這url直接存到結果檔案就ok了。
【例子3】有10個檔案，每個檔案1G，每個檔案的每一行存放的都是使用者的query，每個檔案的query都可能重複。要求你按照query的頻度排序。
【例子4】有一個1G大小的一個檔案，裡面每一行是一個詞，詞的大小不超過16位元組，記憶體限制大小是1M。傳回頻數最高的100個詞。
像例子3和例子4這些場景都可以用我們的一貫老招數解決：先Hash映射降低資料規模，然後統計加載到記憶體，最後排序。具體做法可以參考上面2個例子。
四、Hash算法在MapReduce架構中的應用
Hash算法在分布式計算架構MapReduce中起着核心作用。先來看看下面整個mapreduce的運作流程，首先是原始資料經過切片進入到map函數中，經過map函數的資料會在整個環形緩沖區裡邊進行第一次排序，接着map的輸出結果會根據key值(預設情況是這樣，另外可以自定義)進行Hash映射将資料量龐大的map輸出分割為N份（N為reduce數目）來實作資料的并行處理，這就是Partition階段，另外MapReduce架構中Partition的實作方式往往能夠決定資料的傾斜度，是以在處理資料前最好要對資料的分布情況有所了解。
接下來從MapReudce的源碼角度來研究一下Partition的實作原理：
其Partition的實作主要有：HashPartitioner、BinaryPartitioner、KeyFieldBasedPartitioner、TotalOrderPartitioner這幾種，其中HashPartitioner是預設的。首先來看看HashPartitioner的核心實作：
我們看到第25行，在這裡我們有看到了可愛的Hash取模映射方法，這樣做的原因大家看到這裡都應該已經了然于心了。另外，TotalOrderPartitioner、BinaryPartitioner等幾種Partitioner的實作都是基于Hash取模映射方法，隻是他們為了實作自己自定義的功能而添加了一些邏輯，例如其中的TotalOrderPartitioner可以實作全排序功能。其他幾個Partition的源代碼這裡就不貼了，有興趣的可以自己看看。
五、Hash算法的其他特性
本部分為本文最後一部分，之是以要介紹這一部分的内容主要是從Hash算法的完整性出發的，這部分的内容和海量資料的解決方案關系不大，主要是用于分布式緩存設計方面。由于關于這部分的内容已經有一些大拿們做了很深入的研究并且講解地相當完美，小弟這裡就直接引用了。是以本部分引用的blog。
consistent hashing算法早在1997年就在論文中被提出，目前在cache系統中應用越來越廣泛；
比如你有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...
Hash算法的一個衡量名額是單調性（Monotonicity），定義如下：
單調性是指如果已經有一些内容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已配置設定的内容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
容易看到，上面的簡單hash算法hash(object)%N難以滿足單調性要求。
consistent hashing是一種hash算法，簡單的說，在移除/添加一個cache時，它能夠盡可能小的改變已存在key映射關系，盡可能的滿足單調性的要求。
下面就來按照5個步驟簡單講講consistent hashing算法的基本原理。
考慮通常的hash算法都是将value映射到一個32為的key值，也即是0~2^32-1次方的數值空間；我們可以将這個空間想象成一個首（0）尾（2^32-1）相接的圓環，如下面圖1所示的那樣。
圖1環形hash空間
接下來考慮4個對象object1~object4，通過hash函數計算出的hash值key在環上的分布如圖2所示。
hash(object1) = key1;
… …
hash(object4) = key4;
圖2 4個對象的key值分布
Consistent hashing的基本思想就是将對象和cache都映射到同一個hash數值空間中，并且使用相同的hash算法。
假設目前有A,B和C共3台cache，那麼其映射結果将如圖3所示，他們在hash空間中，以對應的hash值排列。
hash(cache A) = key A;
hash(cache C) = key C;
圖3 cache和對象的key值分布
說到這裡，順便提一下cache的hash計算，一般的方法可以使用cache機器的IP位址或者機器名作為hash輸入。
現在cache和對象都已經通過同一個hash算法映射到hash數值空間中了，接下來要考慮的就是如何将對象映射到cache上面了。
在這個環形空間中，如果沿着順時針方向從對象的key值出發，直到遇見一個cache，那麼就将該對象存儲在這個cache上，因為對象和cache的hash值是固定的，是以這個cache必然是唯一和确定的。這樣不就找到了對象和cache的映射方法了嗎？！
依然繼續上面的例子（參見圖3），那麼根據上面的方法，對象object1将被存儲到cache A上；object2和object3對應到cache C；object4對應到cache B；
前面講過，通過hash然後求餘的方法帶來的最大問題就在于不能滿足單調性，當cache有所變動時，cache會失效，進而對背景伺服器造成巨大的沖擊，現在就來分析分析consistent hashing算法。
3.5.1 移除cache
考慮假設cache B挂掉了，根據上面講到的映射方法，這時受影響的将僅是那些沿cache B逆時針周遊直到下一個cache（cache C）之間的對象，也即是本來映射到cache B上的那些對象。
是以這裡僅需要變動對象object4，将其重新映射到cache C上即可；參見圖4。
圖4 Cache B被移除後的cache映射
3.5.2 添加cache
再考慮添加一台新的cache D的情況，假設在這個環形hash空間中，cache D被映射在對象object2和object3之間。這時受影響的将僅是那些沿cache D逆時針周遊直到下一個cache（cache B）之間的對象（它們是也本來映射到cache C上對象的一部分），将這些對象重新映射到cache D上即可。
是以這裡僅需要變動對象object2，将其重新映射到cache D上；參見圖5。
圖5 添加cache D後的映射關系
考量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。
圖6 引入“虛拟節點”後的映射關系
此時，對象到“虛拟節點”的映射關系為：
objec1->cache A2；objec2->cache A1；objec3->cache C1；objec4->cache C2；
是以對象object1和object2都被映射到了cache A上，而object3和object4映射到了cache C上；平衡性有了很大提高。
引入“虛拟節點”後，映射關系就從{對象->節點}轉換到了{對象->虛拟節點}。查詢物體所在cache時的映射關系如圖7所示。
圖7 查詢對象所在cache
“虛拟節點”的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
參考文獻：
文章第五部分來自:
本文出自 “” 部落格，謝絕轉載！