最近公司在招人，我們準備的問題中有一道是關于一緻性hash算法的問題，隻有一些面試者能夠回答上來，而且答的也不是很全面，有的面試者隻是聽說過，有的連聽都沒聽過，下面我把一緻性hash算法整理一下分享給大家
一 .算法背景(作為了解，不在面試範圍)
一緻性雜湊演算法在1997年由麻省理工學院的Karger等人在解決分布式Cache中提出的，設計目标是為了解決網際網路中的熱點(Hot spot)問題，初衷和CARP十分類似。一緻性哈希修正了CARP使用的簡單雜湊演算法帶來的問題，使得DHT可以在P2P環境中真正得到應用
二.應用場景
一緻性Hash用于分布式緩存系統，将Key值映射到具體機器Ip上，并且增加和删除1台機器的資料移動量較小
比如你有 N 個 redis 伺服器(後面簡稱 redis )，那麼如何将一個對象 object 映射到 N 個 redis 上呢，你很可能會采用類似下面的通用方法計算 object 的 hash 值，然後均勻的映射到到 N 個 cache
求餘算法: hash(object)%N
這種通用的計算方法有什麼問題呢？
1. 一個 redis 伺服器 x 宕 掉了，這樣所有映射到 redis x 的對象都會失效，怎麼辦，需要把 redis x 從 redis叢集中移除，這時候 redis伺服器 是 N-1 台le，那麼對應映射公式變成了 hash(object)%(N-1) ；
2.還有一種情況是由于通路量增多，需要添加 redis ，這時候 redis 是 N+1 台，映射公式變成了 hash(object)%(N+1) ；
1 和 2 意味着什麼？這意味着突然之間幾乎所有的 redis緩存都失效了。對于伺服器而言，這是一場災難，所有的通路都會直接沖向背景伺服器，對背景伺服器造成壓力，甚至是背景伺服器癱瘓。
如何解決上面的問題呢？一緻性hash算法就派上用場了
一緻性Hash算法也是使用取模的方法，隻是，剛才描述的取模法是對伺服器的數量進行取模，而一緻性Hash算法是對2^32取模，什麼意思呢？簡單來說，一緻性Hash算法将整個哈希值空間組織成一個虛拟的圓環，如假設某哈希函數H的值空間為0-2^32-1(即哈希值是一個32位無符号整形)，整個哈希環如下
圖檔來自于網絡，如有侵權請聯系作者删除
整個空間按順時針方向組織，圓環的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4、5、6……直到2^32-1，也就是說0點左側的第一個點代表2^32-1， 0和2^32-1在零點中方向重合，我們把這個由2^32個點組成的圓環稱為Hash環。
那麼，一緻性雜湊演算法與上圖中的圓環有什麼關系呢？我們繼續聊，以之前描述的場景為例，假設我們有4台緩存伺服器，node1、node2、node3，node4，那麼，在生産環境中，這4台伺服器肯定有自己的IP位址或主機名，我們使用它們各自的IP位址或主機名作為關鍵字進行哈希計算，使用哈希後的結果對2^32取模，可以使用如下公式示意
hash(node1的IP位址) % 2^32
通過上面公式算出的計算一定能得到一個0到2^32-1之間的整數，我們就用得出的整數，代表伺服器node1，既然這個整數肯定處于0到2^32-1之間，那麼，上圖中的hash環上必定有一個點與這個整數對應，我們剛才已經說過了，使用這個整數代表伺服器node1，那麼，伺服器node1就可以映射到這個環上了，其他伺服器一次類推即可得到相應的位置。
接下來使用如下算法定位資料通路到相應伺服器： 将資料key使用相同的函數Hash計算出哈希值，并确定此資料在環上的位置，從此位置沿環順時針“行走”，遇到的第一台伺服器就是該資料應該映射到的伺服器，如圖：
圖檔來自網絡，如有侵權請聯系作者删除
三.一緻性hash算法的容錯性和擴充性
我想看了上面的例子大家應該已經了解了一緻性hash的優勢了，如果伺服器node1節點宕掉，那麼object1的資料會根據規則映射到最近的伺服器node3上，同理如果增加一台伺服器那麼影響的也隻是一小部分資料，一小部分資料會跟着規則遷移到新增伺服器上
如上就是我們面試過程中想要得到的回答，今天就整理到這裡了，大家有什麼不同的觀點歡迎評論指正，我是【不愛八阿哥】如果你覺得有用，記得關注我同時把知識分享給大家吧！！