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

一 什么是 Hash 沖突

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

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

為了解決 Hash 沖突，有幾種常見的方法：

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

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

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

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

不同的編程語言在面臨這個問題時也都采取了不同策略，例如：

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

小伙伴們需要先熟悉這些解決方案，因為 Redis 中的解決方案無外乎就是這四種方案中的某幾種。

二 Redis 中的 Hash

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

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

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

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

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

• 鏈地址法
• rehash

三 Redis 如何解決 Hash 沖突

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

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

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

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

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

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

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

四 小結(jié)

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

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

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