前言

#程式設(shè)計師對雜湊演算法應(yīng)該都不陌生，例如業(yè)界著名的MD5、SHA、 CRC等等;在日常開發(fā)中我們經(jīng)常用一個Map來裝載一些具有(key,value)結(jié)構(gòu)的數(shù)據(jù)，利用哈希算法O(1)的時間複雜度提高程序處理效率，除此之外，你還知道哈希演算法的其他應(yīng)用場景嗎？

1. 什麼是雜湊演算法？

了解雜湊演算法的應(yīng)用場景前，我們先看下雜湊（雜湊）想法，雜湊就是把任意長度的輸入透過雜湊演算法變換成固定長度的輸出，輸入稱為Key(鍵)，輸出為Hash值，即雜湊值hash(key)，雜湊演算法即hash()函數(shù)（雜湊與雜湊是對hash的不同翻譯）；實際上儲存這些雜湊值的是一個數(shù)組，稱為散列表，散列表用的是數(shù)組支援按照下標隨機存取資料的特性，把資料值與數(shù)組下標按雜湊函數(shù)做的一一映射，從而實現(xiàn)O(1)的時間複雜度查詢；

#1.1 散列衝突

目前的雜湊演算法MD5、SHA、CRC等都無法做到一個不同的key對應(yīng)的雜湊值都不一樣的雜湊函數(shù)，即無法避免出現(xiàn)不同的key映射到同一個值的情況，即出現(xiàn)了雜湊衝突，而且，因為陣列的儲存空間有限，也會增加雜湊衝突的機率。如何解決散列衝突？我們常用的雜湊衝突解決方法有兩類：開放尋址法(open addressing) 和 鍊錶法(chaining)。

1.1.1 開放尋址法

透過線性探測的方法找到散列表中空閒位置，寫入hash值：

如圖，834313在hash表中散列到303432的位置上，出現(xiàn)了衝突，則順序遍歷hash表直到找到空閒位置寫入834313；當(dāng)散列表中空閒位置不多的時候，散列衝突的機率就會大大增加，一般情況下，我們會盡可能保證散列衝突中有一定比例的空閒槽位，此時，我們用裝載因子來表示空閒位置的多少，計算公式是：散列表的裝載因子=填入表中的元素個數(shù)/散列表的長度。裝載因子越大，表示空閒位置越少，衝突越多，散列表的效能就會下降。

當(dāng)資料量比較小，裝載因子小的時候，適合採用開放尋址法，這也是java中的ThreadLocalMap使用開放尋址法解決散列衝突的原因。

1.1.2 鍊錶法

鍊錶法是一種較常用的雜湊衝突解決方法，也比較簡單。如圖：

在散列表中，每個桶/槽會對應(yīng)一條鍊錶，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鍊錶中；當(dāng)雜湊衝突比較多時，鍊錶的長度也會變長，查詢hash值需要遍歷鍊錶，這時查詢效率就會從O(1)退化成O(n)。

這種解決散列衝突的處理方法比較適合大物件、大資料量的散列表，而且，支援更多的最佳化策略，例如使用紅黑樹來取代鍊錶；jdk1.8為了對HashMap做進一步優(yōu)化，引入了紅黑樹，當(dāng)鍊錶長度太長（預(yù)設(shè)超過8）時，鍊錶就會轉(zhuǎn)換成紅黑樹，這時可以利用紅黑樹快速增刪查改的特點，提高HashMap的性能，當(dāng)紅黑樹節(jié)點個數(shù)小於8個時，又將紅黑樹轉(zhuǎn)換成為鍊錶，因為在資料量比較小的情況下，紅黑樹要維持平衡，比起鍊錶，效能上的優(yōu)勢並不明顯。

2. 雜湊演算法的應(yīng)用場景

2.1 安全加密

最常用於加密的雜湊演算法是MD5(MD5 Message-Digest Algorithm)和SHA(Secure Hash Algorithm 安全雜湊演算法)，利用hash的特徵計算出來的hash值很難反向推導(dǎo)出原始數(shù)據(jù)，從而達到加密的目的。

