1）哈希算法：

????將任意長度的二進制串映射為固定長度的二進制值串，這個映射的規(guī)則就是哈希算法，而通過原始數(shù)據(jù)映射之后得到的二進制值串就是哈希值。要設(shè)計一個哈希算法要滿足幾點要求：

1. 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈細(xì)算法也叫單向哈希算法）；

2. 對輸入數(shù)據(jù)敏感，稍作改變得到的哈希值也大不相同；

3. 散列沖突的概率要小，對不同的原始數(shù)據(jù)，哈希值相同的概率很小；

4. 效率要盡量高效，針對很長的文本也能快速的計算出哈希值。

2）哈希算法的應(yīng)用

? ??1.安全加密：

????最常用的安全加密算法是MD5（消息摘要算法）和SHA（安全散列算法），除了這兩個以外還有其他加密算法，比如DES、AES。前面講的哈希算法的四點要求其實有兩點對于安全加密來書尤為重要，不能反向推導(dǎo)和散列沖突概率小，理論上哈希算法無法做到零沖突，比如MD5算法，他的哈希值固定式128個二進制串，也就是最多能表示2^128個數(shù)據(jù)。所以一旦數(shù)據(jù)量達(dá)到2^128+1，那么就一定會有重復(fù)的。但是盡管散列沖突是無法避免的，但是如果拿到一個MD5的哈希值，找到跟這個值相同的另一個數(shù)據(jù)，那耗費的時間也會是一個天文數(shù)字，所以有限時間資源情況下，哈希算法還是很難破解的。

? ??2.唯一標(biāo)識：

????如果想要在海量的圖庫中，搜索一張圖是否存在，不能單純的根據(jù)圖片的元信息（比如說圖片的名稱）來進行搜索，因為可能存在名稱相同但是圖片內(nèi)容不同的。任何文件在計算中都可以表示成二進制碼串，所以比較笨的方法就是拿圖片的二進制碼串和數(shù)據(jù)庫中的作比較，但是每個圖片轉(zhuǎn)換成二進制是一個非常長的串，比對起來非常耗時。

????可以給每一個圖片取一個唯一標(biāo)識，或者說信息摘要，比如說可以取圖片的二進制字碼串前100，中間100，后100，將這300個字節(jié)放在一塊通過哈希算法得到一個哈希字符串，作為唯一標(biāo)識。

????如果想繼續(xù)提高效率，可以把每個圖片的唯一標(biāo)識和圖片的路徑都存儲在一個散列表中，當(dāng)要查詢某一個圖片是否在圖庫中的時候，可以對這個圖片進行哈希算法獲得唯一標(biāo)識，然后在散列表中查找是否存在這個唯一標(biāo)識。如果不存在，則說明不在圖庫中，如果存在，則查到這個圖片，然后把兩張圖片進行全量對比，如果相同，則說明存在，如果不相同，則說明兩張圖片盡管標(biāo)識相同，但是圖片其實是不一樣的。

3.數(shù)據(jù)校驗

????要下載一個電影，可能會被分割成很多的文件塊，（比如下載一個2GB的電影，被分割成100塊，每塊大約20MB），等所有的片段都下載完，在組裝成一個片段就可以了。網(wǎng)絡(luò)下載是不安全的，下載后的文件可能會被宿主惡意修改過的，又或者下載過程中出現(xiàn)了錯誤，導(dǎo)致下載不完整，這樣最后合并可能無法觀看甚至導(dǎo)致電腦中毒。那么如何校驗文件塊的安全、正確、完整。

????BT協(xié)議很復(fù)雜，校驗方法也有很多，通過哈希算法校驗是其中一種，對100個文件塊分別取哈希值，并且保存在種子文件中。從前面來看，哈希算法十分敏感，只要文件塊的內(nèi)容有一丁點改變，最終計算得到的哈希值就會完全不同。當(dāng)文件塊下載完后，對其一一求哈希值然后和種子文件中的哈希值作對比。如果不同，則說明這個文件不完整或者被惡意篡改了。

4.散列函數(shù)

????散列函數(shù)其實也是哈希算法的一種應(yīng)用，相對于其他哈希算法的運用，散列函數(shù)對于散列沖突的要求其實低得多，只要不是過分嚴(yán)重，都可以通過鏈表法和開放尋址法來進行解決，而且對于是否能反向推導(dǎo)也不太關(guān)切，更加關(guān)注的是散列后的值能否平均分布，除此以外，散列函數(shù)的執(zhí)行快慢也會影響散列表的效率，散列函數(shù)用的散列算法設(shè)計一般比較簡單，比較追求效率。

3）區(qū)塊鏈的底層實現(xiàn)

????區(qū)塊鏈?zhǔn)怯梢粔K塊區(qū)塊組成的，每個區(qū)塊分為兩部分，區(qū)塊頭和區(qū)塊體，區(qū)塊頭上保存著自己的區(qū)塊體的和上一個區(qū)塊頭的哈希值，這種鏈?zhǔn)降年P(guān)系和哈希值的唯一性，只要區(qū)塊鏈上任意一個區(qū)塊被修改過，后面所有區(qū)塊保存的哈希值就不對了。如果要篡改一個區(qū)塊，就必須重新計算該區(qū)塊后面所有的區(qū)塊的哈希值，短時間內(nèi)幾乎不可能做到。

5.負(fù)載均衡

????負(fù)載均衡的方法有很多，比如輪詢、隨機、加權(quán)輪詢等，如何實現(xiàn)一個會話粘滯的負(fù)載均衡算法，也就是在同一個客戶端上，在一次會話中所有的請求都路由到同一個服務(wù)器上。

