---

在數據結構的世界里，紅黑樹一直以「自平衡二叉查找樹」的身份備受贊譽。憑借紅黑節點的精妙設計，它能將插入、刪除、查找的時間復雜度穩定控制在 $(\log n)$，成為處理有序數據的經典方案。然而，當業務場景對「快速查找」提出極致要求時，紅黑樹的局限性逐漸顯現 ——我們是否需要一種更直接的數據訪問方式？ 哈希表正是為突破這一困境而生，它用獨特的映射機制顛覆了傳統樹結構的查找邏輯

---

1 紅黑樹的優勢與潛在短板

• 紅黑樹的核心優勢:紅黑樹通過五條嚴格規則（如根黑、葉黑、紅節點無子紅、黑高平衡）維持樹的平衡，確保最壞情況下的操作效率。在需要維護數據有序性的場景（如數據庫索引、任務調度優先級隊列）中，它能高效完成范圍查詢（例如：查找價格在 100-200 元之間的商品）。
• 紅黑樹的性能瓶頸:盡管 $(O(\log n)$ 的復雜度已足夠優秀，但當業務聚焦于 「單鍵快速查找」 時，紅黑樹的比較式搜索顯得冗余：
  • 路徑依賴：每次查找需從根節點沿比較路徑逐層遍歷，即便樹高度可控，仍存在對數級的比較開銷。
  • 有序性代價：為維持樹的平衡與有序，插入 / 刪除時需頻繁調整節點顏色與結構（旋轉操作），額外消耗計算資源。
  • 范圍無關場景：若應用僅需「根據 ID 獲取用戶信息」這類單鍵操作，紅黑樹的有序性反而成了負擔。

2.哈希表：以空間換時間的終極方案

哈希表借助哈希函數（如 MD5、FNV 哈希）將數據鍵值映射為數組索引，實現「鍵→值」的直接訪問。例如，將用戶 ID 通過哈希函數計算后，直接定位到對應數組槽位獲取用戶信息，理論上可將查找復雜度降至 $(O(1))$

2.1 hash 函數

定義：給定一個輸入數據（可以是字符串、數字、文件內容等各種形式的數據），哈希函數會對其進行一系列的計算和轉換，最終生成一個固定長度的輸出值，這個輸出值就是哈希值。例如，對于字符串 “hello”，經過某個哈希函數計算后，可能得到一個 32 位的十六進制數作為哈希值。
特性：

• 確定性：對于相同的輸入數據，哈希函數必須始終返回相同的哈希值。也就是說，無論何時對同一個數據調用哈希函數，得到的結果都是一致的。例如，多次對字符串 “world” 使用同一個哈希函數計算，得到的哈希值應該完全相同。
• 強隨機性 (高效性和均勻分布性):在處理海量文件的哈希計算時，快速的哈希函數可以顯著提高處理速度。理想情況下，哈希函數應該能夠將輸入數據均勻地映射到哈希值的取值范圍內。這樣可以減少哈希沖突（不同的輸入數據得到相同的哈希值的情況）的發生概率
• 單向性：哈希函數是一種單向函數，即從哈希值很難（甚至不可能）反向推導出原始的輸入數據。這一特性在數據存儲和安全領域非常重要，比如存儲用戶密碼時，通常存儲的是密碼的哈希值，而不是原始密碼，這樣即使哈希值被獲取，也無法輕易得到原始密碼。

常用的哈希函數（非密碼學 無需了解實現 只需選擇就行）

• MurmurHash2：計算速度比較快，且質量較好，在眾多非加密哈希算法中是使用較為廣泛的一種。其內部循環使用了乘法和旋轉操作。不過，即使使用隨機化種子實施 MurmurHash2，也容易受到 Hash DoS 攻擊，通過差分密碼分析能生成導致哈希碰撞的輸入。
• CityHash：計算速度非常快，在處理大規模數據時表現出色。能夠產生高質量的哈希值，哈希沖突的概率較低。它針對不同的平臺和數據類型進行了優化，具有較好的適應性
• SipHash：要解決相近字符串的強隨機分布性問題，能夠抵抗各種形式的哈希沖突攻擊，尤其是對惡意構造的輸入具有很強的抵抗力，安全性較高。計算過程相對復雜，不過在現代硬件上仍然具有較好的性能

2.2 哈希沖突

定義:
哈希函數的作用是把任意長度的輸入數據轉化為固定長度的哈希值。哈希沖突指的是當兩個或多個不同的輸入數據，經過同一個哈希函數計算后，得到了相同的哈希值。可以用數學公式來表示：若有輸入數據 $x_1$ 和 $x_2$，且 $x_1\ne x_2$，但經過哈希函數 H 計算后，$(H(x_1)=H(x_2))$，這種情況就屬于哈希沖突。
負載因子：數組存儲元素的個數 / 數據長度；用來形容散列表的存儲密度；負載因子越小，沖突越小，負載因子越大，沖突越大；

2.3 哈希沖突解決

2.3.1 擴容

負載因子達到閾值：負載因子是指哈希表中已存儲元素的數量與哈希表大小的比值。當負載因子超過預先設定的閾值（通常為 0.75 或 0.8）時，說明哈希表中元素已經比較密集，哈希沖突的概率增加，此時需要進行擴容。例如，一個哈希表初始大小為 16，當存儲的元素達到 12 個時（負載因子達到 0.75），就可能觸發擴容操作。
擴容操作

• 創建新的哈希表：按照一定的擴容策略，比如將哈希表的大小擴大為原來的兩倍，創建一個新的更大的哈希表。這個新哈希表具有更多的槽位，能夠容納更多的元素，從而降低哈希沖突的概率。
• 重新計算哈希值并復制數據：遍歷原哈希表中的每個元素，使用相同的哈希函數重新計算每個元素在新哈希表中的哈希值，并將其插入到新哈希表的相應位置。由于哈希表大小發生了變化，元素的哈希值在新哈希表中的分布也會不同，所以需要重新計算和分配位置。

和string以及vector擴容 差不多

2.3.2 鏈表法

引用鏈表來處理哈希沖突；也就是將沖突元素用鏈表鏈接起來；這也是常用的處理沖突的?式；但是可能出現一種極端情況，沖突元素比較多，該沖突鏈表過長，這個時候可以將這個鏈表轉換為紅黑樹；由原來鏈表時間復雜度 轉換為紅黑樹時間復雜度 ；
普通：

STL中hashmap

將鏈表連起來，方便實現迭代器

2.3.3開放尋址法

定義：當向哈希表中插入一個元素時，通過哈希函數計算出該元素的哈希值，若該位置已被占用（即發生哈希沖突），則按照一定的探測策略在哈希表中尋找下一個空閑的位置來插入該元素。查找元素時，也按照同樣的探測策略在哈希表中進行搜索，直到找到目標元素或確定元素不存在。

操作：

• 線性探測：當發生哈希沖突時，從沖突位置開始，依次向后探測下一個位置，直到找到空閑位置為止
• 二次探測：探測的步長是探測次數的平方。即第一次探測的步長為 12，第二次為 22，第三次為 32，以此類推。例如，發生沖突后，第一次探測的位置是沖突位置 + 12，第二次是沖突位置 + 22，第三次是沖突位置 + 32，若超出哈希表范圍，則對哈希表大小取模。

哈希聚集（這上面都會造成哈希聚集）：當多個元素的哈希值相近時，它們會在哈希表中連續占據相鄰的位置。->增加探測次數和降低插入效率
雙重哈希：：使用兩個哈希函數，第一個哈希函數用于計算初始哈希值，當發生沖突時，使用第二個哈希函數計算一個步長，然后按照這個步長進行探測。(可以解決)

• 步長隨機性：第二個哈希函數 $h_2(key)$ 計算出的步長是基于元素的鍵值生成的，不同元素的步長可能不同。這使得在發生沖突時，元素不會像線性探測那樣總是依次向后或按照固定模式探測，而是以不同的步長跳躍式地尋找空閑位置，從而避免了元素在某個區域過度聚集。
• 均勻分布：通過合理設計兩個哈希函數，可以使元素在哈希表中更均勻地分布。

3 布隆過濾器（哈希升級）

3.1 背景

在計算機科學和信息技術領域，特別是在處理大規模數據集合時，經常需要快速判斷一個元素是否屬于某個集合。例如，在網絡爬蟲中，需要判斷一個 URL 是否已經被訪問過；在數據庫系統中，要快速確定一個記錄是否存在。傳統的數據結構如哈希表，雖然可以實現快速查詢，但在處理大規模數據時，需要消耗大量的內存空間來存儲元素及其相關信息，空間成本較高。

總結：

• 布隆過濾器是一種概率型數據結構，它的特點是高效地插入和查詢，能確定某個字符串一定不存在或者可能存在；
• 布隆過濾器不存儲具體數據，所以占用空間小，查詢結果存在誤差，但是誤差可控，同時不支持刪除操作；

3.2 位圖

位圖（Bit - map），又稱為位向量（Bit - vector）或比特數組（Bit - array），是一種用二進制位來表示和存儲數據的數據結構

原理：位圖中的每個二進制位（bit）都可以表示一個特定元素的某種狀態，通常用 0 表示該元素不存在或不具有某種屬性，用 1 表示該元素存在或具有某種屬性。例如，要表示一個包含 10 個元素的集合，就可以創建一個長度為 10 的位圖，初始時所有位都設置為 0。當集合中添加元素 3 時，就將位圖的第 3 位設置為 1；如果要刪除元素 3，就將第 3 位重新設置為 0。

圖中展示了在 C++ 中利用 byte buf[8] 構建 64bit 位圖的原理
你可以讀一下這個鏈接->內存知識

3.3 布隆操作

• 插入過程：當插入 str1 時，h1(str1)、h2(str1)、h3(str1) 三個哈希函數分別計算出不同的哈希值，這些哈希值對應到位圖中的位置，將這些位置的值從 0 置為 1（圖中藍色箭頭指向的位置 ） 。插入 str2 時同理，h1(str2)、h2(str2)、h3(str2) 計算的位置（圖中紅色箭頭指向 ）也被置為 1 。
• 查詢過程：當查詢某個元素是否在集合中時，用相同的哈希函數計算該元素對應的位圖位置。若這些位置的值都為 1 ，則該元素可能在集合中；只要有一個位置為 0 ，則該元素一定不在集合中。不過由于不同元素哈希值可能重疊（像圖中部分箭頭指向同一位置 ） ，存在誤判情況，即元素實際不在集合中，但位圖對應位置都為 1 。

哈希函數特性與位圖存儲：布隆過濾器使用多個哈希函數將元素映射到位圖的不同位置。位圖大小固定，當插入元素增多，不同元素經哈希函數計算后，映射位置可能重疊。比如有元素 A 和 B，A 先插入，其通過哈希函數計算的位圖位置被標記為 1 ；之后插入 B，若 B 的部分哈希位置與 A 重疊，這些位置早已被標記為 1 。

3.4 應用分析

n – 預期布隆過濾器中元素的個數，如上圖 只有str1和str2 兩個元素 那么 n=2
p – 假陽率，在0-1之間 0.0000001也可以 這個錯判率
m – 位圖所占空間
k – hash函數的個數

n = ceil(m / (-k / log(1 - exp(log§ / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log§) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

網站操作
可以快速算出m k

4 分布式一致性 hash

4.1 背景

• 哈希環構建：將整個哈希值空間組織成一個虛擬的圓環，比如哈希函數取值范圍為 0 - 2^32 - 1 ，這就構成了哈希環。節點（如服務器）和數據都通過哈希函數映射到這個環上。例如，以服務器的 IP 地址或主機名作為關鍵字進行哈希，確定其在環上的位置 ；對數據的鍵進行哈希，也能定位到環上位置。
• 數據映射：當需要定位數據時，使用哈希函數對數據的鍵進行哈希，然后在哈希環上沿順時針方向找到第一個遇到的節點，該數據就由這個節點負責處理。

4.2 hash 偏移

hash 算法得到的結果是隨機的，不能保證服務器節點均勻分布在哈希環上；分布不均勻造成請求訪問不均勻，服務器承受的壓力不均勻

4.3虛擬節點

為了解決哈希偏移的問題，增加了虛擬節點的概念；理論上，哈希環上節點數越多，數據分布越均衡。
假設一個分布式存儲系統中有三個物理節點，其 IP 地址分別為：
Node A：192.168.1.100
Node B：192.168.1.101
Node C：192.168.1.102
為每個物理節點創建多個虛擬節點，例如為每個節點創建三個虛擬節點，通過對 IP 地址和虛擬節點編號進行組合來標識虛擬節點，如下所示：
對于 Node A：

• 虛擬節點 A - 1：192.168.1.100 - 1
• 虛擬節點 A - 2：192.168.1.100 - 2
• 虛擬節點 A - 3：192.168.1.100 - 3

對于 Node B：

• 虛擬節點 B - 1：192.168.1.101 - 1
• 虛擬節點 B - 2：192.168.1.101 - 2
• 虛擬節點 B - 3：192.168.1.101 - 3

對于 Node C：

• 虛擬節點 C - 1：192.168.1.102 - 1
• 虛擬節點 C - 2：192.168.1.102 - 2
• 虛擬節點 C - 3：192.168.1.102 - 3

使用哈希函數對這些虛擬節點的標識（如上述組合的字符串）進行計算，將它們映射到哈希環上。例如，哈希函數可以是一個簡單的取模運算，將虛擬節點的標識轉換為一個在 0 到 2^32 - 1 之間的哈希值，從而確定其在哈希環上的位置。

4.4 數據遷移

增加節點

• 節點哈希計算與定位：對新增節點的標識（如 IP 地址等）進行哈希計算，確定其在哈希環上的位置。
• 數據遷移：從新增節點在哈希環上的位置開始，沿順時針方向找到其前一個節點。將該前一個節點中，哈希值落在新增節點與該前一個節點之間的數據，遷移到新增節點上。

節點 A 的哈希值是 0。節點 B 的哈希值是 100。新節點 C 的哈希值是 50。新增節點 C（50）后，需要將 節點 B（100） 中哈希值落在 (50, 100] 范圍內的數據遷移到 C（50）。
節點 A 的負責范圍不變（仍負責回繞部分 (100, 0]），節點 B 的負責范圍縮小為 (50, 100]，節點 C 負責 (0, 50]。
數據遷移的核心是：僅遷移新增節點與它順時針下一個節點之間的區間數據，其他節點的負責范圍不受影響，從而最小化遷移量。

• 虛擬節點處理：若系統采用了虛擬節點，為新增物理節點創建對應的虛擬節點，并將虛擬節點映射到哈希環上。虛擬節點的數據遷移方式與上述物理節點類似，即把相關虛擬節點順時針方向前一虛擬節點到它之間的數據進行遷移。不過，由于虛擬節點數量較多，數據遷移會更分散，能使數據分布更均勻，減少對單個節點的影響。

刪除節點

• 節點移除：將待刪除節點從哈希環上移除。
• 數據遷移：把被刪除節點上的數據，全部遷移到其在哈希環上順時針方向的下一個節點上。例如，節點 B 被刪除，那么節點 B 上的數據會被遷移到節點 B 順時針方向的下一個節點（假設是節點 C）上。
• 虛擬節點處理：對于要刪除的物理節點所對應的虛擬節點，先將這些虛擬節點從哈希環上刪除。由于虛擬節點對應的數據可能分散在多個物理節點上，所以每個虛擬節點的數據會根據其在哈希環上的位置，遷移到各自順時針方向的下一個虛擬節點對應的物理節點上。這樣可以避免單個物理節點因數據遷移量過大而出現負載過高的情況，提高系統的穩定性。