以MD5為例子，哈希值是固定的128位元二進位串，最多能表示2^128 個數(shù)據(jù)，這個數(shù)據(jù)已經(jīng)是天文數(shù)字了，散列衝突的機率要小於1/2^ 128，如果希望透過窮舉法來找到跟這個MD5相同的另一個數(shù)據(jù)，那耗費的時間也應(yīng)該是天文數(shù)字了，所以在有限的時間內(nèi)哈希演算法還是很難被破解的，這也就達到了加密效果了。

2.2 資料校驗

利用Hash函數(shù)對資料敏感的特點，可以用來校驗網(wǎng)路傳輸過程中的資料是否正確，防止被惡意串改。

2.3 雜湊函數(shù)

利用hash函數(shù)相對均勻分佈的特點，取hash值作為資料儲存的位置值，讓資料均勻分佈在容器裡面。

2.4 負載平衡

透過hash演算法，對客戶端id位址或會話id進行計算hash值，將取得的雜湊值與伺服器清單的大小進行取模運算，最終得到的值就是應(yīng)該要路由到的伺服器編號。

2.5 資料分片

假如我們有1T的日誌文件，裡面記錄了使用者的搜尋關(guān)鍵字，我們想要快速統(tǒng)計每個關(guān)鍵字被搜尋的次數(shù)，該怎麼做呢？資料量比較大，很難放到一臺機的記憶體中，即使放到一臺機子上，處理時間也會很長，針對這個問題，我們可以先對資料進行分片，然後再用多臺機器處理的方法，來提高處理速度。

具體的想法是：為了提高處理速度，我們用n臺機器並行處理。從搜尋記錄的日誌檔案中，依序獨處每個搜尋關(guān)鍵字，並透過雜湊函數(shù)計算哈希值，然後再跟n取模，最終得到的值，就是應(yīng)該被分配到的機器編號；這樣哈希值相同的搜尋關(guān)鍵字就被分配到了同一臺機器上，每個機器會分別計算關(guān)鍵字出現(xiàn)的次數(shù)，最後合併起來就是最終的結(jié)果。實際上，這裡的處理過程也是MapReduce的基本設(shè)計想法。

2.6 分散式儲存

對於海量的資料需要快取的情況，一臺快取機器肯定是不夠的，於是，我們就需要將資料分散在多臺機器上。 這時，我們可以藉助前面的分片思想，也就是透過雜湊演算法對資料取哈希值，然後對機器個數(shù)取模，得到應(yīng)該儲存的快取機器編號。

但是，如果資料增多，原來的10臺機器已無法承受，需要擴容了，這時是如果所有資料都重新計算哈希值，然後重新搬移到正確的機器上，那就相當(dāng)於所有的快取資料一下子都失效了，會穿透快取回源到資料庫，這樣就可能發(fā)生雪崩效應(yīng)，壓垮資料庫。為了新增快取機器不搬移所有的數(shù)據(jù)，一致性雜湊演算法就是比較好的選擇了，主要的想法是：假設(shè)我們有kge機器，資料的雜湊值範圍是[0, Max]，我們將整個範圍劃分成m個小區(qū)間(m遠大於k)，每個機器負責(zé)m/k個小區(qū)間，當(dāng)有新機器加入時，我們就將某幾個小區(qū)間的數(shù)據(jù)，從原來的機器中搬移到新的機器中，這樣，即不用全部重新哈希、搬移數(shù)據(jù)，也保持了各個機器上數(shù)據(jù)量的平衡。

3. ?寫在最後

實際上，哈希演算法還有很多其他的應(yīng)用，例如git commit id等等，很多應(yīng)用都來自於對演算法的理解和擴展，也是基礎(chǔ)的資料結(jié)構(gòu)和演算法的價值體現(xiàn)，需要我們在工作中慢慢理解和體會。

推薦教學(xué)：《Java教學(xué)》

以上是常用演算法之哈希演算法的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！