這是小伙伴之前遇到的一個(gè)面試題，感覺(jué)也是一個(gè)經(jīng)典八股，和大伙分享下。

一 什么是 Hash 沖突

Hash 沖突，也稱為 Hash 碰撞，是指不同的關(guān)鍵字通過(guò) Hash 函數(shù)計(jì)算得到了相同的 Hash 地址。

Hash 沖突在 Hash 表中是不可避免的，因?yàn)?Hash 表的地址空間有限，而可能的關(guān)鍵字?jǐn)?shù)量是無(wú)限的。

為了解決 Hash 沖突，有幾種常見(jiàn)的方法：

1. 鏈地址法（Chaining）：這是最常用的方法之一，每個(gè) Hash 表的桶（bucket）都維護(hù)一個(gè)鏈表，所有散列到同一個(gè)位置的元素都存儲(chǔ)在這個(gè)鏈表中。當(dāng)發(fā)生沖突時(shí)，新元素被添加到該鏈表的末尾。這種方法的優(yōu)點(diǎn)是操作簡(jiǎn)單，插入、查找和刪除的時(shí)間復(fù)雜度為 O(1)，但當(dāng)鏈表長(zhǎng)度較長(zhǎng)時(shí)，查找效率會(huì)降低，并且需要額外的內(nèi)存空間來(lái)存儲(chǔ)鏈表結(jié)構(gòu)。

2. 開(kāi)放尋址法（Open Addressing）：這種方法也稱為閉散列，當(dāng)發(fā)生 Hash 沖突時(shí)，會(huì)順序地查找下一個(gè)可用的數(shù)組位置，直到找到一個(gè)空閑位置為止。開(kāi)放尋址法有幾種變體，包括線性探測(cè)、二次探測(cè)和偽隨機(jī)探測(cè)。線性探測(cè)法是最簡(jiǎn)單的形式，它按順序檢查下一個(gè)空閑位置。二次探測(cè)法在發(fā)生沖突時(shí)，在表的左右進(jìn)行跳躍式探測(cè)。偽隨機(jī)探測(cè)法則使用偽隨機(jī)數(shù)序列來(lái)確定下一個(gè)探查位置。

3. 再 Hash 法（Rehashing）：這種方法同時(shí)構(gòu)造多個(gè)不同的 Hash 函數(shù)，當(dāng)發(fā)生沖突時(shí)，使用第二個(gè) Hash 函數(shù)計(jì)算地址，直到找到一個(gè)不發(fā)生沖突的位置。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。

4. 建立公共溢出區(qū)：將 Hash 表分為基本表和溢出表，將發(fā)生沖突的元素都存放在溢出表中。這種方法可以減少?zèng)_突，但需要額外的存儲(chǔ)空間。

不同的編程語(yǔ)言在面臨這個(gè)問(wèn)題時(shí)也都采取了不同策略，例如：

• Python 采用開(kāi)放尋址。字典 dict 使用偽隨機(jī)數(shù)進(jìn)行探測(cè)。
• Java 采用鏈?zhǔn)降刂?。?JDK1.8 以來(lái)，當(dāng) HashMap 內(nèi)數(shù)組長(zhǎng)度達(dá)到 64 且鏈表長(zhǎng)度達(dá)到 8 時(shí)，鏈表會(huì)轉(zhuǎn)換為紅黑樹(shù)以提升查找性能。
• Go 采用鏈?zhǔn)降刂贰o 規(guī)定每個(gè)桶最多存儲(chǔ) 8 個(gè)鍵值對(duì)，超出容量則連接一個(gè)溢出桶；當(dāng)溢出桶過(guò)多時(shí)，會(huì)執(zhí)行一次特殊的等量擴(kuò)容操作，以確保性能。

小伙伴們需要先熟悉這些解決方案，因?yàn)?Redis 中的解決方案無(wú)外乎就是這四種方案中的某幾種。

二 Redis 中的 Hash

Redis 中的 Hash 數(shù)據(jù)結(jié)構(gòu)在底層使用了兩種不同的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)鍵值對(duì)：

1. 壓縮列表（ziplist）：當(dāng) Hash 表中的元素?cái)?shù)量較少，并且每個(gè)元素的值都小于特定閾值（例如，值的長(zhǎng)度小于 64 字節(jié)）時(shí)，Redis 會(huì)使用壓縮列表來(lái)存儲(chǔ) Hash 表。壓縮列表是一種內(nèi)存高效的數(shù)據(jù)結(jié)構(gòu)，它將所有的元素存儲(chǔ)在一塊連續(xù)的內(nèi)存空間中，這樣可以減少內(nèi)存碎片和內(nèi)存分配次數(shù)。但是，當(dāng)元素?cái)?shù)量增加或者單個(gè)元素的大小超過(guò)閾值時(shí)，壓縮列表的性能會(huì)下降，因?yàn)樗枰l繁地進(jìn)行內(nèi)存重新分配和數(shù)據(jù)復(fù)制。

