Hash 表的時(shí)間復(fù)雜度為什么是 O(1)

講 Hash 之前，簡(jiǎn)單聊聊數(shù)組(直接尋址表)

數(shù)組

數(shù)組是內(nèi)存中一塊連續(xù)的空間，并且數(shù)組中必須存放相同的類型，所以存放數(shù)組只需要記住 首地址的位置就可以，而且數(shù)組的長(zhǎng)度必須是定長(zhǎng)。

以 int 數(shù)據(jù)類型為例，每個(gè) int 占 4 字節(jié)內(nèi)存空間，所以對(duì)一個(gè)一個(gè)長(zhǎng)度單位為 5 的整形數(shù)組，所占用的字節(jié)為 4*5=20 字節(jié)，知道首地址，數(shù)組每個(gè)元素定長(zhǎng)，可以輕易算出每個(gè)數(shù)據(jù)的內(nèi)存下標(biāo)地址。

+------------+------------+------------+------------+------------+
| arr[0]     | arr[1]     | arr[2]     | arr[3]     | arr[4]     |
+------------+------------+------------+------------+------------+
| 內(nèi)存地址 1  | 內(nèi)存地址 2   | 內(nèi)存地址 3  | 內(nèi)存地址 4  | 內(nèi)存地址 5   |
+------------+------------+------------+------------+------------+

在這個(gè)例子中，arr[0] 存儲(chǔ)在內(nèi)存地址1，arr[1] 存儲(chǔ)在內(nèi)存地址2，依此類推。每個(gè)元素之間的間隔是4個(gè)字節(jié)（一個(gè)整數(shù)的大小）。

這樣，通過首地址和元素的大小，我們可以計(jì)算出數(shù)組中任意元素的內(nèi)存地址。

數(shù)組的首地址假設(shè)為 base_address = 1000，那么：

• arr[0] 的地址是 base_address
• arr[1] 的地址是 base_address + 4
• arr[2] 的地址是 base_address + 8
• arr[3] 的地址是 base_address + 12
• arr[4] 的地址是 base_address + 16

所以只讀取數(shù)組元素的時(shí)候，可以直接通過下標(biāo)，也就是索引進(jìn)行讀取，即我們常講的直接尋址，時(shí)間復(fù)雜度為 O(1). 所以在算法導(dǎo)論中也會(huì)把數(shù)組稱為直接尋址表

隨機(jī)快速讀寫是數(shù)組的一個(gè)特性，在 Java 中有個(gè) 標(biāo)志性接口 RandomAccess 用于表示此類特性，比如我們經(jīng)常用的 ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  .......
}

這也是常講 對(duì)于 ArrayList  來說 通過索引訪問要優(yōu)于通過迭代器訪問。知道索引下標(biāo)后，下標(biāo)乘以元素大小，再加上數(shù)組的首地址，就可以獲得目標(biāo)訪問地址，直接獲取數(shù)據(jù)。通過迭代器方法，需要通過方法先獲取索引，中間多了一步，并且最好指定初始容量，數(shù)組定長(zhǎng)，所以每一次的擴(kuò)容都要進(jìn)行一次數(shù)組拷貝

在數(shù)組的情況下，由于元素是連續(xù)存儲(chǔ)的，序列化過程可以直接將整個(gè)內(nèi)存塊復(fù)制到磁盤或網(wǎng)絡(luò)中，這樣可以減少 CPU 的開銷，提高效率。所以數(shù)組尤其適合于需要高性能數(shù)據(jù)傳輸?shù)膱?chǎng)景。

相比在鏈表中，由于節(jié)點(diǎn)是分散存儲(chǔ)的，序列化時(shí)必須遍歷每一個(gè)節(jié)點(diǎn)，將其值逐個(gè)寫入到連續(xù)的內(nèi)存中，這樣不僅需要更多的計(jì)算時(shí)間，還可能在內(nèi)存分配上引入額外的開銷。

Hash 表

回頭來看 Hash 表，數(shù)組可以直接尋址，但是缺點(diǎn)很明顯，必須定長(zhǎng)，元素大小相等,實(shí)際中使用的時(shí)候，往往可能不知道需要多長(zhǎng)，希望是一個(gè)動(dòng)態(tài)集合。

