在 HashMap 中，通過對鍵的哈希值進行處理，能夠將生成的哈希碼映射到 HashMap 內部數組（桶）中的索引位置。

如下圖所示：

這一過程可以通過以下步驟認真分析：

想了解更多map數據結構更多的可參考：HashMap的擴容機制

1、哈希值的生成與處理

如我們之前討論的，第一次會調用 hashCode() 方法來生成一個完整的 32 位整數哈希碼。然后，使用以下代碼對哈希值進行處理：

int h = key.hashCode();
h ^= (h >>> 16);

2、計算桶的索引

經過處理后，哈希值可能會更分散，最后會用于計算桶的索引位置：

int index = h & (n - 1);

2.1 這里的計算方法：

• n 是當前 HashMap 內部數組的長度（即桶的數量）。為了更高效地計算數組索引，我們通常選擇 n 為 2 的冪（例如 16、32、64 等），這允許高效的位操作。
• n - 1 的計算是為了確保采用位與運算來進行取模操作。例如，如果 n 為 16（即 10000），那么 n - 1 為 15（即 01111）。這樣做的好處是通過位與運算能夠快速計算出在數組中的有效索引。

2.2 示例

假設生成的哈希值 h 為 0b11010110110101101010011000111101（即 32 位二進制數），并且 HashMap 的桶數量 n 為 16（也即 index = h & 15）。

計算過程：

• 二進制示例哈希值：11010110110101101010011000111101
• n-1：00000000000000000000000000001111 （即 15 的二進制表示）

進行位與操作：

        11010110110101101010011000111101
  &     00000000000000000000000000001111
  ------------------------------------------
        00000000000000000000000000000101  （結果即為 index）

• 結果 index 是 5，表示該鍵值對應的元素存放在 HashMap 的第 5 個桶（數組索引為 5 的位置）。

3、哈希值總結

• 哈希值處理：通過對原始哈希碼的處理（即與高位信息進行異或），可以確保更均勻的哈希分布，從而減少碰撞的機會。
• 桶的索引計算：使用 h & (n - 1) 技巧使得計算過程高效，將生成的哈希值直接映射到 HashMap 內部數組的有效索引，從而實現快速的鍵值對存儲和檢索。
• 效率：以上步驟都是為了確保在 O(1) 平均情況下能快速訪問 HashMap 中的元素，同時減少由于哈希沖突引起的性能損失。

4、哈希沖突解決方案

拉鏈法（Separate Chaining）和開放尋址法（Open Addressing）是兩種常用的哈希表沖突解決策略。

它們在處理兩個或多個鍵沖突（即哈希函數返回相同索引）時采取不同的策略。

下面是對這兩種方法的詳細介紹及示例：

4.1. 拉鏈法（Separate Chaining）

1.原理

基本思路是為每個哈希表的桶（數組索引）維護一個鏈表（或其他數據結構），用來存儲所有哈希到同一索引位置的鍵值對。當發(fā)生沖突時，新的鍵值對會被追加到這個鏈表中。

2.特點

• 沖突分離：拉鏈法可以有效處理沖突，因為每個桶可以容納多個元素。
• 空間利用率：空間利用率較高，尤其在負載因子較大時。

3.示例

設想一個簡單的哈希表，哈希函數為 h(key) = key mod 5，并且存在以下鍵值對：

• (3, "A")
• (8, "B")
• (13, "C")
• (9, "D")

哈希表的桶數組將如下所示（使用鏈表處理沖突）：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") -> null
Index: 4  -> (8, "B") -> null

當插入鍵 13，計算得到 h(13) = 3，這個鍵會追加到索引 3 的鏈表中：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") -> (13, "C") -> null
Index: 4  -> (8, "B") -> null

4.2. 開放尋址法（Open Addressing）

1.原理

開放尋址法在發(fā)生哈希沖突時，會在哈希表的數組中尋找下一個可用的桶來存儲沖突的元素。

常用的方法包括線性探測、二次探測和雙重哈希等。

2.特點

• 使用數組存儲數據：所有數據都存儲在哈希表的原始數組中，不需要額外的鏈表或其他數據結構。
• 查找時間：在平均情況下，查找時間復雜度與負載因子密切相關，負載因子過高可能導致性能下降。

3.示例

仍然使用相同的哈希函數 h(key) = key mod 5，并且存在以下鍵值對：

• (3, "A")
• (8, "B")
• (9, "D")

假設當前哈希表的索引結構如下：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") 
Index: 4  -> (8, "B") 

當插入鍵 9 時，計算得到 h(9) = 4，但索引 4 已經被占用，因此會采取開放尋址法策略查找下一個可用位置。這個位置是索引 0（線性探測），最終得到如下數據結構：

Index: 0  -> (9, "D")
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") 
Index: 4  -> (8, "B") 

常用的探測方法

1、線性探測（Linear Probing）

• 當發(fā)生沖突時，逐個檢查下一個可用的桶。通過簡單地向后移動（對當前索引加 1）來查找下一個位置。
• 例如，如果索引 ii 已經被占用，就檢查 (i+1)(i+1)， (i+2)(i+2)，...直到找到空桶。

這種方法的實現如下：

public int linearProbe(int hash, int i) {
    return (hash + i) % table.length;
}

2、二次探測（Quadratic Probing）

• 對于每次沖突，使用二次函數（例如，i2i2）的方式查找下一個位置。這有助于減少碰撞和聚集問題。
• 例如，如果索引 ii 已經被占用，就檢查 (i+12)(i+12)，(i+22)(i+22)，(i+32)(i+32)，...直到找到空桶。

實現類似于：

public int quadraticProbe(int hash, int i) {
    return (hash + i * i) % table.length;
}

3、雙重哈希（Double Hashing）

• 兩個不同的哈希函數同時使用，第一次利用主哈希函數獲取初步的索引，若發(fā)生沖突，則根據第二個哈希函數計算步長。這種方法能夠減小聚集問題。
• 例如，如果主哈希函數返回的索引 h1h1，而第二個哈希函數返回 h2h2，那么如果發(fā)生沖突，查找下一個位置的方法為：

public int doubleHash(int hash, int i) {
    return (hash + i * secondHash(key)) % table.length;
}

心得

在開放尋址法中，探測的基礎是通過某種方式計算下一個桶的索引，從而避免沖突并正確處理數據。

每種探測方法（線性、二次、雙重）各有優(yōu)缺點，實際使用時可以根據應用需求、性能和負載因子來選擇合適的探測方式。

總結

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論