更多文章，請關(guān)注我的個人博客：www.ahey.net
引言
哈希算法，多應(yīng)用于多數(shù)框架的底層實現(xiàn)，在JAVA中與其相關(guān)的有HashMap、HashTable等。
首先拋幾個問題
- 都知道Hashmap底層使用了hash（取模）算法，它與一致性hash算法有什么區(qū)別呢？
- 在分布式緩存中，hash算法起了很大的作用，它也是上述提到的取模算法嗎？
- 取模法與一致性哈希算法有什么區(qū)別？
什么是哈希算法
hash即散列，哈希算法又稱散列算法，將任意長度的二進(jìn)制值映射為較短的固定長度的二進(jìn)制值（哈希值），哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式，常用于快速查找和加密算法。
傳統(tǒng)取模法（以Hashmap為例）
HashMap底層結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹。數(shù)組相當(dāng)于一個bucket，在bucket這一層就用到了取模法。
假設(shè)數(shù)組的長度為n，當(dāng)一個Node（key-value）加入時，先計算key的hash值，再通過 （n -1）& hash 的位操作，得到bucket的下標(biāo)。這里的位操作其實就是取模算法 hash % n的優(yōu)化版。這時候問題來了，由于數(shù)組容量必定有限，當(dāng)需要擴(kuò)容（新增Node節(jié)點(diǎn)）時，Hashmap會rehash（重建hash表），可想而知重建會導(dǎo)致大量的key需要遷移并重新計算下標(biāo)。 故Hashmap源碼中提到了要合理設(shè)置初始長度和負(fù)載因子，以“內(nèi)存換性能”的操作來避免rehash。
取模思路如下
假設(shè)數(shù)組初始長度n = 5，增加結(jié)點(diǎn)至n = 6，最終導(dǎo)致全部數(shù)據(jù)都需進(jìn)行遷移，改變下標(biāo)。
換個角度思考，是否可以做到，在擴(kuò)容的時候盡最大化地減少遷移的操作，并且保證原來的key仍在原來的位置（在分布式緩存系統(tǒng)中，這點(diǎn)尤為重要，否則容易引起緩存雪崩等情況）
一致性哈希算法
引自wiki
一致哈希 是一種特殊的哈希算法。在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙/n 個關(guān)鍵字重新映射，其中K是關(guān)鍵字的數(shù)量，n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個槽位的幾乎需要對所有關(guān)鍵字進(jìn)行重新映射。
其實一致性哈希算法也是一種取模法，只不過不直接對服務(wù)器數(shù)量進(jìn)行取模分發(fā)，而是對2^32進(jìn)行取模，以此解決重新散列的問題。
實現(xiàn)原理大致如下
構(gòu)造由2^32個點(diǎn)位組成的環(huán)形hash空間
將服務(wù)器節(jié)點(diǎn)映射到hash空間
將存儲對象映射到hash空間
將對象沿順時針轉(zhuǎn)動，碰到的第一個服務(wù)器節(jié)點(diǎn)，即當(dāng)前對象應(yīng)緩存的節(jié)點(diǎn)
將上述原理概括成描述一致性哈希算法的規(guī)則：環(huán)形空間，節(jié)點(diǎn)映射，對象映射，順時針相遇
它目前已經(jīng)應(yīng)用于AWS Dynamodb高可用 Nosql數(shù)據(jù)庫、Memcached分布式緩存、Nginx負(fù)載均衡等
一致性哈?；诜植际骄彺娴膽?yīng)用
為什么說一致性哈希是一種特殊的哈希算法，可以借助分布式緩存的例子來說明。
假設(shè)現(xiàn)在有三個服務(wù)器節(jié)點(diǎn)A、B、C，三條待緩存的鍵值對數(shù)據(jù)a、b、c。
初始節(jié)點(diǎn)
- 將三個服務(wù)器節(jié)點(diǎn)通過hash(ip地址) % 2^32 取模得到一個整數(shù)值（介于0 ~ 2^32），定位到環(huán)形空間上
- 將三個緩存對象通過hash(key) % 2^32 取模得到一個整數(shù)值（介于0 ~ 2^32），定位到環(huán)形空間上
- 將緩存對象沿順時針“轉(zhuǎn)動”，當(dāng)?shù)谝粋€遇到的服務(wù)器節(jié)點(diǎn)，就是緩存對象對應(yīng)存儲的節(jié)點(diǎn)
如下圖所示，緩存對象a在服務(wù)節(jié)點(diǎn)A上存儲，緩存對象b在服務(wù)節(jié)點(diǎn)B上存儲...
節(jié)點(diǎn)故障
- 假設(shè)此時節(jié)點(diǎn)B出現(xiàn)故障下線了，按照一致性哈希的規(guī)則中的“順時針相遇”，緩存對象b應(yīng)該與服務(wù)節(jié)點(diǎn)C相遇，存儲位置變動，而其他節(jié)點(diǎn)按兵不動，不受影響
新增節(jié)點(diǎn)
- 假設(shè)此時新增一個節(jié)點(diǎn)D，位于A與C之間，如下圖，按照一致性哈希的規(guī)則中的“順時針相遇”可知，所有緩存對象無需再次轉(zhuǎn)動
- 假設(shè)此時新增一個節(jié)點(diǎn)E，位于A與B之間，如下圖，按照一致性哈希的規(guī)則中的“順時針相遇”可知，緩存對象b與服務(wù)節(jié)點(diǎn)E相遇，存儲位置變動
hash環(huán)傾斜
在描述基于分布式緩存的應(yīng)用時，看似一切都很理想化。
但是會遇到一種情況，實際服務(wù)節(jié)點(diǎn)的映射位置可能比較極端，進(jìn)而造成數(shù)據(jù)傾斜，這種情況會導(dǎo)致大多數(shù)的緩存對象都集中在一個節(jié)點(diǎn)，失去了哈希算法存在的意義。
虛擬節(jié)點(diǎn)
hash算法無法保證絕對的平衡，一致性哈希算法容易導(dǎo)致數(shù)據(jù)傾斜，故它又引入了“虛擬節(jié)點(diǎn)”，即實際節(jié)點(diǎn)在hash空間的復(fù)制節(jié)點(diǎn)，兩者關(guān)系為1：n，虛擬節(jié)點(diǎn)在hash空間中以hash值排列
總結(jié)
一致性哈希算法，相較于常規(guī)的取模法，解決了增刪節(jié)點(diǎn)導(dǎo)致的重新散列的問題，基于“環(huán)形空間，節(jié)點(diǎn)映射，對象映射，順時針相遇”的規(guī)則，加上虛擬節(jié)點(diǎn)的引入，很大程度地解決了分布式系統(tǒng)的心結(jié)，故它常用于Nginx負(fù)載均衡、Dynamodb分布式數(shù)據(jù)庫等。
