1）哈希算法：

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

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

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

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

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

2）哈希算法的應用

? ??1.安全加密：

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

? ??2.唯一標識：

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

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

????如果想繼續(xù)提高效率，可以把每個圖片的唯一標識和圖片的路徑都存儲在一個散列表中稚失，當要查詢某一個圖片是否在圖庫中的時候栋艳，可以對這個圖片進行哈希算法獲得唯一標識，然后在散列表中查找是否存在這個唯一標識句各。如果不存在吸占，則說明不在圖庫中，如果存在凿宾，則查到這個圖片矾屯，然后把兩張圖片進行全量對比，如果相同初厚，則說明存在问拘，如果不相同，則說明兩張圖片盡管標識相同惧所，但是圖片其實是不一樣的骤坐。

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

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

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

4.散列函數(shù)

????散列函數(shù)其實也是哈希算法的一種應用粉洼，相對于其他哈希算法的運用节预，散列函數(shù)對于散列沖突的要求其實低得多，只要不是過分嚴重属韧，都可以通過鏈表法和開放尋址法來進行解決安拟，而且對于是否能反向推導也不太關切，更加關注的是散列后的值能否平均分布宵喂，除此以外糠赦，散列函數(shù)的執(zhí)行快慢也會影響散列表的效率，散列函數(shù)用的散列算法設計一般比較簡單锅棕，比較追求效率拙泽。

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

????區(qū)塊鏈是由一塊塊區(qū)塊組成的，每個區(qū)塊分為兩部分裸燎，區(qū)塊頭和區(qū)塊體顾瞻，區(qū)塊頭上保存著自己的區(qū)塊體的和上一個區(qū)塊頭的哈希值，這種鏈式的關系和哈希值的唯一性德绿，只要區(qū)塊鏈上任意一個區(qū)塊被修改過荷荤，后面所有區(qū)塊保存的哈希值就不對了退渗。如果要篡改一個區(qū)塊，就必須重新計算該區(qū)塊后面所有的區(qū)塊的哈希值蕴纳，短時間內幾乎不可能做到会油。

5.負載均衡

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

????最直接的方法就是維護一張映射關系表颖低，這張表的內容是客戶端IP地址或者會話ID與服務器編號的映射關系絮吵，客戶端每次發(fā)出請求，都要先在映射表中查找應該路由到的服務器編號忱屑，然后在請求編號對應的服務器蹬敲。優(yōu)點：簡單直觀。缺點：如果客戶端很多莺戒，映射表可能會很大伴嗡，比較浪費內存空間；客戶端下線从铲，上線瘪校，服務器擴容、縮容都會導致映射失效名段，這樣維護映射表的成本就會很大阱扬。

????如果借助哈希算法，這些問題都可以非常完美的解決伸辟÷榛蹋可以通過哈希算法，對客戶端IP地址或者會話ID計算哈希值信夫，將取得的哈希值與服務器列表的大小進行取模運算窃蹋，最終得到的值就是應該被路由到的服務器編號。這樣就可以把同一個IP發(fā)過來的請求静稻，都路由到同一個后端服務器上警没。

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

舉例來說明：

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

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

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

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

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

????現(xiàn)在有1億張圖片躯畴，很顯然民鼓，在單臺機器上構建散列表是行不通的，因為單臺機器的內存有限蓬抄，所以前面提到的方法就失效了丰嘉。

????同樣對數(shù)據(jù)進行分片，然后采用多機處理嚷缭，準備n臺機器饮亏，讓每臺機器只維護一部分圖片對應的散列表。每次從圖庫中讀取一個圖片阅爽，對圖片進行唯一標識計算路幸，然后與機器個數(shù)n求余取模，假設得到的值為k优床，那就去編號k的機器構建的散列表中查找。

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

7.分布式存儲

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

但是适荣！

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

????所以蓖墅，需要一種在加入一個新的機器库倘，并不需要進行大量數(shù)據(jù)搬移的算法一致性哈希算法，假設有k個機器论矾，數(shù)據(jù)哈希值范圍[0,MAX]教翩。我們將整個范圍劃分為m個小區(qū)間(m遠大于k)，每個機器負責m/k個小區(qū)間贪壳，當有新機器加入時饱亿，就把某幾個小區(qū)間的數(shù)據(jù)從原來的機器中搬移到新機器。這樣既不用全部重新計算哈希、搬移數(shù)據(jù)彪笼，也保持了各個機器上數(shù)據(jù)量的均衡钻注。（一致性哈希算法可以參考http://www.reibang.com/p/570dc8913c20）

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