什么是哈希算法
將任意長度的二進(jìn)制值串，映射為固定長度的二進(jìn)制值串，這個(gè)映射規(guī)則就是哈希算法，映射后的二進(jìn)制值串就是哈希值。
一個(gè)優(yōu)秀的哈希算法，需要滿足下面幾點(diǎn)要求：
- 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)
- 對輸入的數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個(gè)bit，哈希值也要大不同
- 散列沖突的概率要很小，即對于不同的原始數(shù)據(jù)，哈希值相同的概率要很小
- 哈希算法的執(zhí)行效率要盡量高效，針對較長文本，也能快速計(jì)算出哈希值
哈希算法的應(yīng)用
1. 安全加密
經(jīng)常用于加密的哈希算法是：
(1) MD5（Message-Digest Algorithm 消息摘要算法）
(2) SHA（Secure Hash Algorithm 安全散列算法）
對用于加密的哈希算法，比較重要的兩點(diǎn)是：
(1) 很難從哈希值反向推到出原始數(shù)據(jù)
(2) 散列沖突的概率要很小
哈希值越長的算法，散列沖突的概率就越低；越復(fù)雜、越難破解的算法，計(jì)算時(shí)間就越長。
2. 唯一標(biāo)識(shí)
這里舉個(gè)列子：如何在海量的圖庫中，搜索一張圖是否存在？（可能存在名稱相同但圖片內(nèi)容不同，或者圖片內(nèi)容相同但名稱不同）
任何文件在計(jì)算中都可以轉(zhuǎn)成二進(jìn)制串，所以比較笨的辦法，就是直接拿要找的圖片的二進(jìn)制串與圖庫中所有圖片的二進(jìn)制串一一比對。但是每個(gè)圖片小則幾KB，大則幾MB，轉(zhuǎn)成二進(jìn)制串很長，對比起來非常耗時(shí)。
所以比較快的方法就是，給每個(gè)圖片起個(gè)唯一標(biāo)識(shí)（可以從圖片的二進(jìn)制串開頭、中間、尾部各取100個(gè)字節(jié)，放在一起進(jìn)行哈希運(yùn)算），把唯一標(biāo)識(shí)和圖片路徑都存在散列表里。查找的時(shí)候，先通過哈希算法得到這個(gè)圖片的唯一標(biāo)識(shí)，再在散列表中查找是否存在這個(gè)唯一標(biāo)識(shí)。如果不存在，則圖片不在圖庫中，如果存在，從散列表中取出圖片路徑，獲取到圖片內(nèi)容，和要查找的圖片比對，如果完全一樣，則在圖庫中，否則不在。
3. 數(shù)據(jù)校驗(yàn)
BT下載的原理是基于P2P協(xié)議的，從多個(gè)機(jī)器上并行下載一個(gè)2GB的電影，這個(gè)電影會(huì)被分成很多塊，等所有文件塊都下載完畢，再組裝成一個(gè)完整的電影文件。
但網(wǎng)絡(luò)傳輸是不安全的，下載的文件塊可能被修改過，或者不完整等等，最終合并成的電影可能就無法觀看，甚至導(dǎo)致電腦中毒。那怎么校驗(yàn)文件塊的安全、正確、完整呢？
可以對每個(gè)文件塊分別取哈希值，保存在種子文件中。因?yàn)楣Ｋ惴▽?shù)據(jù)很敏感，只要文件塊的內(nèi)容有一丁點(diǎn)改變，得到的哈希值都大不一樣，這樣下載完成后，通過對比文件塊的哈希值，即可得到校驗(yàn)。
4. 散列函數(shù)
散列函數(shù)是散列表的關(guān)鍵，直接決定了散列沖突的概率和散列表的性能。
不過散列函數(shù)對于散列算法沖突概率的要求比較低，而且也不關(guān)心值是否能反向解密，更加關(guān)注的是散列算法的執(zhí)行快慢 和 散列后數(shù)據(jù)是否能均勻分布。
所以散列函數(shù)用的散列算法，一般都比較簡單，比較追求效率。
5. 負(fù)載均衡
通過哈希算法，對客戶端IP地址或會(huì)話ID計(jì)算哈希值，將哈希值與服務(wù)器列表大小進(jìn)行取模運(yùn)算，得到的值就是被路由到的服務(wù)器的編號(hào)。
6. 數(shù)據(jù)分片
假設(shè)有1TB的日志文件，記錄了搜索詞，如何快速統(tǒng)計(jì)每個(gè)搜索詞出現(xiàn)的次數(shù)？
分析：日志文件很大，沒法放到一臺(tái)機(jī)器的內(nèi)存中；只用一臺(tái)機(jī)器處理，時(shí)間會(huì)很長。
所以，要先對數(shù)據(jù)進(jìn)行分片，然后采用多機(jī)處理提高速度。依次讀取日志文件中的搜索詞，通過哈希函數(shù)計(jì)算哈希值，再跟機(jī)器數(shù)取模，得到被分配到的機(jī)器編號(hào)，每個(gè)機(jī)器計(jì)算出搜索次出現(xiàn)次數(shù)，合并后即為最終結(jié)果。
7. 分布式存儲(chǔ)
緩存數(shù)據(jù)分布在多臺(tái)機(jī)器上的時(shí)候，通過哈希函數(shù)對數(shù)據(jù)取哈希值，再與機(jī)器數(shù)取模，得到的值就是數(shù)據(jù)該存儲(chǔ)的機(jī)器編號(hào)。
但是這樣在面對增減緩存機(jī)器時(shí)，緩存中的數(shù)據(jù)大部分會(huì)失效，請求穿透緩存，直接請求數(shù)據(jù)庫，可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫。
想要在增加機(jī)器時(shí)，只需要做少量數(shù)據(jù)遷移，一致性哈希算法 就登場了。
還有很多別的應(yīng)用，就不舉例了。