這個(gè)時(shí)候可以定義一個(gè)很大的數(shù)組，但是存在一種情況，當(dāng)要存放的元素遠(yuǎn)遠(yuǎn)小于定義某個(gè)長(zhǎng)度的數(shù)組的時(shí)候，就會(huì)造成資源浪費(fèi)。

所以我們需要一種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)上面的功能，可以根據(jù)要放的元素動(dòng)態(tài)的定義數(shù)組的大小，這也就是哈希表，算法導(dǎo)論中也叫散列表。

索引計(jì)算

哈希表會(huì)通過哈希函數(shù)把要放的元素轉(zhuǎn)換為一個(gè)哈希值，往往是一個(gè) Int 型 的數(shù)值，如何得到索引，最簡(jiǎn)單的方法就是余數(shù)法，使用 Hash 表的數(shù)組長(zhǎng)度對(duì)哈希值求余， 余數(shù)即為 Hash 表數(shù)組的下標(biāo),使用這個(gè)下標(biāo)就可以直接訪問得到 Hash 表中存儲(chǔ)的數(shù)據(jù)。。每次讀寫元素的時(shí)候會(huì)計(jì)算哈希值得到索引然后讀寫。

因?yàn)楣：瘮?shù)的執(zhí)行時(shí)間是常量，數(shù)組的隨機(jī)訪問也是常量，時(shí)間復(fù)雜度就是 O(1)。

在編程語言中，為了避免哈希沖突，會(huì)對(duì)哈希函數(shù)的數(shù)據(jù)做進(jìn)一步處理，對(duì)于 Java 來講，HashMap 的 hash 方法接收一個(gè) Object 類型的 key 參數(shù)，然后根據(jù) key 的 hashCode() 方法計(jì)算出的哈希值 h。

然后會(huì)執(zhí)行位運(yùn)算 h >>> 16（將 h 的高 16 位右移 16 位），然后將結(jié)果與原始哈希值 h 進(jìn)行異或操作（^），最后返回計(jì)算得到的哈希值。

Java 的 HashSet 也是基于 HashMap 的只是 Val 做了單獨(dú)處理。

下面為 HashMap 的擾動(dòng)函數(shù)

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Object 的 哈希函數(shù)是一個(gè)原生的方法，即由 JVM 提供，可能通過 C 或者 C++ 實(shí)現(xiàn)。

public native int hashCode();

通過一個(gè)具體的例子來解釋 Java 中 HashMap 的 hash 方法是如何工作的，以及為什么通過對(duì)原始哈希值的高 16 位和低 16 位進(jìn)行異或操作可以減少哈希沖突

假設(shè)我們有一個(gè)字符串鍵 "example"，其 hashCode() 方法返回的原始哈希值為 1047298352 一個(gè) int 值.

即4字節(jié)32 位： 0011 1110 0110 1100 1000 0001 0011 0000

原始哈希值：h = 1047298352

• 高 16 位：0011 1110 0110 1100（二進(jìn)制）
• 低 16 位：1000 0001 0011 0000（二進(jìn)制）

右移操作：h >>> 16，高位填0，原來的高位變低位

• 結(jié)果：0000 0000 0000 0000 0011 1110 0110 1100（二進(jìn)制）
• 這個(gè)操作將原始哈希值的高位信息“復(fù)制”到了低位。

異或操作：h ^ (h >>> 16)

• 結(jié)果：1047298352 ^ 15980 = 1047560497（十進(jìn)制）=00111110011011001011111101011100 （二進(jìn)制）
• 異或操作將高位的信息混合到了低位，使得高位的變化能夠影響到低位。

通過對(duì)原始哈希值的高 16 位和低 16 位進(jìn)行異或操作，HashMap 的 hash 方法試圖達(dá)到以下目的：

• 均勻分布：這種混合操作有助于在哈希表中更均勻地分布鍵，因?yàn)楦呶坏淖兓F(xiàn)在能夠影響到低位，從而減少了只依賴低位導(dǎo)致的分布不均。
• 減少?zèng)_突：由于高位信息現(xiàn)在也被考慮在內(nèi)，因此具有相似高位但不同低位的鍵更有可能產(chǎn)生不同的哈希值，從而減少了哈希沖突的可能性。

當(dāng)調(diào)用 putVal 方法插入鍵值對(duì)時(shí)，會(huì)傳入通過 hash 方法計(jì)算得到的哈希值作為 hash 參數(shù),然后計(jì)算索引

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

