今天復習了一下HashMap的部分，寫一篇博客記錄一下今天學習內容
雖然之前學習過，但由于后來沒怎么使用過而且也沒復習基本忘得差不多了
在Java的HashMap中，高效存儲鍵值對的核心在于哈希算法和索引定位。本文將結合源碼逐步拆解存儲流程，并給出代碼示例。
?核心流程概述
- 擾動函數處理Key?通過擾動函數優化Key的哈希值，減少碰撞
- 存儲哈希值?計算后的哈希值存入Node對象的
hash字段 - 計算桶下標?用
(n-1) & hash定位數組索引（n為數組長度） - 存入數據結構?根據下標存入數組（或鏈表/紅黑樹）
?源碼級分步解析（基于JDK 17）
① 擾動函數與哈希計算
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}- 作用：將原始哈希碼的高16位與低16位異或
- 目的：讓高位參與運算，解決低位相同導致的哈希碰撞
- 結果：擾動后的哈希值存儲在Node的
hash字段
② Node對象結構
static class Node<K,V> implements Map.Entry<K,V> {final int hash; // 存儲擾動計算后的哈希值final K key;V value;Node<K,V> next; // 鏈表結構指針
}③ 索引定位公式
// 在putVal方法中：
int index = (n - 1) & hash;n-1：當前數組長度減1（如長度16→15，二進制0...01111）- 位與運算：高效實現取模運算，
hash % n等價于(n-1) & hash
④ 完整put流程偽代碼
final V putVal(int hash, K key, V value) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 1. 首次使用觸發初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 2. 計算桶下標 (核心公式)i = (n - 1) & hash;// 3. 處理碰撞情況if ((p = tab[i]) == null) tab[i] = newNode(hash, key, value); // 無碰撞直接存else {// 碰撞后遍歷鏈表/紅黑樹if (p.hash == hash && ...)// 更新已存在key的值else {// 鏈表新增節點if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash); // 鏈表轉紅黑樹}}
}舉個🌰 實戰示例與驗證
import java.util.*;public class HashMapDemo {public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<>(16); // 初始容量16// 存儲鍵值對 "A":1map.put("A", 1);// 手動驗證存儲過程String key = "A";// 1. 原始哈希碼int hashCode = key.hashCode(); System.out.println("原始哈希碼: 0x" + Integer.toHexString(hashCode));// 2. 擾動計算int perturbedHash = hash(key);System.out.println("擾動哈希值: 0x" + Integer.toHexString(perturbedHash));// 3. 計算桶下標 (n=16)int n = 16;int index = (n - 1) & perturbedHash;System.out.println("數組下標: " + index);}// JDK擾動函數實現static int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
}輸出結果：
原始哈希碼: 0x41
擾動哈希值: 0x41 // 小值無高位變化
數組下標: 1 // (16-1)=15: 0b1111 & 0x41=65 → 1?設計原理深度剖析
為什么用位與代替取模？
- 位運算
(n-1) & hash比%效率高10倍以上（實測） - 前提：數組長度必須是2的冪（保證
n-1的二進制全為1）
- 位運算
擾動函數的必要性
原始哈希: 0x1234abcd 和 0x5678abcdn=16時：未擾動 → 兩值低位相同 → 碰撞擾動后 → 高位參與運算 → 低位不同 → 避免碰撞? ? ?3.哈希碰撞策略
最佳實踐建議
- 避免自定義Key哈希碰撞
// 錯誤實現：所有對象返回相同哈希碼@Overridepublic int hashCode() { return 1; } // 導致HashMap退化為鏈表// 正確實現：組合關鍵字段哈希@Overridepublic int hashCode() {return Objects.hash(field1, field2);}- 初始化容量優化
// 預期存儲1000個元素時new HashMap<>(2048); // 避免擴容 (1000/0.75≈1333 → 取2的冪2048)至此，本章的內容結束，后續我會補充一下在高并發情況下HashMap會出現的一些問題? ??
)
