前言
哈希算法在程序開發(fā)中的很多地方都能看到他的身影，但是哈希有他的局限性，比如如果兩個key哈希到同一個位置的時候，此時就不好處理。本節(jié)我們介紹一下常規(guī)處理方式。
1. 什么是哈希算法
哈希算法將任意長度的二進(jìn)制值映射為較短的固定長度的二進(jìn)制值，這個小的二進(jìn)制值稱為哈希值。哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表現(xiàn)形式。一般用于快速查找和加密算法。
簡單解釋:哈希(Hash)算法,即散列函數(shù)。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程 沒有解密過程。同時,哈希函數(shù)可以將任意長度的輸入經(jīng)過變化以后得到固定長度的輸出。哈希函數(shù)的這種單向特征和輸出數(shù)據(jù)長度固定的特征使得它可以生成消息或者數(shù)報。
2. 哈希算法在分布式場景中的應(yīng)用場景
Hash算法在很多分布式集群產(chǎn)品中都有應(yīng)?，?如分布式集群架構(gòu)Redis、Hadoop、ElasticSearch，Mysql分庫分表，Nginx負(fù)載均衡等。
2.1 請求的負(fù)載均衡
nginx的ip_hash策略，通過對ip地址或者sessionid進(jìn)?計算哈希值，哈希值與服務(wù)器數(shù)量進(jìn)?取模運算，得到的值就是當(dāng)前請求應(yīng)該被路由到的服務(wù)器編號，如此，同?個客戶端ip發(fā)送過來的請求就可以路由到同?個?標(biāo)服務(wù)器，實現(xiàn)會話粘滯
2.2 分布式存儲
以分布式內(nèi)存數(shù)據(jù)庫Redis為例,集群中有redis1，redis2，redis3 三臺Redis服務(wù)器。那么,在進(jìn)?數(shù)據(jù)存儲時,<key1,value1>數(shù)據(jù)存儲到哪個服務(wù)器當(dāng)中呢？針對key進(jìn)?hash處理hash(key1)%3=index, 使?余數(shù)index鎖定存儲的具體服務(wù)器節(jié)點。
分庫分表的數(shù)據(jù)庫可以同樣用類似邏輯處理。
3. 哈希算法存在的問題
3.1 哈希碰撞
index = HashCode (Key) % Array.length
int index=Math.abs("Hello".hashCode())%10; （0-9）
以上面的demo為例，對象Hash的前提是hashCode()方法，那么HashCode()的作用就是保證對象返回唯一hash值，但當(dāng)兩個對象計算值一樣時，這就發(fā)生了碰撞沖突。
當(dāng)我們對某個元素進(jìn)行哈希運算，得到一個存儲地址，然后要進(jìn)行插入的時候，發(fā)現(xiàn)已經(jīng)被其他元素占用了，其實這就是所謂的哈希沖突，也叫哈希碰撞。
簡單來說，就是兩個不同的待存儲元素，經(jīng)過哈希函數(shù)計算后得到的存儲位置一樣，這樣兩個存儲元素就沖突了。舉個極端的例子，當(dāng)長度為10 的數(shù)組要存儲11個元素的時候，那么哈希碰撞一定會發(fā)生。
3.2 哈希碰撞常見解決方式
3.2.1 開放尋址法
開放尋址法的原理是當(dāng)一個Key通過哈希函數(shù)獲得對應(yīng)的數(shù)組下標(biāo)已被占用時，就尋找下一個空檔位置。
在Java中，ThreadLocal所使用的就是開放尋址法
3.2.2 拉鏈法
數(shù)組的每一個元素不僅是一個Entry對象，還是一個鏈表的頭節(jié)點。每一個Entry對象通過next指針指向它的下一個Entry節(jié)點。當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時，只需要插入到對應(yīng)的鏈表中即可，默認(rèn)next指向null
在Java中，HashMap所使用的就是鏈表法。（這里留意java8中，當(dāng)節(jié)點元素過多的時候，為避免鏈表過長，鏈表會調(diào)整為紅黑樹）
3.3 分布式環(huán)境中的問題
我們知道哈希算法中很重要的兩個因素，一個是哈希表，一個是哈希函數(shù)，哈希函數(shù)的好壞決定數(shù)據(jù)能不能均衡的分布在哈希表中，如果哈希算法不好的話，可能很多值會路由到同一個位置，造成頻繁的哈希碰撞。極端情況會導(dǎo)致哈希表退化為單鏈表。
哈希表的長度也是很重要的因素，如果太短的話，可能會導(dǎo)致很多元素掛在鏈表上，最終退化為單鏈表，如果長度過長的話，會造成內(nèi)存空間的浪費。
在分布式環(huán)境中，常見的場景是服務(wù)的擴(kuò)容縮容，以上面提到的例子為例，比如mysql存儲到瓶頸了，我們需要擴(kuò)容mysql節(jié)點，此時就需要擴(kuò)容。比如雙十一的時候，我們?yōu)榱酥С指嗟恼埱筇幚恚趎ginx后面加了多臺tomcat 服務(wù)器處理請求，在雙十一過后，請求沒那么多，我們可以選擇釋放部分服務(wù)器資源，節(jié)省服務(wù)器成本。
3.4 本質(zhì)
通過上面舉例子可以看到，哈希算法用的好，確實可以提高我們的查詢效率。但是不管是在jdk中的hashmap擴(kuò)容縮容，還是我們分布式場景中的服務(wù)器資源擴(kuò)容縮容，其實本質(zhì)上都是對哈希表的擴(kuò)容縮容。而固定的哈希函數(shù)在擴(kuò)容縮容的時候，需要存儲的元素重新哈希計算元素的在擴(kuò)容后的哈希表中的位置。
那么，有沒有其他辦法，在哈希表擴(kuò)容縮容的時候，不重新計算所有元素位置呢，就是下面的一致性哈希算法。
4. 一致性哈希算法
?先有?條直線，直線開頭和結(jié)尾分別定為為1和2的32次?減1，這相當(dāng)于?個地址，對于這樣?條線，彎過來構(gòu)成?個圓環(huán)形成閉環(huán)，這樣的?個圓環(huán)稱為hash環(huán)。我們把服務(wù)器的ip或者主機(jī)名求hash值然后對應(yīng)到hash環(huán)上，那么針對客戶端?戶，也根據(jù)它的ip進(jìn)?hash求值，對應(yīng)到環(huán)上某個位置，然后如何確定?個客戶端路由到哪個服務(wù)器處理呢？
按照順時針?向找最近的服務(wù)器節(jié)點。
假如將服務(wù)器3下線，服務(wù)器3下線后，原來路由到3的客戶端重新路由到服務(wù)器4，對于其他客戶端沒有影響只是這??部分受影響（請求的遷移達(dá)到了最?，這樣的算法對分布式集群來說?常合適的，避免了?量請求遷移 ）
增加服務(wù)器5之后，原來路由到3的部分客戶端路由到新增服務(wù)器5上，對于其他客戶端沒有影響只是這??部分受影響（請求的遷移達(dá)到了最?，這樣的算法對分布式集群來說?常合適的，避免了?量請求遷移 ）
5. 手寫一致性哈希算法
5.1 普通哈希
package org.wanlong.hash;
/**
* @author wanlong
* @version 1.0
* @description: 普通哈希
* @date 2023/5/23 13:37
*/
public class GeneralHash {
public static void main(String[] args) {
// 定義客戶端IP
String[] clients = new String[]
{"102.178.122.12", "23.243.63.2", "8.8.8.8"};
// 定義服務(wù)器數(shù)量
int serverCount = 3;// (編號對應(yīng)0，1，2)
// hash(ip)%node_counts=index
//根據(jù)index鎖定應(yīng)該路由到的tomcat服務(wù)器
for (String client : clients) {
int hash = Math.abs(client.hashCode());
int index = hash % serverCount;
System.out.println("客戶端：" + client + " 被路由到服務(wù)器編號為："
+ index);
}
}
}
5.2 一致性哈希
package org.wanlong.hash;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* @author wanlong
* @version 1.0
* @description: 一致性哈希
* @date 2023/5/23 13:40
*/
public class ConsistHash {
public static void main(String[] args) {
//step1 初始化：把服務(wù)器節(jié)點IP的哈希值對應(yīng)到哈希環(huán)上
// 定義服務(wù)器ip
String[] tomcatServers = new String[]
{"23.23.0.0", "7.4.3.1", "7.6.6.8", "6.6.7.7"};
SortedMap<Integer, String> hashServerMap = new TreeMap<>();
for (String tomcatServer : tomcatServers) {
// 求出每?個ip的hash值，對應(yīng)到hash環(huán)上，存儲hash值與ip的對應(yīng)關(guān)系
int serverHash = Math.abs(tomcatServer.hashCode());
// 存儲hash值與ip的對應(yīng)關(guān)系
hashServerMap.put(serverHash, tomcatServer);
}
//step2 針對客戶端IP求出hash值
// 定義客戶端IP
String[] clients = new String[]
{"8.8.8.8","709.7.8.1","787.4.2.5"};
for(String client : clients) {
int clientHash = Math.abs(client.hashCode());
//step3 針對客戶端,找到能夠處理當(dāng)前客戶端請求的服務(wù)器（哈希環(huán)上順時針最近）
// 根據(jù)客戶端ip的哈希值去找出哪?個服務(wù)器節(jié)點能夠處理（）
SortedMap<Integer, String> integerStringSortedMap =
hashServerMap.tailMap(clientHash);
if(integerStringSortedMap.isEmpty()) {
// 取哈希環(huán)上的順時針第?臺服務(wù)器
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========>>>>客戶端：" + client + " 被 路由到服務(wù)器：" + hashServerMap.get(firstKey));
}else{
Integer firstKey = integerStringSortedMap.firstKey();
System.out.println("==========>>>>客戶端：" + client + " 被 路由到服務(wù)器：" + hashServerMap.get(firstKey));
}
}
}
}
5.3 一致性哈希包含虛擬節(jié)點
package org.wanlong.hash;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* @author wanlong
* @version 1.0
* @description: 包含虛擬節(jié)點的一致性哈希
* @date 2023/5/23 13:41
*/
public class ConsistentHashWithVirtual {
public static void main(String[] args) {
//step1 初始化：把服務(wù)器節(jié)點IP的哈希值對應(yīng)到哈希環(huán)上
// 定義服務(wù)器ip
String[] tomcatServers = new String[]
{"23.23.0.0", "7.4.3.1", "7.6.6.8", "6.6.7.7"};
SortedMap<Integer, String> hashServerMap = new TreeMap<>();
// 定義針對每個真實服務(wù)器虛擬出來?個節(jié)點
int virtaulCount = 3;
for (String tomcatServer : tomcatServers) {
// 求出每?個ip的hash值，對應(yīng)到hash環(huán)上，存儲hash值與ip的對應(yīng)關(guān)系
int serverHash = Math.abs(tomcatServer.hashCode());
// 存儲hash值與ip的對應(yīng)關(guān)系
hashServerMap.put(serverHash, tomcatServer);
// 處理虛擬節(jié)點
for (int i = 0; i < virtaulCount; i++) {
int virtualHash = Math.abs((tomcatServer + "#" + i).hashCode());
hashServerMap.put(virtualHash, "----由虛擬節(jié)點" + i + "映射過 來的請求：" + tomcatServer);
}
}
//step2 針對客戶端IP求出hash值
// 定義客戶端IP
String[] clients = new String[]
{"8.8.8.8","709.7.8.1","787.4.2.5"};
for (String client : clients) {
int clientHash = Math.abs(client.hashCode());
//step3 針對客戶端,找到能夠處理當(dāng)前客戶端請求的服務(wù)器（哈希環(huán)上順時針最近）
// 根據(jù)客戶端ip的哈希值去找出哪?個服務(wù)器節(jié)點能夠處理（）
SortedMap<Integer, String> integerStringSortedMap =
hashServerMap.tailMap(clientHash);
if (integerStringSortedMap.isEmpty()) {
// 取哈希環(huán)上的順時針第?臺服務(wù)器
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========>>>>客戶端：" + client + " 被 路由到服務(wù)器：" + hashServerMap.get(firstKey));
} else {
Integer firstKey = integerStringSortedMap.firstKey();
System.out.println("==========>>>>客戶端：" + client + " 被 路由到服務(wù)器：" + hashServerMap.get(firstKey));
}
}
}
}
6. 參考文檔
部分圖片案例來源文章來源：http://www.zghlxwxcb.cn/news/detail-460166.html
以上，本人菜鳥一枚，如有錯誤，請不吝指正。文章來源地址http://www.zghlxwxcb.cn/news/detail-460166.html
到了這里，關(guān)于07. 算法之一致性哈希算法介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