????最直接的方法就是維護一張映射關(guān)系表，這張表的內(nèi)容是客戶端IP地址或者會話ID與服務(wù)器編號的映射關(guān)系，客戶端每次發(fā)出請求，都要先在映射表中查找應(yīng)該路由到的服務(wù)器編號，然后在請求編號對應(yīng)的服務(wù)器。優(yōu)點：簡單直觀。缺點：如果客戶端很多，映射表可能會很大，比較浪費內(nèi)存空間；客戶端下線，上線，服務(wù)器擴容、縮容都會導(dǎo)致映射失效，這樣維護映射表的成本就會很大。

????如果借助哈希算法，這些問題都可以非常完美的解決?？梢酝ㄟ^哈希算法，對客戶端IP地址或者會話ID計算哈希值，將取得的哈希值與服務(wù)器列表的大小進行取模運算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號。這樣就可以把同一個IP發(fā)過來的請求，都路由到同一個后端服務(wù)器上。

6.數(shù)據(jù)分片

舉例來說明：

1）如何統(tǒng)計“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)

????假設(shè)有1T的日志文件，記錄了用戶的搜索關(guān)鍵詞，要快速統(tǒng)計出每個關(guān)鍵詞被搜索的次數(shù)，該怎么做?

????兩個難點：一是搜索日志很大，沒辦法放到一臺機器內(nèi)存，二是如果只用一臺機器來處理那么大的數(shù)據(jù)處理時間會很長。

????針對這兩個難點，可以先對數(shù)據(jù)進行分片，然后采用多臺機器處理的方式，來提高處理速度，具體思路是采用n臺機器進行并行處理，我們從搜索記錄的日志文件中，依次讀出每個搜索關(guān)鍵詞，并且通過哈希算法對關(guān)鍵詞進行計算得到哈希值，然后跟n取模，最終得到的值就是應(yīng)該被分配到的機器編號，這樣相同的關(guān)鍵詞就會被分配到同一臺機器，每個機器分別計算關(guān)鍵詞出現(xiàn)的次數(shù)，最后合并起來就是最終的結(jié)果。這也是MapReduce的基本設(shè)計思想。

2）如何快速判斷圖片是否在圖庫中

????現(xiàn)在有1億張圖片，很顯然，在單臺機器上構(gòu)建散列表是行不通的，因為單臺機器的內(nèi)存有限，所以前面提到的方法就失效了。

????同樣對數(shù)據(jù)進行分片，然后采用多機處理，準(zhǔn)備n臺機器，讓每臺機器只維護一部分圖片對應(yīng)的散列表。每次從圖庫中讀取一個圖片，對圖片進行唯一標(biāo)識計算，然后與機器個數(shù)n求余取模，假設(shè)得到的值為k，那就去編號k的機器構(gòu)建的散列表中查找。

????估算一下需要多少臺機器，散列表每個數(shù)據(jù)單元包括兩個信息，哈希值和圖片文件的路徑，假設(shè)通過MD5來計算哈希值，那長度就是128bit，也就是16字節(jié)，文件路徑上限是256字節(jié)，假設(shè)平均長度128字節(jié)。如果用鏈表法來解決散列沖突，每個指針8字節(jié)，所以散列表中每個數(shù)據(jù)單元大概是152字節(jié)。假設(shè)一臺機器內(nèi)存2GB，散列表因子0.75，那一臺機器可以給大約1000萬張照片構(gòu)建散列表，所以需要大概十幾臺機器。

7.分布式存儲

????互聯(lián)網(wǎng)面對著海量的數(shù)據(jù)、海量的用戶，為了提高數(shù)據(jù)的讀取、寫入能力一般采用分布式來存儲數(shù)據(jù)，比如說分布式緩存，需要將海量的緩存存儲到多臺機器上，那么如何決定將哪個數(shù)據(jù)放到哪臺服務(wù)器上，可以根據(jù)數(shù)據(jù)分片思想，即對于數(shù)據(jù)進行哈希計算取哈希值，然后對機器數(shù)量取模，得到的值就是緩存機器編號。

但是！

????如果數(shù)據(jù)增多，由10臺機器擴容到11臺機器，這時候麻煩就來了，原來的數(shù)據(jù)是對10區(qū)模的，現(xiàn)在11臺機器，所有的數(shù)據(jù)都需要重新計算哈希值，然后搬移到正確的機器上，這樣就相當(dāng)于，緩存的數(shù)據(jù)一下子全部失效了，所有的數(shù)據(jù)請求會穿透緩存，直接訪問數(shù)據(jù)庫，這樣就是可能會發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫。

????所以，需要一種在加入一個新的機器，并不需要進行大量數(shù)據(jù)搬移的算法一致性哈希算法，假設(shè)有k個機器，數(shù)據(jù)哈希值范圍[0,MAX]。我們將整個范圍劃分為m個小區(qū)間(m遠(yuǎn)大于k)，每個機器負(fù)責(zé)m/k個小區(qū)間，當(dāng)有新機器加入時，就把某幾個小區(qū)間的數(shù)據(jù)從原來的機器中搬移到新機器。這樣既不用全部重新計算哈希、搬移數(shù)據(jù)，也保持了各個機器上數(shù)據(jù)量的均衡。（一致性哈希算法可以參考http://www.itdecent.cn/p/570dc8913c20）

（本文是個人聽課筆記，不少東西摘取于王爭老師的原文，原文鏈接http://gk.link/a/10aMZ）