資料結構之雜湊演算法
此文是資料結構和演算法之美學習筆記
雜湊演算法就是將任意長度的二進位制值對映為固定長度的二進位制串，這個對映的規則就是雜湊演算法，原始資料對映之後得到的二進位制雜湊值。
一般雜湊演算法的要求：
- 不能通過雜湊值反向推匯出原始資料（雜湊演算法也叫單向雜湊演算法）
- 對輸入的資料非常敏感，哪怕原始資料只是修改了一個bit，最後得到的雜湊值也大不形同
- 對不同的原始資料，雜湊值相同的概率要非常小，雜湊衝突的概率要很小。
- 雜湊演算法的執行效率要儘量的高效，即使較長的文字也能很快的計算出雜湊值
雜湊演算法的應用非常多最常見的有安全加密，唯一標識，資料校驗，雜湊函式，負載均衡，資料分片，分散式儲存。
安全加密
常用於加密的雜湊演算法是
MD5（Message-Digest-Algorihm 訊息摘要演算法）
SHA(Secure Hash Algorihm 安全雜湊演算法)
DES(Data Encryption Standard 資料加密標準)
AES(Advanced Encryption Standard 高階加密標準)
為什麼雜湊演算法無法做到零衝突？
有一個數學理論：鴿巢原理（也叫抽屜原理）就是說如果有10個鴿巢，有11個格子，那麼肯定有一個鴿巢中有兩個鴿子。
雜湊演算法產生的雜湊值的長度也是有限的，比如MD5的雜湊值固定是128位的二進位制串，最多能表示2
128個數據。而我們需要表示的雜湊數是無窮的，當資料大於2
128的時候，就必然會出現雜湊值相同的情況。不過由於2
128這個陣列已經很大了，出現雜湊衝突的概率要小於1/2
128，相對來說很難破解。沒有絕對的安全加密，越複雜越難破解的加密演算法，需要的計算時間也越長，就想SHA-256比SHA-1要更加複雜也就更安全，相應的計算時間就會更長。
唯一標識
比如在海量的相簿中怎麼搜尋一張圖片是否存在？
（1）使用圖片名字肯定不行，因為可能有的圖片名字不一樣但是都是一樣的圖片
（2）對比圖片的二進位制碼，這種辦法可行，但是比較笨，因為圖片很多都很大幾MB都是常事，轉化成二進位制後會很大，對比起來也非常耗時
（3）可以給每一張圖片取一個唯一標識，比如可以從二進位制碼的開頭取100位元組，中間取100位元組，結尾再取100位元組，把這300位元組放到一塊通過雜湊演算法比如MD5得到一個雜湊字串，用這個作為圖片的唯一標識來判斷庫中是否有該圖片
當我們向庫中插入一個圖片的時候，先去散列表中查詢唯一標識，如果不存在就說明這個圖片不在相簿中，如果存在就拿出這個圖片和將要插入的圖片做全量對比，看是否完全一樣。如果一樣說明已經存在，如果不一樣說明兩張圖片雖然唯一標識一樣但不是相同的圖片。
資料校驗
比如BT下載，一個電影可能會被分割成很多塊（比如100塊）分別下載，等所有檔案都下載完成之後在組裝成一個完整的電影檔案。
由於網路傳輸是不安全的，下載的檔案快可能會被宿主幾區惡意修改或者下載過程出現了錯誤導致下載的檔案是不完整的。如果下載完不能檢測是否出錯，就會導致最後合併完的電影無法觀看甚至中毒。
一種校驗的思路就是，把這100個快分別取雜湊值並且儲存在種子檔案中，由於雜湊演算法對原始資料非常敏感，只要檔案中有一點點改變最後的雜湊值就完全不同，當檔案塊下載完成後，我們可以通過同樣的雜湊演算法對下載好的檔案快一一求雜湊值跟種子檔案中的雜湊值對比。如果不一樣說明檔案快不完整或者被篡改了，需要重新下載。
雜湊函式
散列表中的雜湊函式也需要雜湊演算法，不過相對於其他的應用，它對雜湊演算法的要求不高，即使出現雜湊衝突，也可以通過開放定址法和連結串列法來解決
雜湊函式對雜湊演算法的要求主要雜湊後的值能否平均分佈，雜湊函式是否執行很快。
如何防止資料庫中資訊被脫庫
可以通過雜湊演算法，對使用者密碼進行加密之後在儲存不過最好選擇相對安全的加密演算法比如SHA(MD5據說被破解了)
不過如果使用者的密碼設定的很簡單比如000000，,13456等簡單的陣列，黑客可以通過字典攻擊很容易的猜中
針對字典攻擊可以引入一個鹽（salt）跟使用者的密碼組合在一起增加其複雜度然後在通過雜湊演算法加密。比如原始密碼是123456，可以在其頭部或者尾部加上個字串bxt變成bxt123456或者123456bxt也可以在中間加。
區塊鏈現很火，其實其底層也是通過雜湊演算法
區塊鏈是一塊塊的區塊組成，每個區塊分成區塊頭和區塊體，區塊頭儲存著自己區塊體和上一個區塊頭的雜湊值。
因為這種鏈式關係和雜湊值的唯一性，只要區塊鏈上的任意一個區塊被修改過，後面的所有的區塊儲存的雜湊值就不對了。
區塊鏈使用的是SHA256這種雜湊演算法，計算雜湊值是很耗時的，如果要篡改一個區塊，就必須重新計算該區塊後面的所有的區塊的雜湊值，短時間內幾乎做不到。
負載均衡
負載均衡演算法有很多，比如輪訓，隨機，加權輪詢等等。怎麼才能實現一個會話粘滯（同一個客戶端上，在一次會話中的所有請求都路由到同一個伺服器上）的負載均衡呢
最直接的做法就是維護一張對映表，內容是客戶端的IP地址或者會話ID，於伺服器編號的對映關係。客戶端發出的每次請求都要先在對映表中查詢應該路由到哪臺伺服器，然後在請求對應的伺服器。
不過當客戶端很多的時候，對映表會很大，浪費空間。客戶端的上線下線伺服器的擴容都會導致對映失效，維護成本很大。
我們可以通過雜湊演算法，把客戶端IP地址或者會話ID計算雜湊值，把得到的雜湊值跟伺服器列表的大小進行取模運算，最終得到的值就是應該被路由到的伺服器的編號。
資料分片
1、如何統計某個關鍵詞出現的次數
如果我們有1T的資料，裡面記錄了使用者搜尋的關鍵詞，怎麼快速的統計出每個關鍵詞被搜尋的次數。
先對資料進行分片，然後採用多臺機器處理，提高處理速度。
為了提高處理速度，我們使用n臺機器並行處理，從搜尋日誌中一次讀取出每個搜尋關鍵詞，通過雜湊函式計算雜湊值，然後n取模，得到的值就是應該分配到的機器編號
這樣雜湊值相同的關鍵字就會被分配到同一臺機器上，每個機器分別計算出關鍵詞的次數，最後合併起來就是最後結果。
2、如何快速判斷圖片是否存在相簿中
假如又一億張圖片，一臺機器是無法裝下的，這時候就可以給資料分片，然後多機處理。準備n臺機器，每臺機器只維護某一部分圖片對應的散列表。我們每次從相簿中讀取一個圖片，計算唯一標識，然後與機器個數,取模，得到的值就是對應分配的機器標號，然後將這個圖片唯一標識和圖片路徑發往對應的機器構建散列表。
查詢的時候，通過同樣的雜湊演算法計算圖片的唯一標識，然後機器個數n取模，得到的值就是對應機器的編號，然後去該機器中尋找。
分散式儲存
如今的網際網路的資料都是海量的，只能分散式的儲存在不同的機器上，怎麼決定放在哪個機器上呢，跟資料分片一樣，通過雜湊演算法對資料取雜湊值，然後對機器取模，值就是對應機器的編號。
問題：當資料增多，原來的機器無法儲存的時候，就需要加機器了。但是這個時候不僅僅是加機器這麼簡單。
因為比如原來有10臺機器，原來的值是通過10來取模的，當加了一臺機器之後，就是按11取模了，最後分配到的機器是不一樣的。因此所有的資料都要從新計算雜湊值，然後從新搬移到正確的機器上，相當於快取中的資料全部失效，假如以前是直接請求快取，現在就是直接去請求資料庫，資料庫就會被壓垮、
怎麼解決這個問題呢，可以使用一致性雜湊演算法
什麼是一致性雜湊演算法，假如我們有k臺機器資料的雜湊值的範圍是[0,max],我們把整個範圍劃分成m個小區間（m遠大於k），每個機器負責m/k個小區間。當有新的機器加入的時候，就把某幾個小區間的資料從原來的機器中搬移到新的機器中，這樣既不用重新雜湊搬移資料，也保持了哥哥機器上資料的均衡。
注意取模的時候不是根據機臺的個數k而是跟m取。當然取到的數也許不是機臺的編號，這時候就按照順時針來尋找，把資料放到第一個找到的機器上。
當然這樣做也有可能某臺機器上儲存的東西太多，不夠均勻，怎麼辦呢，可以引入虛擬結點的概念，每臺機器分成m/k份，這樣相當於這m個結點上都有一臺小機器了，取模之後就可以直接放到這些小機器上了。這樣就解決了不均勻的問題了。