既然看到一致性哈希了，那就必然有不一致性哈希，我們平時說的哈希算法都是不一致的哈希，這個不用多說了，大家都熟悉的不能再熟悉了

說不熟悉的拉出去打一頓

哈希一般都是將一個大數字取模然后分散到不同的桶里，假設我們只有兩個桶，有 2、3、4、5 四個數字，那么模 2 分桶的結果就是：

這時我們嫌桶太少要給哈希表擴容加了一個新桶，這時候所有的數字就需要模 3 來確定分在哪個桶里，結果就變成了：

可以看到新加了一個桶后所有數字的分布都變了，這就意味著哈希表的每次擴展和收縮都會導致所有條目分布的重新計算，這個特性在某些場景下是不可接受的。

那一致性哈希是個什么東西呢，就是屬于哈希的一個升級版

在解決分布式系統負載均衡這個問題上，可以使用哈希算法讓固定的一部分請求落到同一臺服務器上，就是根據服務器的個數來進行相應哈希算法的設計，這樣每臺服務器固定處理一部分請求，并且維護這些請求的信息，起到負載均衡的作用

但是呢，如果使用普通的哈希算法就存在一個很大的問題，就是算法的伸縮性很差，當新增或者下線的時候，服務器的個數改變了，用戶ID和服務器的映射關系就會出現大量的失效

這樣就會導致大量的請求出現服務器的遷移，比如我們redis的服務器還是是五臺，經過%5之后映射到相應的服務器上

服務器變成了8臺之后，那就變成了%8，那哈希值大多可能就改變了，這樣導致映射的就不是原來的服務器上了

有服務器宕機的時候，這個負載均衡映射也會改變，服務器恢復之后，負載均衡映射還是會改變

一致性哈希算法

一致性Hash算法也是使用取模的方法，不過，上述的取模方法是對服務器的數量進行取模，而一致性的Hash算法是對2的32方取模。

即，一致性Hash算法將整個Hash空間組織成一個虛擬的圓環，Hash函數的值空間為0 ~ 2^32 - 1(一個32位無符號整型)，整個哈希環如下：

整個圓環以順時針方向組織，圓環正上方的點代表0，0點右側的第一個點代表1，以此類推。

第二步，我們將各個服務器使用Hash進行一個哈希，具體可以選擇服務器的IP或主機名作為關鍵字進行哈希，這樣每臺服務器就確定在了哈希環的一個位置上，比如我們有三臺機器，使用IP地址哈希后在環空間的位置如下圖所示：

現在，我們使用以下算法定位數據訪問到相應的服務器：

將數據Key使用相同的函數Hash計算出哈希值，并確定此數據在環上的位置

從此位置沿環順時針查找，遇到的服務器就是其應該定位到的服務器。

例如，現在有ObjectA，ObjectB，ObjectC三個數據對象，經過哈希計算后，在環空間上的位置如下：

根據一致性算法，Object -> NodeA，ObjectB -> NodeB, ObjectC -> NodeC

一致性Hash算法的容錯性和可擴展性

現在，假設我們的Node C宕機了，我們從圖中可以看到，A、B不會受到影響，只有Object C對象被重新定位到Node A。

所以我們發現，在一致性Hash算法中，如果一臺服務器不可用，受影響的數據僅僅是此服務器到其環空間前一臺服務器之間的數據(這里為Node C到Node B之間的數據)，其他不會受到影響。

如下圖所示：

另外一種情況，現在我們系統增加了一臺服務器Node X，如圖所示：

此時對象ObjectA、ObjectB沒有受到影響，只有Object C重新定位到了新的節點X上。如上所述：一致性Hash算法對于節點的增減都只需重定位環空間中的一小部分數據，有很好的容錯性和可擴展性。

數據傾斜問題

在一致性Hash算法服務節點太少的情況下，容易因為節點分布不均勻面造成數據傾斜(被緩存的對象大部分緩存在某一臺服務器上)問題，如圖特例：

這時我們發現有大量數據集中在節點A上，而節點B只有少量數據。

為了解決數據傾斜問題，一致性Hash算法引入了虛擬節點機制，即對每一個服務器節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛擬節點。

具體操作可以為服務器IP或主機名后加入編號來實現，實現如圖所示：

數據定位算法不變，只需要增加一步：虛擬節點到實際點的映射。

所以加入虛擬節點之后，即使在服務節點很少的情況下，也能做到數據的均勻分布。

既然一致性哈希有這么多好的特性，那為啥主流的哈希都是非一致的呢?

主要一個原因在于查找效率上，普通的哈希查詢一次哈希計算就可以找到對應的桶了，算法時間復雜度是 O(1)，而一致性哈希需要將排好序的桶組成一個鏈表，然后一路找下去，k 個桶查詢時間復雜度是 O(k)，所以通常情況下的哈希還是用不一致的實現。

這里再提一嘴

之所以說一致性哈希有用，這是一個思想，一個方案，我們在平時中很多地方都會涉及到這種思想，比如Redis集群，采用這種方案可以更好的去應對集群節點的動態的增刪，再比如分庫分表，這也是一種思路