2. Hash 表（hash table）：當(dāng) Hash 表中的元素?cái)?shù)量較多，或者元素的大小超過(guò)壓縮列表的閾值時(shí)，Redis 會(huì)使用一個(gè)普通的 Hash 表來(lái)存儲(chǔ)數(shù)據(jù)。這個(gè) Hash 表由數(shù)組和鏈表組成，每個(gè)數(shù)組的索引位置上可以存儲(chǔ)多個(gè)元素，這些元素通過(guò)鏈表連接起來(lái)。當(dāng) Hash 表中的元素?cái)?shù)量增加到一定程度時(shí)，Redis 會(huì)進(jìn)行 rehash 操作，即創(chuàng)建一個(gè)新的更大的 Hash 表，并將舊表中的所有元素重新映射到新表中。

Redis 會(huì)根據(jù) Hash 表的大小和元素的數(shù)量自動(dòng)在這兩種數(shù)據(jù)結(jié)構(gòu)之間進(jìn)行切換，以保證性能和內(nèi)存效率。這種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)選擇機(jī)制使得 Redis 的 Hash 數(shù)據(jù)結(jié)構(gòu)既靈活又高效。

從上面的介紹中小伙伴們其實(shí)能看到，Redis 在處理 Hash 沖突的時(shí)候，用到了兩種不同的方案：

• 鏈地址法
• rehash

三 Redis 如何解決 Hash 沖突

根據(jù)前面的介紹，小伙伴們已經(jīng)明白了 Redis 在處理 Hash 沖突的時(shí)候，用到了兩種不同的方案：鏈地址法和 rehash。

第一種鏈地址法大家應(yīng)該是比較熟悉的，我們 Java 里邊早期的 HashMap 就是這樣的，具體數(shù)據(jù)結(jié)構(gòu)如下圖：

不過(guò)鏈地址法有一個(gè)弊端，就是如果出現(xiàn)大量的 key 沖突導(dǎo)致鏈表過(guò)長(zhǎng)，此種情況下會(huì)導(dǎo)致數(shù)據(jù)的檢索效率變慢，這不符合 Redis 高性能的人設(shè)，那怎么辦呢？

為了保持高效，Redis 會(huì)對(duì) Hash 表做 rehash 操作，也就通過(guò)增加 Hash 桶來(lái)減少?zèng)_突。為了 rehash 更高效，Redis 還默認(rèn)使用了兩個(gè)全局 Hash 表，一個(gè)用于當(dāng)前使用，稱為主 Hash 表，一個(gè)用于擴(kuò)容，稱為備用 Hash 表。

具體來(lái)說(shuō)，在 Hash 表擴(kuò)容時(shí)，Redis 首先會(huì)創(chuàng)建一個(gè)新的 Hash 表，該 Hash 表的大小是原有 Hash 表的兩倍，然后將原有 Hash 表中的鍵值對(duì)逐一遷移到新的 Hash 表中。

在遷移過(guò)程中，Redis 會(huì)為每個(gè)被遷移的鍵值對(duì)計(jì)算出其在新 Hash 表中的位置，并將其插入到相應(yīng)的位置上。在遷移完成后，Redis 會(huì)將新 Hash 表作為當(dāng)前 Hash 表，用于存儲(chǔ)新的鍵值對(duì)，同時(shí)釋放舊 Hash 表的內(nèi)存。

由于遷移過(guò)程是逐步進(jìn)行的，因此在遷移過(guò)程中，既可以對(duì)新 Hash 表進(jìn)行寫(xiě)入操作，也可以對(duì)舊 Hash 表進(jìn)行讀取操作，從而保證了 Redis 服務(wù)的正常運(yùn)行。

四 小結(jié)

Redis 通過(guò)鏈地址法解決 Hash 沖突，并通過(guò)漸進(jìn)式 rehash 保持 Hash 表的性能。

鏈地址法實(shí)現(xiàn)簡(jiǎn)單且在負(fù)載因子較低時(shí)性能較好，但在負(fù)載因子較高時(shí)性能會(huì)下降。漸進(jìn)式 rehash 通過(guò)分批次遷移數(shù)據(jù)，避免了 rehash 過(guò)程中的服務(wù)阻塞，從而保持了系統(tǒng)的高性能和高可用性。

通過(guò)以上機(jī)制，Redis 在處理 Hash 沖突時(shí)能夠有效地平衡性能和復(fù)雜度，確保在各種使用場(chǎng)景下都能提供高效的數(shù)據(jù)存儲(chǔ)和檢索服務(wù)。