在 Java 中，HashMap 是一種高效的數據結構，它通過將鍵映射到數組中的索引位置來實現快速的插入和查找。但之前看源碼總是理解到它要hash之后散列到數組中某一個位置，但卻從未深究它究竟怎么散列的，如果不夠散那就意味著hash沖突增加，在這個過程中，散列函數的設計至關重要，特別是右移和異或操作如何幫助減少哈希沖突。

• 沖突對性能的影響
  • 盡管 HashMap 使用鏈表和紅黑樹來處理沖突，但沖突仍然會對性能產生顯著影響：
  • 查詢性能下降：當多個元素存儲在同一個桶中時，查找這些元素的時間復雜度可能退化到 O(n)，而不是理想情況下的 O(1)。
  • 插入性能下降：插入新元素時，如果發生沖突，可能需要遍歷鏈表或調整紅黑樹，導致插入時間復雜度增加。
  • 內存使用效率：沖突頻繁發生時，某些桶可能存儲過多元素，而其他桶則幾乎沒有元素，這種不均勻性可能導致內存浪費。
  • 如果散列性不足，導致大量沖突，HashMap的性能將受到嚴重影響。在最壞的情況下，所有元素都可能映射到同一個桶，形成一個鏈表或紅黑樹，導致查找、插入和刪除操作的時間復雜度退化到 O(n)。

1. HashMap 的基本概念

HashMap 使用一個數組來存儲鍵值對（key-value pairs），每個鍵通過其哈希值計算出一個數組索引。理想情況下，不同的鍵應該映射到不同的索引，以避免哈希沖突。
數組：用于存儲桶（bucket），每個桶可以存儲多個鍵值對。
鏈表或紅黑樹：用于處理哈希沖突，桶中的每個元素可以是鏈表或紅黑樹。

1.1 數據結構

HashMap 的核心數據結構如下：

static class Node<K,V> {final int hash; // 哈希值final K key;    // 鍵V value;        // 值Node<K,V> next; // 下一個節點
}

2. 計算索引位置的流程

2.1 獲取哈希值

當調用 put(key, value) 或 get(key) 方法時，HashMap 首先會通過鍵的 hashCode() 方法獲取哈希值。以下是 put 方法的簡化實現：

public V put(K key, V value) {int hash = (key == null) ? 0 : hash(key);// 計算索引位置int index = indexFor(hash, table.length);// 進行插入操作
}

2.2 散列函數的實現

HashMap 中的散列函數是通過 hash 方法實現的。該方法的實現如下：

static final int hash(int h) {h ^= (h >>> 16); // 右移 16 位并異或return h ^ (h >>> 16); // 再次混合
}

2.3 計算索引位置

在 HashMap 中，索引位置的計算是通過以下方式實現的：

int index = (n - 1) & hash;

這里，n 是數組的長度，hash 是經過處理的哈希值。

3. 右移與異或的作用

3.1 為什么需要右移與異或？

在進行哈希值的計算時，HashMap 使用右移和異或的組合來增強哈希值的隨機性。讓我們通過一個示例來詳細分析這一過程。

3.2 示例分析

假設我們有一個鍵 "key1"，其哈希值為 0xB2690FF0。我們將分析右移和異或如何影響哈希值的混合。

原始哈希值

hash:  10110010 01101001 00001111 11110000  (二進制)

3.3 右移操作

首先，我們進行右移 16 位的操作：

hash >>> 16:
原始: 10110010 01101001 00001111 11110000
結果: 00000000 00000000 10110010 01101001

3.4 異或運算

接下來，我們進行異或運算：

new_hash = hash ^ (hash >>> 16);

計算過程

原始哈希值:  10110010 01101001 00001111 11110000
右移結果:    00000000 00000000 10110010 01101001
-----------------------------------------------
new_hash:     10110010 01101001 10110101 10011001

3.5 高位信息的參與

在計算索引時，HashMap 使用以下公式：

if ((p = tab[i = (n - 1) & hash]) == null) {// 插入新節點
}

這里，(n - 1) 是數組長度減去 1 的值。由于數組長度通常是 2 的冪（例如 16、32、64 等），n - 1 的二進制表示通常以 0 結尾，導致在進行按位與運算時，只有低位信息參與計算。

3.6 按位與的影響

因為按位與運算只有在對應的位都為 1 時結果才為 1，若 hash 的高位信息沒有參與，可能導致多個不同的哈希值映射到同一個索引位置，從而增加哈希沖突的概率。例如：

• 假設 n = 16，即 n - 1 = 15，其二進制為 0000 1111。
• 如果 hash 的高位為 0，低位的變化可能導致多個不同的 hash 值在與 15 進行與運算后得到相同的索引。

3.7 通過右移與異或減少沖突

通過右移和異或，HashMap 能夠打破哈希值的模式，使得高位信息參與到最終的哈希計算中。這種方式使得即使在低位相同的情況下，高位的不同也能影響最終的索引計算，從而有效減少哈希沖突的發生。

4. 減少哈希沖突的原理

4.1 高位與低位的混合

通過右移和異或，HashMap 有效地將高位信息引入低位，增強了哈希值的隨機性，使得相似的鍵在哈希表中更可能映射到不同的索引位置。

4.2 均勻分布

理想的散列函數應該能夠均勻地分布哈希值。如果哈希值的分布不均勻，某些桶可能會存儲過多的元素，從而導致性能下降。通過混合高位和低位，HashMap 提高了哈希值的隨機性，使得鍵值對能夠更加均勻地分布在桶中。

4.3 沖突處理機制

盡管 HashMap 通過上述方法減少了哈希沖突，但仍然可能發生沖突。當多個鍵映射到同一個索引時，HashMap 使用以下兩種方法來處理沖突：

a. 鏈表法

在同一個桶中使用鏈表存儲所有具有相同索引的鍵值對。當發生沖突時，新元素會被添加到鏈表的末尾。

b. 紅黑樹

當某個桶中的元素數量超過一定閾值（如 8），HashMap 會將鏈表轉換為紅黑樹，以提高查找效率。紅黑樹的查找時間復雜度為 O(log n)，比鏈表的 O(n) 更高效。

5. 總結

通過對 HashMap 源碼的分析，我們可以看到它是如何計算索引位置的，以及散列函數在其中的關鍵作用。右移和異或的組合使用有效地混合了哈希值的高位和低位，從而減少了哈希沖突的概率，盡可能的確保了 HashMap 的高效性能。如果對你有幫助歡迎點贊支持。