這里的 n 為數(shù)組的長(zhǎng)度，那么數(shù)組長(zhǎng)度如何確定？

長(zhǎng)度計(jì)算

索引的問題解決了，那么長(zhǎng)度是如何解決的，我們知道既然使用數(shù)組，那么一定是定長(zhǎng)才行

和 ArrayList 類似，在Java中，Hash 表的長(zhǎng)度是有一個(gè)一個(gè)默認(rèn)長(zhǎng)度的，當(dāng)負(fù)載因子超過閾值時(shí)會(huì)自動(dòng)擴(kuò)容，擴(kuò)容同樣涉及數(shù)組拷貝，哈希值計(jì)算。所以一般也需要指定初始容量。

所以 Java 中在創(chuàng)建 HashMap 時(shí)，會(huì)根據(jù)初始容量和負(fù)載因子來確定實(shí)際的對(duì)象數(shù)組大小。需要注意 HashMap 的內(nèi)部實(shí)現(xiàn)會(huì)確保實(shí)際容量為最接近且大于或等于給定初始容量的 2 的冪次方。這樣可以充分利用位運(yùn)算的優(yōu)勢(shì)，提高哈希表的性能。

實(shí)際中指定初始容量后還會(huì)進(jìn)行進(jìn)一步的運(yùn)算，例如，如果初始容量為 16，實(shí)際對(duì)象數(shù)組大小將為 16；如果初始容量為 17，實(shí)際對(duì)象數(shù)組大小將為 32（最接近且大于 17 的 2 的冪次方）。

計(jì)算方式通過下面的函數(shù)：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

獲取到長(zhǎng)度之后，通過下面的方式獲取索引。

index = hash_value & (table_size - 1)

可以看到在 Java 中，這里使用了位運(yùn)算，而不是之前我們講的取模運(yùn)算，

位與運(yùn)算（bitwise AND）和取模運(yùn)算（modulo operation，使用%符號(hào)）都可以用來將哈希值映射到哈希表的索引范圍內(nèi)，但它們的工作原理和適用場(chǎng)景有所不同。

位與運(yùn)算（bitwise AND） ，當(dāng)哈希表的大小是2的冪時(shí)，可以使用位與運(yùn)算來計(jì)算索引，這種方法的優(yōu)點(diǎn)是速度快，因?yàn)樗簧婕耙淮挝贿\(yùn)算。但是，它要求哈希表的大小必須是2的冪。

取模運(yùn)算（modulo operation），取模運(yùn)算可以用于任何大小的哈希表，不僅限于2的冪：

index = hash_value % table_size

這也是上面為什么要容量是2的冪，除法運(yùn)算通常比位運(yùn)算慢，位運(yùn)算可以直接映射到硬件層面操作。

那么位運(yùn)算又是如何計(jì)算出索引的？這里的原理是基于二進(jìn)制的特性以及位運(yùn)算的規(guī)則。

首先，數(shù)組的大小是 2 的冪次方，例如 16（2^4）。當(dāng)數(shù)組大小為 2 的冪次方時(shí)，它的二進(jìn)制表示形式中只有一個(gè)位為 1，其余位為 0。例如，16 的二進(jìn)制表示為 10000。

使用按位與運(yùn)算（&）計(jì)算索引。

對(duì)哈希碼和數(shù)組大小減 1（例如 15，見上面的公式）進(jìn)行按位與運(yùn)算時(shí)，實(shí)際上是在將哈希碼的二進(jìn)制表示中的高位全部置為 0，只保留低位的數(shù)值。這是因?yàn)閿?shù)組大小減 1 的二進(jìn)制表示形式中，所有低位都為 1，而高位都為 0。例如，15 的二進(jìn)制表示為 01111。

使用上面Demo中的數(shù)據(jù)。

0011 1110 0110 1100 1000 0001 0011 0000(2)    1047298352(擾動(dòng)前哈希值)
0011 1110 0110 1100 1011 1111 0101 1100(2)    1047560497(擾動(dòng)后哈希值 h >>> 16)
0000 0000 0000 0000 0000 0000 0000 1111(2)    15(哈希表容量-1)
& ---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0000(2)    0 (擾動(dòng)前計(jì)算的索引)
0000 0000 0000 0000 0000 0000 0000 1100(2)    12(擾動(dòng)后計(jì)算的索引)

