更多文章，請關(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é)點）時溅蛉，Hashmap會rehash（重建hash表），可想而知重建會導(dǎo)致大量的key需要遷移并重新計算下標(biāo)他宛。 故Hashmap源碼中提到了要合理設(shè)置初始長度和負(fù)載因子船侧，以“內(nèi)存換性能”的操作來避免rehash。
取模思路如下
假設(shè)數(shù)組初始長度n = 5厅各，增加結(jié)點至n = 6镜撩，最終導(dǎo)致全部數(shù)據(jù)都需進(jìn)行遷移，改變下標(biāo)队塘。
換個角度思考袁梗，是否可以做到，在擴(kuò)容的時候盡最大化地減少遷移的操作憔古，并且保證原來的key仍在原來的位置（在分布式緩存系統(tǒng)中遮怜，這點尤為重要，否則容易引起緩存雪崩等情況）
一致性哈希算法
引自wiki
一致哈希 是一種特殊的哈希算法鸿市。在使用一致哈希算法后锯梁，哈希表槽位數(shù)（大屑赐搿）的改變平均只需要對K/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個點位組成的環(huán)形hash空間
將服務(wù)器節(jié)點映射到hash空間
將存儲對象映射到hash空間
將對象沿順時針轉(zhuǎn)動批狱，碰到的第一個服務(wù)器節(jié)點裸准，即當(dāng)前對象應(yīng)緩存的節(jié)點
將上述原理概括成描述一致性哈希算法的規(guī)則：環(huán)形空間，節(jié)點映射赔硫，對象映射炒俱，順時針相遇
它目前已經(jīng)應(yīng)用于AWS Dynamodb高可用 Nosql數(shù)據(jù)庫、Memcached分布式緩存爪膊、Nginx負(fù)載均衡等
一致性哈先ㄎ颍基于分布式緩存的應(yīng)用
為什么說一致性哈希是一種特殊的哈希算法，可以借助分布式緩存的例子來說明推盛。
假設(shè)現(xiàn)在有三個服務(wù)器節(jié)點A峦阁、B、C耘成，三條待緩存的鍵值對數(shù)據(jù)a榔昔、b、c瘪菌。
初始節(jié)點
- 將三個服務(wù)器節(jié)點通過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é)點诵肛，就是緩存對象對應(yīng)存儲的節(jié)點
如下圖所示，緩存對象a在服務(wù)節(jié)點A上存儲默穴，緩存對象b在服務(wù)節(jié)點B上存儲...
節(jié)點故障
- 假設(shè)此時節(jié)點B出現(xiàn)故障下線了怔檩，按照一致性哈希的規(guī)則中的“順時針相遇”，緩存對象b應(yīng)該與服務(wù)節(jié)點C相遇蓄诽，存儲位置變動珠洗，而其他節(jié)點按兵不動，不受影響
新增節(jié)點
- 假設(shè)此時新增一個節(jié)點D若专，位于A與C之間许蓖，如下圖，按照一致性哈希的規(guī)則中的“順時針相遇”可知，所有緩存對象無需再次轉(zhuǎn)動
- 假設(shè)此時新增一個節(jié)點E膊爪，位于A與B之間自阱，如下圖，按照一致性哈希的規(guī)則中的“順時針相遇”可知米酬，緩存對象b與服務(wù)節(jié)點E相遇沛豌，存儲位置變動
hash環(huán)傾斜
在描述基于分布式緩存的應(yīng)用時，看似一切都很理想化赃额。
但是會遇到一種情況加派，實際服務(wù)節(jié)點的映射位置可能比較極端，進(jìn)而造成數(shù)據(jù)傾斜跳芳，這種情況會導(dǎo)致大多數(shù)的緩存對象都集中在一個節(jié)點芍锦，失去了哈希算法存在的意義。
虛擬節(jié)點
hash算法無法保證絕對的平衡飞盆，一致性哈希算法容易導(dǎo)致數(shù)據(jù)傾斜娄琉，故它又引入了“虛擬節(jié)點”，即實際節(jié)點在hash空間的復(fù)制節(jié)點吓歇，兩者關(guān)系為1：n孽水，虛擬節(jié)點在hash空間中以hash值排列
總結(jié)
一致性哈希算法，相較于常規(guī)的取模法城看，解決了增刪節(jié)點導(dǎo)致的重新散列的問題女气，基于“環(huán)形空間，節(jié)點映射测柠，對象映射炼鞠，順時針相遇”的規(guī)則，加上虛擬節(jié)點的引入鹃愤，很大程度地解決了分布式系統(tǒng)的心結(jié)簇搅，故它常用于Nginx負(fù)載均衡、Dynamodb分布式數(shù)據(jù)庫等软吐。
