hash學(xué)習(xí)記錄一

什么是Hash函數(shù)

hash函數(shù)，一般翻譯做散列或者直接音譯為哈希，是把任意長度的輸入（又叫做預(yù)映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。

什么是Hash沖突

如果兩個關(guān)鍵字通過hash函數(shù)得到的值是一樣的，就是hash沖突。

什么是Hash表（散列表）

根據(jù)散列函數(shù)和沖突處理將一組關(guān)鍵字分配在連續(xù)的地址空間內(nèi)，并以散列值記錄在表中的存儲位置，這種表就是散列表。

常見的Hash算法：
  1. 直接尋址法

取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H（key）=key或H（key） = a?key + b，其中a和b為常數(shù),?代表運(yùn)算符號（這種散列函數(shù)叫做自身函數(shù)）

  1. 數(shù)字分析法

分析數(shù)字的規(guī)律，利用數(shù)據(jù)的特點來構(gòu)造沖突幾率較低的散列地址。例如人的生日，前面的年很容易重復(fù)，用月和日構(gòu)建散列表沖突的幾率會明顯降低。

  1. 折疊法

將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。

  1. 平方取中法

取關(guān)鍵字平方后的中間幾位作為散列地址。

  1. 隨機(jī)數(shù)法

選擇一隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，通常用于關(guān)鍵字長度不同的場合。

  1. 除留余數(shù)法

取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H（key） = key MOD p， p《=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生同義詞。

現(xiàn)在來思考一下這樣一道題：

  • 題目描述：

提供一組數(shù)據(jù) 1,5,7,6,3,4,8，對這組數(shù)據(jù)進(jìn)行存儲，然后給定一個數(shù)num，請你判斷num是否存在剛才的數(shù)據(jù)集中?

  1. 順序查找法
    最容易想到的方法就是遍歷數(shù)據(jù)，在遍歷的過程中比較當(dāng)前元素是否等于數(shù)num,等于則存在，如果遍歷結(jié)束也沒有找到和num相等的元素，則不存在. 這種方法就是順序查找法，時間復(fù)雜度O(n).
arr = new int[]{1,5,7,6,3,4,8};
for (int m : arr) {
   if (m == num) {
     return "num存在于數(shù)據(jù)集中"
   }
}
return "num不存在于數(shù)據(jù)集中"
  1. 二分查找法
    除此之外，還可以對數(shù)據(jù)進(jìn)行排序，然后進(jìn)行則半查詢（每次比較中間數(shù)據(jù)和num的大?。?，也就是二分查找法，時間復(fù)雜度O(log(n)).
    那么是否存在一種方法，時間復(fù)雜度比上面的兩種方法更低呢，也即是，是否存在一種時間復(fù)雜度為O(1)的方法，可以讓我們直接判斷出num在數(shù)據(jù)中是否存在.

  2. 直接尋址法
    看下面這個數(shù)組，可以看出來，這個該數(shù)組中索引和索引所在元素是相等的，如果我們要判斷數(shù)num是否在數(shù)組中，只需要判斷arr[num]是否等于空就行了，這就是直接尋址法。利用了數(shù)組隨機(jī)索引的特性，時間復(fù)雜度O(1).



    這種方法可以用來解決一些特定問題，例如：限制服務(wù)器內(nèi)存只有100m,給你全國人的年齡文件（一個人的年齡占一行），求出每個年齡都有多少人。
    全國超過10億人的年齡數(shù)據(jù)，肯定是超過100m的，直接加載到內(nèi)存是不行的，我們就可以初始化一個長度為200的數(shù)組nums（最大年齡不可能超過200），讀取文件每次取出一個人的年齡age，nums[age]++;最后輸出數(shù)組即可。
    不過這種方式的缺點也很明顯，就是最大和最小數(shù)之間的差不能過大，例如給定10個隨機(jī)數(shù)，范圍是0到1億之間，還使用這種方式，需要創(chuàng)建一個初始長度1億的數(shù)組，嚴(yán)重的浪費(fèi)空間。

  3. 除留余數(shù)法
    有什么方法可以解決這種最大最小數(shù)差距過大的情況嗎，例如數(shù)據(jù)（1,3,4,5,10002）.如果使用直接尋址法就需要創(chuàng)建一個長度為10002的數(shù)組。這種情況下，我們可以對數(shù)據(jù)進(jìn)行取模，例如上面數(shù)據(jù)個數(shù)5，1 mod 5 = 1,3 mod 5 = 3, 4 mod 5 = 4, 5 mod 5 = 0, 10002 mod 5 = 2; 也就是（1，3，4，0，2）這時候我們只需要創(chuàng)建一個長度為5的數(shù)組nums,然后用nums[m mod 5] = m,存放數(shù)據(jù)即可[5, 1, 10002, 3, 4]。
    現(xiàn)在再來對數(shù)據(jù)（1,3,4,5,10003）使用留余數(shù)法，先進(jìn)行取模運(yùn)算，1 mod 5 = 1, 3 mod 5 = 3, 4 mod 5 = 4, 5 mod 5 = 0, 10003 mod 5 = 3. （1， 3， 4， 0， 3），可以看到3和10003取模的結(jié)果都是3，上面對數(shù)據(jù)求模 (數(shù)據(jù)%空間位置數(shù)) 他就是一個hash算法，只不過這是一種比較普通又簡單的hash 算法。這種情況就稱之為hash沖突。