通過按位與運(yùn)算，我們可以得到哈希碼的低 4 位（在這個(gè)例子中），這些低 4 位就是我們要找的索引值。這個(gè)過程相當(dāng)于對(duì)哈希碼進(jìn)行模運(yùn)算（取余數(shù)），使用位運(yùn)算來實(shí)現(xiàn)會(huì)更高效。這里也可以看到擾動(dòng)函數(shù)的作用，利用高位影響低位。

在Java 中當(dāng)哈希表的元素個(gè)數(shù)超過容量乘以加載因子（默認(rèn)為0.75）時(shí)，會(huì)觸發(fā)擴(kuò)容，擴(kuò)容會(huì)重新計(jì)算大小，擴(kuò)容后的大小為。newCap = oldCap << 1 ,即左移一位，增加當(dāng)前容量的一倍。

......
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 如果擴(kuò)容后的容量小于最大容量，并且當(dāng)前容量大于等于默認(rèn)初始容量
        oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 將閾值也擴(kuò)容為原來的兩倍
}
....

實(shí)際上在 Java 中，，如果類實(shí)現(xiàn)了哈希方法，會(huì)使用自己覆蓋的哈希方法，如果關(guān)鍵字是字符串，會(huì)使用 BKDR 哈希算法將其轉(zhuǎn)換為自然數(shù)，再，對(duì)它進(jìn)行求余，就得到了數(shù)組下標(biāo)。

下面為 字符串類 String 覆寫的 哈希函數(shù)。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
        }
        return h;
}

哈希沖突

當(dāng)多個(gè)不同的元素通過哈希函數(shù)生成的哈希值后計(jì)算的索引一樣，就會(huì)觸發(fā)哈希沖突。

我們看一個(gè)生產(chǎn)的 Demo，下面為兩個(gè)樓宇編碼，需要批量生成每棟樓房間的鎖號(hào)，這里我們通過樓宇編碼生成哈希值，拼接到鎖號(hào)最前面當(dāng)樓宇標(biāo)識(shí)。

• 西輔樓： RLD836092851942064128
• 西平房： RLD836132304567926784

這里我們有 8 棟樓宇，所以長(zhǎng)度為8.

public static void main(String[] args) {
        String b1 = "RLD836092851942064128";
        String b2 = "RLD836132304567926784";

        int b1i = b1.hashCode() & (8 - 1);
        int b2i = b2.hashCode() & (8 - 1);
        System.out.println(b1.hashCode()+"|  "+b1i);
        System.out.println(b2.hashCode()+"|  "+b2i);

    }

可以看到，雖然哈希值不一樣，但是算完的索引一樣，

-652344316|  4
1275548884|  4

這兩個(gè)字符串都會(huì)落到下標(biāo) 4 中，這就產(chǎn)生了沖突。就會(huì)促發(fā)哈希沖突，解決辦法一般有兩種：

鏈接法（Separate Chaining）：

落到數(shù)組同一個(gè)位置中的多個(gè)數(shù)據(jù)，通過鏈表串在一起。使用哈希函數(shù)查找到這個(gè)位置后，再使用鏈表遍歷的方式查找數(shù)據(jù)。Java 中的哈希表就使用鏈接法解決沖突。在 Java8 之后，鏈表節(jié)點(diǎn)超過8個(gè)自動(dòng)轉(zhuǎn)為紅黑樹，小于6個(gè)會(huì)自動(dòng)轉(zhuǎn)為鏈表。

鏈表法即把沖突的元素放到一個(gè)鏈表里面，鏈表第一個(gè)元素地址放到哈希表索引的元素位置。

所以說最壞的情況下，即所有的元素都哈希沖突，時(shí)間復(fù)雜度為鏈表的時(shí)間復(fù)雜度 O(n).

• 優(yōu)點(diǎn)：

實(shí)現(xiàn)簡(jiǎn)單，容易處理動(dòng)態(tài)擴(kuò)容。

允許負(fù)載因子大于1，能夠處理更多的元素。

可以靈活應(yīng)對(duì)哈希沖突，即使哈希表中的桶很少也能保持性能。

• 缺點(diǎn)：

需要額外的內(nèi)存用于指針存儲(chǔ)，因此每個(gè)桶可能需要額外的空間，這導(dǎo)致內(nèi)存使用不連續(xù)。

