HashMap作為Java集合框架中最重要且最常用的數(shù)據(jù)結(jié)構(gòu)之一，是每一個(gè)Java開發(fā)者都必須掌握的核心知識(shí)點(diǎn)。

它不僅面試高頻，在實(shí)際開發(fā)中也無(wú)處不在。

本文將深入剖析HashMap的底層實(shí)現(xiàn)，揭示其高效性能背后的設(shè)計(jì)哲學(xué)。

一、概述：HashMap的宏觀結(jié)構(gòu)

簡(jiǎn)單來(lái)說(shuō)，HashMap的底層實(shí)現(xiàn)可以概括為 "數(shù)組 + 鏈表 + 紅黑樹" 的復(fù)合結(jié)構(gòu)。它通過(guò)哈希表來(lái)存儲(chǔ)鍵值對(duì)，提供了高效的查找、插入和刪除操作，在理想情況下時(shí)間復(fù)雜度可達(dá)O(1)。

二、核心數(shù)據(jù)結(jié)構(gòu)解析

1. 數(shù)組（桶數(shù)組）

HashMap內(nèi)部維護(hù)了一個(gè)Node<K,V>[] table數(shù)組，這個(gè)數(shù)組被稱為"桶數(shù)組"(bucket array)，是HashMap的骨干結(jié)構(gòu)。數(shù)組的每個(gè)位置稱為一個(gè)"桶"(bucket)，用于存儲(chǔ)鍵值對(duì)。

transient Node<K,V>[] table; // 存儲(chǔ)元素的數(shù)組

2. 鏈表節(jié)點(diǎn)（Node）

每個(gè)數(shù)組元素（桶）實(shí)際上是一個(gè)鏈表的頭節(jié)點(diǎn)。這個(gè)鏈表用于解決**哈希沖突**——當(dāng)不同的鍵通過(guò)哈希函數(shù)計(jì)算出相同的數(shù)組下標(biāo)時(shí)，將它們以鏈表形式存儲(chǔ)在同一個(gè)桶中。

鏈表節(jié)點(diǎn)定義如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // 存儲(chǔ)鍵的哈希值（經(jīng)過(guò)二次處理）
    final K key;       // 鍵，final確保不可變
    V value;           // 值
    Node<K,V> next;    // 指向下一個(gè)節(jié)點(diǎn)的指針
    // 構(gòu)造方法和其他方法...
}

3. 紅黑樹節(jié)點(diǎn)（TreeNode）

在JDK 1.8及之后版本，當(dāng)鏈表過(guò)長(zhǎng)時(shí)，為了優(yōu)化查詢性能，鏈表會(huì)轉(zhuǎn)換為**紅黑樹**。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 紅黑樹父節(jié)點(diǎn)
    TreeNode<K,V> left;    // 左子節(jié)點(diǎn)
    TreeNode<K,V> right;   // 右子節(jié)點(diǎn)
    TreeNode<K,V> prev;    // 前驅(qū)節(jié)點(diǎn)（仍保留鏈表結(jié)構(gòu)）
    boolean red;           // 顏色標(biāo)記
    // 紅黑樹相關(guān)操作方法...
}

三、HashMap的核心工作機(jī)制

1. PUT操作流程（以map.put(key, value)為例）

詳細(xì)步驟說(shuō)明：

1)  計(jì)算哈希值：調(diào)用鍵的hashCode()方法獲得原始哈希值，然后通過(guò)HashMap內(nèi)部的hash()方法進(jìn)行二次處理：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

這里通過(guò)高16位與低16位進(jìn)行異或運(yùn)算，目的是讓哈希值的高位也參與運(yùn)算，從而降低哈希沖突的概率。

2) 計(jì)算數(shù)組下標(biāo)：通過(guò)(n - 1) & hash計(jì)算鍵值對(duì)應(yīng)存放的桶位置（n為數(shù)組長(zhǎng)度）。這等價(jià)于hash % n，但位運(yùn)算效率更高。

3) 處理哈希沖突：

1. 1. 如果桶為空，直接創(chuàng)建新節(jié)點(diǎn)插入
   2. 如果桶不為空，檢查是鏈表還是紅黑樹：

• • • 鏈表：遍歷查找是否存在相同key，存在則覆蓋值，不存在則尾插法插入。插入后若鏈表長(zhǎng)度≥8且數(shù)組容量≥64，則將鏈表轉(zhuǎn)為紅黑樹
    • 紅黑樹：按照紅黑樹的方式插入節(jié)點(diǎn) 