hash沖突的解決方法
  • 開放尋址法

所有的元素都存放在散列表里，每個表項或包含動態(tài)集合的一個元素或者NIL。當(dāng)查找某個元素時，要系統(tǒng)的檢查所有表項，直到找到所有的元素或者最終查明元素不在表中

所有的元素都存放在散列表里，每個表項或包含動態(tài)集合的一個元素或者NIL。當(dāng)查找某個元素時，要系統(tǒng)的檢查所有表項，直到找到所有的元素或者最終查明元素不在表中

簡單來說就是3 mod 5 = 3,把數(shù)組nums的3號坑位占了，當(dāng)10003 mod 5 = 3,來到3號坑位存放數(shù)據(jù)時，發(fā)現(xiàn)該坑位已經(jīng)被使用，就往后面找還沒有被占的坑位。

  • 拉鏈法

把具有相同散列地址的關(guān)鍵字(同義詞)值放在同一個單鏈表中，稱為同義詞鏈表。有m個散列地址就有m個鏈表，同時用指針數(shù)組T[0..m-1]存放各個鏈表的頭指針，凡是散列地址為i的記錄都以結(jié)點方式插入到以T[i]為指針的單鏈表中。
簡單來說就是3 mod 5 = 3把nums的3號坑位占用了，10003 mod 5 = 3,來到3號坑位存放數(shù)據(jù)時，發(fā)現(xiàn)該坑位已經(jīng)被使用,也不往后面找了，直接和數(shù)據(jù)3共有這個坑位，HashMap就是使用這種方式解決的hash沖突.


Hash算法的應(yīng)用場景

Hash算法在分布式中間件中得到了廣泛的應(yīng)用，例如集群模式redis的請求路由策略（16384個槽位），ShardingSphere分庫分表鍵的路由策略，nginx的負(fù)載均衡策略等。
主要應(yīng)用場景主要分兩個

  • 負(fù)載均衡
    例如nginx的ip_hash,使用ip_hash可以保證來自同一客戶端的請求由固定的服務(wù)器處理，避免了分布式環(huán)境下session的共享問題，實現(xiàn)了會話粘滯。

  • 分布式存儲
    例如redis請求路由策略，Redis集群將所有數(shù)據(jù)劃分為 16384 個 slots(槽位)，每個節(jié)點負(fù)責(zé)其中一部分槽位。集群默認(rèn)會對 key 值使用 crc16 算法進(jìn)行 hash 得到一個整數(shù)值，然后用這個整數(shù)值對 16384 進(jìn)行取模來得到具體 槽位。HASH_SLOT = CRC16(key) mod 16384

普通Hash算法中存在的問題

我們來看下nginx以ip_hash作為負(fù)載均衡策略時，如果服務(wù)器宕機(jī)或者擴(kuò)容場景下會出現(xiàn)什么情況可以看出來，無論是擴(kuò)容還是縮容，因為服務(wù)器數(shù)量變化，都需要對所有ip進(jìn)行rehash,3臺服務(wù)器時，由server1對客戶端10.13.22.10提供服務(wù)，擴(kuò)容之后由server2提供服務(wù)。擴(kuò)容縮容之后提供對同一客戶端提供服務(wù)的服務(wù)器發(fā)生了變化，并且這種變化的范圍是不可控的，甚至可能rehash之后所有客戶端都路由到其新的目標(biāo)服務(wù)器處理。

如果在真實生產(chǎn)情況下，后臺服務(wù)器很多臺，客戶端也有很多，那么影響是很大的，縮容和擴(kuò)容都會存在這樣的問題，大量用戶的請求會被路由到其他的目標(biāo)服務(wù)器處理，用戶在原來服務(wù)器中的會話都會丟失。


ip_hash擴(kuò)容縮容場景
一致性Hash算法

一致性Hash算法在1997年由麻省理工學(xué)院提出的一種分布式哈希（DHT）實現(xiàn)算法，設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點（Hot Spot）問題，初衷和CARP十分相似。一致性Hash修正了CARP使用的簡單哈希算法帶來的問題，使得分布式哈希（DHT）可以在P2P環(huán)境中真正得到應(yīng)用。

一致性Hash算法的實現(xiàn)方法

和普通hash不同的地方在于，一致性hash定義了一個hash環(huán)的概念，hash環(huán)可以看作是一個由0～（2^32) - 1個元素首尾相連組成的圓環(huán)。再通過hash算法將數(shù)據(jù)處理后映射到環(huán)上。


hash環(huán).png