在序列化時(shí)，指針和內(nèi)存的不連續(xù)性會(huì)導(dǎo)致效率降低，尤其是在需要將整個(gè)哈希表序列化并存儲(chǔ)到文件時(shí)，可能需要更多的時(shí)間來處理指針和數(shù)據(jù)結(jié)構(gòu)。

空桶可能會(huì)浪費(fèi)空間。

開放尋址法

插入時(shí)若發(fā)現(xiàn)對(duì)應(yīng)的位置已經(jīng)占用，或者查詢時(shí)發(fā)現(xiàn)該位置上的數(shù)據(jù)與查詢關(guān)鍵字不同，開放尋址法會(huì)按既定規(guī)則變換哈希函數(shù)（例如哈希函數(shù)設(shè)為 H(key,i)，順序地把參數(shù) i 加 1），計(jì)算出下一個(gè)數(shù)組下標(biāo)，繼續(xù)在哈希表中探查正確的位置，

• 優(yōu)點(diǎn)：

所有的元素都存儲(chǔ)在數(shù)組中，避免了指針導(dǎo)致的內(nèi)存不連續(xù)問題。

序列化效率較高，可以直接將內(nèi)存中的數(shù)組映射到磁盤（如 Linux 的 mmap 機(jī)制），這對(duì)于大規(guī)模數(shù)據(jù)的備份非常高效。

操作系統(tǒng)的內(nèi)存映射機(jī)制自動(dòng)處理數(shù)據(jù)的同步，但為了保證數(shù)據(jù)一致性和準(zhǔn)確性，可能還需要顯式調(diào)用 msync 來確保內(nèi)存內(nèi)容被寫入磁盤。

• 缺點(diǎn)：

需要考慮負(fù)載因子，如果填充太滿，性能會(huì)顯著下降，特別是插入和刪除操作可能會(huì)退化為線性時(shí)間。

如果哈希表太大，擴(kuò)展時(shí)可能會(huì)涉及到大量數(shù)據(jù)的重新計(jì)算和復(fù)制。

public void put(String key) {
        int index = hash(key);
        while (table[index] != null) { // 線性探測(cè)
            index = (index + 1) % capacity; // 循環(huán)處理
        }
        table[index] = key;
    }

實(shí)際中可能還要做容量檢測(cè)，避免死循環(huán)。在選擇沖突解決策略時(shí)，需要綜合考慮以下因素：

內(nèi)存使用：如果內(nèi)存連續(xù)性和序列化效率是關(guān)鍵，開放尋址法可能更適合，尤其是在需要高效序列化的情況下。鏈接法雖然更靈活，但可能會(huì)因?yàn)橹羔樅蛢?nèi)存不連續(xù)性導(dǎo)致序列化和備份成本增加。

數(shù)據(jù)大小和存儲(chǔ)：對(duì)于大型哈希表，應(yīng)該關(guān)注內(nèi)存布局和存儲(chǔ)策略，采用分塊、壓縮或稀疏存儲(chǔ)等方式來優(yōu)化序列化過程。

性能和一致性：在使用內(nèi)存映射等技術(shù)時(shí)，確保數(shù)據(jù)的一致性和完整性依然是關(guān)鍵，可能需要額外的同步操作。

如何減少哈希沖突

理論上頻繁發(fā)生哈希沖突時(shí)，會(huì)直接影響時(shí)間復(fù)雜度，所以檢索速度會(huì)急劇降低，通過哪些手段減少?zèng)_突概率？

• 一是調(diào)優(yōu)哈希函數(shù)
• 二是擴(kuò)容

擴(kuò)容

裝載因子（當(dāng)前元素個(gè)數(shù)/數(shù)組容量）越接近于 1，沖突概率就會(huì)越大。不能改變?cè)氐臄?shù)量，只能通過擴(kuò)容提升哈希桶的數(shù)量，減少?zèng)_突。

哈希表的擴(kuò)容會(huì)導(dǎo)致所有元素在新數(shù)組中的位置發(fā)生變化，因此必須在擴(kuò)容過程中同時(shí)保留舊哈希表和新哈希表。擴(kuò)容時(shí)，需要遍歷舊哈希表中的所有元素，并使用新的哈希函數(shù)將它們重新放入合適的新哈希桶中。

上面我們講到 Java  中 HashMap 會(huì)在數(shù)組元素個(gè)數(shù)超過數(shù)組容量的 0.75 進(jìn)行擴(kuò)容， 擴(kuò)容機(jī)制與上面類似，擴(kuò)容后的容量始終為 2的冪，