4) 檢查擴(kuò)容：插入后檢查元素總數(shù)是否超過(guò)閾值（容量×負(fù)載因子），超過(guò)則進(jìn)行擴(kuò)容。

2. GET操作流程（以map.get(key)為例）

1. 計(jì)算key的哈希值和數(shù)組下標(biāo)（與PUT操作相同）
2. 定位到具體桶位置：

1. 1. 如果桶為空，返回null
   2. 如果桶不為空，檢查第一個(gè)節(jié)點(diǎn)：

• • • 如果是樹節(jié)點(diǎn)，調(diào)用紅黑樹查找方法
    • 如果是鏈表節(jié)點(diǎn)，遍歷鏈表查找

1. 找到則返回對(duì)應(yīng)值，否則返回null

四、擴(kuò)容機(jī)制：Rehashing的奧秘

擴(kuò)容是HashMap保持高效性能的關(guān)鍵機(jī)制之一。

觸發(fā)條件：當(dāng)元素?cái)?shù)量超過(guò)閾值（threshold = capacity × loadFactor）時(shí)觸發(fā)擴(kuò)容。

擴(kuò)容過(guò)程：

1. 創(chuàng)建新數(shù)組，容量為原來(lái)的2倍（保證容量始終是2的冪）
2. 遍歷舊數(shù)組的每個(gè)桶
3. 將每個(gè)元素重新計(jì)算位置并遷移到新數(shù)組

優(yōu)化技巧：由于新容量是原來(lái)的2倍，元素的新位置要么在原下標(biāo)i，要么在原下標(biāo)i + oldCap。只需判斷(e.hash & oldCap) == 0即可確定位置，無(wú)需重新計(jì)算哈希值。

五、關(guān)鍵參數(shù)與優(yōu)化策略

為什么選擇8作為樹化閾值？

這是基于統(tǒng)計(jì)學(xué)泊松分布的設(shè)計(jì)決策。在理想的哈希函數(shù)下，一個(gè)桶中鏈表長(zhǎng)度達(dá)到8的概率極低（小于千萬(wàn)分之一）。這個(gè)閾值是一種防止極端情況下性能急劇下降的保護(hù)措施，而非常態(tài)。

六、使用建議與最佳實(shí)踐

1. 設(shè)置合適的初始容量：根據(jù)預(yù)估元素?cái)?shù)量設(shè)置初始大小，避免頻繁擴(kuò)容

// 預(yù)估存儲(chǔ)1000個(gè)元素，負(fù)載因子0.75
Map<String, Object> map = new HashMap<>(1000 / 0.75 + 1);

1. 鍵對(duì)象的不可變性：作為key的對(duì)象應(yīng)該是不可變的，確保hashCode()返回值穩(wěn)定
2. 重寫hashCode()和equals()：自定義對(duì)象作為key時(shí)，必須正確重寫這兩個(gè)方法
3. 線程安全考慮：HashMap非線程安全，多線程環(huán)境下應(yīng)使用：

Map<String, Object> safeMap = Collections.synchronizedMap(new HashMap<>());
// 或者更好的選擇
Map<String, Object> safeMap = new ConcurrentHashMap<>();

七、總結(jié)

HashMap通過(guò)巧妙的"數(shù)組+鏈表+紅黑樹"三級(jí)結(jié)構(gòu)，結(jié)合高效的哈希算法和智能的擴(kuò)容機(jī)制，實(shí)現(xiàn)了近乎O(1)時(shí)間復(fù)雜度的增刪改查操作。理解其底層原理不僅有助于我們?cè)诿嬖囍忻摲f而出，更能指導(dǎo)我們?cè)趯?shí)際開發(fā)中做出更合理的技術(shù)選型和性能優(yōu)化。

從JDK 1.8引入紅黑樹優(yōu)化，到各種精妙的位運(yùn)算優(yōu)化，HashMap的發(fā)展歷程體現(xiàn)了Java團(tuán)隊(duì)對(duì)性能極致追求的設(shè)計(jì)哲學(xué)，值得我們深入學(xué)習(xí)和借鑒。

到此這篇關(guān)于深入剖析Java HashMap的底層實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)Java HashMap原理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論