假如現(xiàn)在我們有三臺服務(wù)器：server0，server1，server2，五個客戶端：client0，client1,client2,client3,client4,client5
現(xiàn)在對server0,server1,server2三臺服務(wù)器ip進(jìn)行Hash函數(shù)運(yùn)算得到指定的key，再散列到hash環(huán)上。


映射服務(wù)器到hash環(huán).png

再對客戶端進(jìn)行hash運(yùn)算，求出key值散列到hash環(huán)。
映射客戶端.png

散列到hash環(huán)上的客戶端，客戶端的請求由該客戶端順時針尋找到的第一個服務(wù)器負(fù)責(zé)處理。
例如圖中client1,client0,client3的請求由server2處理，cilent4的請求由server1處理，client2的請求由server0處理。

服務(wù)器擴(kuò)容與縮容

普通hash取模算法在服務(wù)器增加或者減少的時候，會導(dǎo)致大量客戶端路由到新的目標(biāo)服務(wù)器，導(dǎo)致用戶在原來服務(wù)器中的會話都會丟失或者大量數(shù)據(jù)需要遷移等問題。
在一致性hash增加或者刪除服務(wù)器節(jié)點又是怎樣的呢。

  • 服務(wù)器擴(kuò)容（增加節(jié)點）


    增加server3節(jié)點

    從圖中可以看出來，擴(kuò)容之后順時針尋找路由服務(wù)器，只有client1請求服務(wù)器變成了server3，其他都沒有變化。

  • 服務(wù)縮容（刪除節(jié)點）


    服務(wù)縮容

    當(dāng)服務(wù)server0因為故障宕機(jī)之后，根據(jù)順時針規(guī)則，只有client2的目標(biāo)服務(wù)器由server0變?yōu)榱藄erver1，其他客戶端服務(wù)器的關(guān)系都沒有發(fā)生變化。

從上面的分析可以看出來，一致性hash在服務(wù)器擴(kuò)容時候，只會影響新增節(jié)點hash環(huán)順時針下第一個server的客戶端數(shù)據(jù)，縮容的時候，只會影響原本由宕機(jī)服務(wù)器處理的數(shù)據(jù)。

虛擬節(jié)點

從圖中我們可以發(fā)現(xiàn)一個問題，路由到server1的客戶端只有client2，其他客戶端請求全部路由到了server2服務(wù)器導(dǎo)致負(fù)載不均衡。針對這種情況，一致性hash中引入了虛擬節(jié)點。


“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機(jī)器）在 hash 空間的復(fù)制品（ replica ），一實際個節(jié)點（機(jī)器）對應(yīng)了若干個“虛擬節(jié)點”，這個對應(yīng)個數(shù)也成為“復(fù)制個數(shù)”，“虛擬節(jié)點”在 hash 空間中以hash值排列。
以上圖為例，為server1和server2創(chuàng)建2個虛擬節(jié)點之后再進(jìn)行映射，這里我們將原服務(wù)器的ip加上#1，#2在進(jìn)行hash運(yùn)算，求出key,散列到hash環(huán)。
從圖中可以看到，4個節(jié)點分別散列到了環(huán)的各個位置（如果還是散列不均勻，可以創(chuàng)建更多的虛擬節(jié)點），實際工作中，通過虛擬節(jié)點-實際節(jié)點的映射關(guān)系，將客戶端請求交給實際服務(wù)器處理，例如根據(jù)順時針規(guī)則，client1的請求由server2#2處理，server2#2屬于server2的虛擬節(jié)點，所以client1的請求由server2處理。


實現(xiàn)一致性hash
/**
 * @author xialu
 * @version 1.0
 * @date 2021/7/26 8:25 下午
 */
public class ConsistentHashWithVirtual {

    public static void main(String[] args) {

        /**
         * 服務(wù)器id
         */
        String[] serviceIds = new String[]{"10.55.12.31", "10.19.12.32", "10.11.22.33"};
        SortedMap<Integer, String> map = new TreeMap<>();
        /**
         * 虛擬節(jié)點個數(shù).
         */
        int virtualCount = 3;
        /**
         * 構(gòu)建虛擬節(jié)點
         */
        for (String serviceId : serviceIds) {
            for (int i = 1; i <= virtualCount; i++) {
                String virtualId = serviceId + "#" + i;
                int index = Math.abs(virtualId.hashCode());
                map.put(index, "由虛擬節(jié)點:" + virtualId + " 映射到服務(wù)器: " + serviceId);
            }

        }

        String[] clientIds = new String[]{"13.161.12.01", "60.111.12.12", "109.11.12.23", "9.1.2.23", "130.220.985.101"};
        for (String clientId : clientIds) {

            int index = Math.abs(clientId.hashCode());
            SortedMap<Integer, String> tailMap = map.tailMap(index);
            if (tailMap.isEmpty()) {
                System.out.println("客戶端：" + clientId + " 被路由到服務(wù)器：" + map.get(map.firstKey()));
            } else {
                Integer firstKey = tailMap.firstKey();
                System.out.println("客戶端：" + clientId + " 被路由到服務(wù)器：" + tailMap.get(firstKey));
            }
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容