概述
維基百科上的解釋：
Consistent hashing is a special kind of hashing such that when a hash table is resized, only { K/n} K/n keys need to be remapped on average, whereK is the number of keys, and { n} n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.
一致性哈希算法是一種特殊的哈希算法，當(dāng)哈希表槽位的數(shù)量（大行鹕怼）發(fā)生變化時(shí)饶号，平均只會(huì)引起{K/n}個(gè)關(guān)鍵字需要重新映射呀页，其中K是關(guān)鍵字的數(shù)量炭玫，n是哈希表的大小叫挟。而其他哈希算法因?yàn)樯婕暗焦１聿畚粩?shù)量取模（hash(o) mod n）運(yùn)算双炕，如果增加或減少哈希表的大絮獯馈（槽位）袖肥，幾乎所有關(guān)鍵字都需要重新映射咪辱。
一致性哈希算法經(jīng)常運(yùn)用在分布式緩存系統(tǒng)中，映射數(shù)據(jù)到對(duì)應(yīng)的緩存主機(jī)中椎组。
原理
可以這樣理解一致性哈希算法油狂，將所有的可能的hash值組成一個(gè)環(huán)（ring），首尾相接庐杨，先將哈希表的槽位（node选调，也就是分布式緩存系統(tǒng)中的主機(jī)）取hash值，在環(huán)中定好位置灵份。如下圖所示：
如果有數(shù)據(jù)對(duì)象需要被緩存仁堪，計(jì)算出該對(duì)象的哈希值后，在該環(huán)中找到比它哈希值大且最近的node填渠，這個(gè)node就是該對(duì)象的緩存主機(jī)弦聂。如下圖所示，B是1對(duì)象的緩存主機(jī)：
增加節(jié)點(diǎn)
假設(shè)有如下圖的哈希環(huán)氛什，對(duì)象8分配到A莺葫，對(duì)象1、4枪眉、6捺檬、7被分配到B，對(duì)象2贸铜、3被分配到C：
如果此時(shí)加入另一臺(tái)主機(jī)D堡纬，其哈希的位置在B和A之間聂受，那么在系統(tǒng)中，只要重新計(jì)算對(duì)象6的哈希值烤镐，將其映射到D蛋济，其余對(duì)象的映射不需要重新計(jì)算：
刪除節(jié)點(diǎn)
如果現(xiàn)在主機(jī)C宕機(jī)無(wú)法連接，在系統(tǒng)中炮叶，也只要重新計(jì)算對(duì)象2碗旅、3的哈希值，映射到A镜悉，其余對(duì)象的映射也不需要重新計(jì)算：
平衡
假設(shè)以 node 的實(shí)際 hash 值作為其在環(huán)中的位置祟辟，由于這些值并不會(huì)均勻的落在環(huán)上，導(dǎo)致這些 node 所“管轄”的范圍并不平均侣肄，最終結(jié)果是數(shù)據(jù)分布的不平均川尖，從圖 1 可以看出 B 節(jié)點(diǎn)的范圍最大，而 A 節(jié)點(diǎn)的范圍最小茫孔。
解決這種不平衡的方式是引入虛節(jié)點(diǎn) (Partition) ：一個(gè)物理節(jié)點(diǎn)（node）會(huì)分到非常多的虛節(jié)點(diǎn)（Partition），實(shí)際緩存對(duì)象會(huì)被映射到虛節(jié)點(diǎn)上被芳，然后系統(tǒng)根據(jù)虛節(jié)點(diǎn)找到物理節(jié)點(diǎn)缰贝，最后把對(duì)象緩存到物理節(jié)點(diǎn)上。
這樣由虛節(jié)點(diǎn)的大規(guī)模分布畔濒，來(lái)保證物理節(jié)點(diǎn)的“管轄”范圍的均勻分布剩晴。如果不同物理節(jié)點(diǎn)存在不同權(quán)重，可以通過(guò)給高權(quán)重的節(jié)點(diǎn)分配更多的虛節(jié)點(diǎn)來(lái)達(dá)到目的侵状。
參考文檔
https://community.oracle.com/blogs/tomwhite/2007/11/27/consistent-hashing
https://www.codeproject.com/articles/56138/consistent-hashing