比如如何 HashMap 的初始容量設(shè)置為 100，那么擴(kuò)容后的容量將按照以下公式計(jì)算：

newCapacity = oldCapacity * 2`

在這種情況下，oldCapacity 是初始容量 100。但是，HashMap 的容量始終是 2 的冪次方，因此實(shí)際的初始容量會(huì)被調(diào)整為大于或等于 100 的最小的 2 的冪次方，即 128（2^7）。

當(dāng) HashMap 需要擴(kuò)容時(shí)，新的容量將是當(dāng)前容量的兩倍。因此，如果初始容量為 128，擴(kuò)容后的新容量將是：

newCapacity = 128 * 2 = 256（2^8）

所以，初始容量設(shè)置為 100，擴(kuò)容后的容量將為 256。這一過程涉及大量數(shù)據(jù)操作，擴(kuò)容是一個(gè)極其耗時(shí)的操作，尤其在元素?cái)?shù)量達(dá)到億級(jí)時(shí)。

所以在初始化的時(shí)候制定容量很有必要，會(huì)避免多次擴(kuò)容，同時(shí)可以考慮其他的擴(kuò)容手段，比如漸進(jìn)式擴(kuò)容和雙緩存技術(shù).

調(diào)優(yōu)哈希函數(shù)

上面我們講到 Java 中 String 類通過 BKDR 哈希算法計(jì)算哈希值，這里的 31 為基數(shù)，哈希函數(shù)為什么基數(shù)必須是素?cái)?shù)，歡迎小伙伴們留言討論 ^_^

它的計(jì)算量很?。簄*31 ，實(shí)際上可以通過先把 n 左移 5 位，再減去 n 的方式替換，即（n*31 == n<<5 - n），因?yàn)槔碚撋衔贿\(yùn)算通常比乘法運(yùn)算更快

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = n<<5 - n + val[i];
            }
            hash = h;
        }
        return h;
    }

也可以在除以一個(gè)質(zhì)數(shù)，這里 prime 是一個(gè)大質(zhì)數(shù)，用于減少哈希沖突。

public class BKDRHash {
    private static final int BASE = 31; // 基數(shù)
    private static final int PRIME = 1000000007; // 質(zhì)數(shù)

    public static int hash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash * BASE + str.charAt(i)) % PRIME;
        }
        return hash;
    }
}

也可以使用其他的哈希算法，或者雙重哈希處理，在分布式場(chǎng)景通過 一致性哈希 來處理數(shù)據(jù)的均勻分布,分散數(shù)據(jù)，降低局部密度，提交分布均勻性，減少?zèng)_突的概率。

一致性哈希（Consistent Hashing）算法

分布式系統(tǒng)中數(shù)據(jù)分布和負(fù)載均衡會(huì)經(jīng)常使用一種叫 一致性哈希（Consistent Hashing）的技術(shù)。用于解決在集群節(jié)點(diǎn)變化（如添加或移除節(jié)點(diǎn)）時(shí)，如何最小化數(shù)據(jù)遷移的問題(Ceph,Redis )。以及在網(wǎng)絡(luò)協(xié)議層流量負(fù)載均衡如何選擇合適的后端節(jié)點(diǎn)(haproxy)。

一致性哈希由 哈希環(huán)，數(shù)據(jù)映射，負(fù)載均衡 組成

哈希環(huán)：

一致性哈希將整個(gè)哈希值空間視為一個(gè)虛擬的環(huán)。每個(gè)節(jié)點(diǎn)（如服務(wù)器）和數(shù)據(jù)項(xiàng)（如緩存中的數(shù)據(jù)）都通過哈希函數(shù)映射到這個(gè)環(huán)上。

比如 Redis Cluster 將整個(gè)數(shù)據(jù)集劃分為 16384 個(gè)哈希槽。每個(gè)鍵通過哈希函數(shù)（CRC16）計(jì)算出一個(gè)哈希值，然后對(duì) 16384 取模，得到該鍵對(duì)應(yīng)的哈希槽。每個(gè)節(jié)點(diǎn)負(fù)責(zé)一部分哈希槽。

節(jié)點(diǎn)和數(shù)據(jù)映射：

節(jié)點(diǎn)和數(shù)據(jù)項(xiàng)都被哈希到這個(gè)環(huán)上。數(shù)據(jù)項(xiàng)被存儲(chǔ)在順時(shí)針方向的第一個(gè)節(jié)點(diǎn)上。例如，如果數(shù)據(jù)項(xiàng) A 被哈希到位置 x，而節(jié)點(diǎn) N1 在 x 的順時(shí)針方向上，那么 A 就存儲(chǔ)在 N1 上。

負(fù)載均衡：

通過將數(shù)據(jù)均勻地分布在環(huán)上，可以實(shí)現(xiàn)負(fù)載均衡。即使添加或刪除節(jié)點(diǎn)，也只會(huì)影響到少量數(shù)據(jù)項(xiàng)的遷移?？傮w的哈希容量不變，所以計(jì)算完的哈希值不會(huì)變，只是對(duì) Hash 空間細(xì)劃。

一致性哈希的優(yōu)勢(shì)

最小化數(shù)據(jù)遷移：當(dāng)節(jié)點(diǎn)加入或離開時(shí)，只需重新映射少量數(shù)據(jù)項(xiàng)，而不是重新分配所有數(shù)據(jù)。這使得系統(tǒng)在擴(kuò)展或縮減時(shí)更為高效。

動(dòng)態(tài)擴(kuò)展：系統(tǒng)可以在不影響現(xiàn)有數(shù)據(jù)的情況下動(dòng)態(tài)擴(kuò)展，增加新的節(jié)點(diǎn)或移除舊的節(jié)點(diǎn)。

• 當(dāng)需要增加新的節(jié)點(diǎn)時(shí)，只需要將新節(jié)點(diǎn)插入到環(huán)中的適當(dāng)位置，并將原節(jié)點(diǎn)的一部分?jǐn)?shù)據(jù)（即一部分哈?？臻g）遷移到新節(jié)點(diǎn)上。
• 同樣地，當(dāng)需要移除節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)可以遷移到其順時(shí)針方向的下游節(jié)點(diǎn)上

容錯(cuò)性：一致性哈希能夠容忍節(jié)點(diǎn)的故障，數(shù)據(jù)可以在節(jié)點(diǎn)故障后快速恢復(fù)。

實(shí)現(xiàn)步驟

1. 選擇哈希函數(shù)：選擇一個(gè)合適的哈希函數(shù)，將節(jié)點(diǎn)和數(shù)據(jù)項(xiàng)映射到哈希環(huán)上。
2. 構(gòu)建哈希環(huán)：使用哈希函數(shù)生成節(jié)點(diǎn)和數(shù)據(jù)項(xiàng)的哈希值，并將它們放置在環(huán)上。
3. 數(shù)據(jù)存儲(chǔ)：當(dāng)存儲(chǔ)數(shù)據(jù)時(shí)，計(jì)算數(shù)據(jù)項(xiàng)的哈希值，并在環(huán)上找到順時(shí)針方向的第一個(gè)節(jié)點(diǎn)，將數(shù)據(jù)存儲(chǔ)在該節(jié)點(diǎn)上。
4. 節(jié)點(diǎn)變動(dòng)：當(dāng)節(jié)點(diǎn)加入或離開時(shí)，重新計(jì)算受影響的數(shù)據(jù)項(xiàng)，進(jìn)行必要的遷移。

以下是一個(gè)簡(jiǎn)單的一致性哈希的 Python 示例：

import hashlib
class ConsistentHashing:
    def __init__(self):
        self.ring = {} #鍵和節(jié)點(diǎn)的映射
        self.sorted_keys = [] # 哈希環(huán)，于存儲(chǔ)已經(jīng)排序好的哈希鍵值
        self.nodes_with_weights = {}  # 用于存儲(chǔ)節(jié)點(diǎn)及其權(quán)重信息

    def _hash(self, key):
        """
        對(duì)給定的鍵進(jìn)行哈希處理，返回一個(gè)整數(shù)形式的哈希值。
        :param key: 要進(jìn)行哈希的鍵，可以是節(jié)點(diǎn)名稱或者數(shù)據(jù)項(xiàng)名稱等。
        :return: 整數(shù)形式的哈希值。
        """
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def add_node(self, node, weight=1):
        """
        向哈希環(huán)中添加一個(gè)節(jié)點(diǎn)。
        :param node: 要添加的節(jié)點(diǎn)名稱。
        :param weight: 節(jié)點(diǎn)的權(quán)重，默認(rèn)為1，權(quán)重越高，在哈希環(huán)上對(duì)應(yīng)的副本數(shù)量越多。
        """
        replicas = weight * 3  # 簡(jiǎn)單根據(jù)權(quán)重設(shè)定副本數(shù)量，這里可根據(jù)實(shí)際需求調(diào)整倍數(shù)關(guān)系
        for i in range(replicas):
            key = f"{node}:{i}"
            hashed_key = self._hash(key)
            self.ring[hashed_key] = node
            self.sorted_keys.append(hashed_key)
        self.nodes_with_weights[node] = weight
        self.sorted_keys.sort()

    def remove_node(self, node):
        """
        從哈希環(huán)中刪除一個(gè)節(jié)點(diǎn)。
        :param node: 要?jiǎng)h除的節(jié)點(diǎn)名稱。
        """
        weight = self.nodes_with_weights.get(node, 1)
        replicas = weight * 3
        for i in range(replicas):
            key = f"{node}:{i}"
            hashed_key = self._hash(key)
            del self.ring[hashed_key]
            self.sorted_keys.remove(hashed_key)
        del self.nodes_with_weights[node]

    def get_node(self, key):
        """
        確定一個(gè)數(shù)據(jù)項(xiàng)應(yīng)該映射到哪個(gè)節(jié)點(diǎn)上。
        :param key: 數(shù)據(jù)項(xiàng)的名稱。
        :return: 數(shù)據(jù)項(xiàng)映射到的節(jié)點(diǎn)名稱，如果哈希環(huán)為空則返回 None。
        """
        if not self.ring:
            return None
        hashed_key = self._hash(key)
        for node_key in self.sorted_keys:
            if hashed_key <= node_key:
                return self.ring[node_key]
        # 將數(shù)據(jù)項(xiàng)映射到了哈希環(huán)上第一個(gè)節(jié)點(diǎn)（按照哈希值從小到大排序后的第一個(gè)節(jié)點(diǎn)）        
        return self.ring[self.sorted_keys[0]]

# 示例使用
if __name__ == "__main__":
    ch = ConsistentHashing()

    # 添加節(jié)點(diǎn)及設(shè)置不同權(quán)重
    ch.add_node('Node1', weight=1)
    ch.add_node('Node2', weight=2)
    ch.add_node('Node3', weight=3)

    data_items = ['data1', 'data2', 'data3', 'data4', 'data5', 'data6', 'data7', 'data8', 'data9', 'data10']

    for item in data_items:
        node = ch.get_node(item)
        print(f"{item} 映射到的節(jié)點(diǎn): {node}")

    # 模擬刪除一個(gè)節(jié)點(diǎn)
    ch.remove_node('Node2')

    print("刪除Node2后:")
    for item in data_items:
        node = ch.get_node(item)
        print(f"{item} 映射到的節(jié)點(diǎn): {node}")

輸出結(jié)果，可以看到刪除 Node2 之后，Node3 和 Node1 之前映射的數(shù)據(jù)并有沒有改變，只是原來Node2 的數(shù)據(jù)被映射到了 Node3

data1 映射到的節(jié)點(diǎn): Node3
data2 映射到的節(jié)點(diǎn): Node1
data3 映射到的節(jié)點(diǎn): Node3
data4 映射到的節(jié)點(diǎn): Node3
data5 映射到的節(jié)點(diǎn): Node1
data6 映射到的節(jié)點(diǎn): Node3
data7 映射到的節(jié)點(diǎn): Node2
data8 映射到的節(jié)點(diǎn): Node1
data9 映射到的節(jié)點(diǎn): Node1
data10 映射到的節(jié)點(diǎn): Node2
刪除Node2后:
data1 映射到的節(jié)點(diǎn): Node3
data2 映射到的節(jié)點(diǎn): Node1
data3 映射到的節(jié)點(diǎn): Node3
data4 映射到的節(jié)點(diǎn): Node3
data5 映射到的節(jié)點(diǎn): Node1
data6 映射到的節(jié)點(diǎn): Node3
data7 映射到的節(jié)點(diǎn): Node3
data8 映射到的節(jié)點(diǎn): Node1
data9 映射到的節(jié)點(diǎn): Node1
data10 映射到的節(jié)點(diǎn): Node3