https://time.geekbang.org/column/article/67388
- hash = 哈希 > 散列
哈希算法
將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串
特點：
- 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)；
- 對輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個 Bit，最后得到到Hash值也不同；
- 沖突的概率要小
- 執(zhí)行效率高，對長文本也能快速計算出哈希值
應(yīng)用
安全加密
MD5，SHA
唯一標(biāo)識
e.g. 海量圖庫中搜索一張圖，可以給每個圖片取一個唯一標(biāo)識符（或者信息摘要），將圖像二進(jìn)制碼的一部分通過哈希算法得到這個標(biāo)識。根據(jù)標(biāo)識找到圖片后再和給定圖片進(jìn)行全量對比。
數(shù)據(jù)校驗
e.g. 防止網(wǎng)絡(luò)傳輸過程中數(shù)據(jù)被修改
散列函數(shù)
- 散列函數(shù)對散列沖突的要求較低，因為碰撞了也可以通過開放尋址或者鏈表法解決
- 散列函數(shù)對散列值能否反向解密也不關(guān)心，散列函數(shù)更關(guān)注散列值是否平均
負(fù)載均衡
通過哈希算法，對客戶端 IP 或者會話 ID 計算哈希值然后和服務(wù)器數(shù)量進(jìn)行取模，這樣就可以把同一個IP的請求分給同一個服務(wù)器
數(shù)據(jù)分片
e.g. 1：統(tǒng)計“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)，n臺機(jī)器并行處理，使用哈希分配數(shù)據(jù)到n臺機(jī)器。再把關(guān)鍵詞哈希到機(jī)器。這就是MapReduce的思想
e.g. 2：判斷圖像是否在圖庫
分布式存儲
現(xiàn)在互聯(lián)網(wǎng)面對的都是海量的數(shù)據(jù)、海量的用戶。我們?yōu)榱颂岣邤?shù)據(jù)的讀取、寫入能力，一般都采用分布式的方式來存儲數(shù)據(jù)，比如分布式緩存。我們有海量的數(shù)據(jù)需要緩存，所以一個緩存機(jī)器肯定是不夠的。于是，我們就需要將數(shù)據(jù)分布在多臺機(jī)器上。
該如何決定將哪個數(shù)據(jù)放到哪個機(jī)器上呢？我們可以借用前面數(shù)據(jù)分片的思想，即通過哈希算法對數(shù)據(jù)取哈希值，然后對機(jī)器個數(shù)取模，這個最終值就是應(yīng)該存儲的緩存機(jī)器編號。
但是，如果數(shù)據(jù)增多，原來的 10 個機(jī)器已經(jīng)無法承受了，我們就需要擴(kuò)容了，比如擴(kuò)到 11 個機(jī)器，這時候麻煩就來了。因為，這里并不是簡單地加個機(jī)器就可以了。
原來的數(shù)據(jù)是通過與 10 來取模的。比如 13 這個數(shù)據(jù)，存儲在編號為 3 這臺機(jī)器上。但是新加了一臺機(jī)器中，我們對數(shù)據(jù)按照 11 取模，原來 13 這個數(shù)據(jù)就被分配到 2 號這臺機(jī)器上了。
因此，所有的數(shù)據(jù)都要重新計算哈希值，然后重新搬移到正確的機(jī)器上。這樣就相當(dāng)于，緩存中的數(shù)據(jù)一下子就都失效了。所有的數(shù)據(jù)請求都會穿透緩存，直接去請求數(shù)據(jù)庫。這樣就可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫。
所以，我們需要一種方法，使得在新加入一個機(jī)器后，并不需要做大量的數(shù)據(jù)搬移。這時候，一致性哈希算法就要登場了。
假設(shè)我們有 k 個機(jī)器，數(shù)據(jù)的哈希值的范圍是 [0, MAX]。我們將整個范圍劃分成 m 個小區(qū)間（m 遠(yuǎn)大于 k），每個機(jī)器負(fù)責(zé) m/k 個小區(qū)間。當(dāng)有新機(jī)器加入的時候，我們就將某幾個小區(qū)間的數(shù)據(jù)，從原來的機(jī)器中搬移到新的機(jī)器中。這樣，既不用全部重新哈希、搬移數(shù)據(jù)，也保持了各個機(jī)器上數(shù)據(jù)數(shù)量的均衡。
