一、前言

在 Java 開發(fā)中，HashMap 是我們最常用的集合類之一。無(wú)論是緩存、配置存儲(chǔ)，還是數(shù)據(jù)傳輸，HashMap 都扮演著重要角色。但你是否真正了解它的底層實(shí)現(xiàn)？為什么它查找這么快？什么時(shí)候會(huì)退化成鏈表？JDK1.8 之后又有哪些優(yōu)化？

本文將帶你深入理解 HashMap 的實(shí)現(xiàn)原理，幫助你從“會(huì)用”到“懂原理”。

二、HashMap 的基本結(jié)構(gòu)

1. 底層數(shù)據(jù)結(jié)構(gòu)（JDK 1.8 之前 vs 之后）

解釋：

• 數(shù)組：HashMap 的主干是一個(gè) Node<K,V>[] table，每個(gè)元素是一個(gè)桶（bucket）。

• 鏈表：當(dāng)發(fā)生哈希沖突時(shí)，多個(gè)鍵值對(duì)會(huì)以鏈表形式存儲(chǔ)在同一個(gè)桶中。

• 紅黑樹：當(dāng)鏈表長(zhǎng)度超過(guò) 8 且數(shù)組長(zhǎng)度大于 64 時(shí)，鏈表會(huì)轉(zhuǎn)為紅黑樹，提升查詢效率。

三、核心源碼解析

1. 構(gòu)造函數(shù)與初始容量

public HashMap(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

• initialCapacity：初始容量，必須是 2 的冪。

• loadFactor：負(fù)載因子，默認(rèn)是 0.75，用于控制擴(kuò)容時(shí)機(jī)。

2. put 方法流程

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

步驟如下：

1. 計(jì)算 key 的 hash 值（hash(key)）

2. 定位桶位置（(n - 1) & hash）

3. 如果桶為空，直接插入

4. 如果桶不為空，遍歷鏈表或紅黑樹

5. 如果 key 已存在，覆蓋 value

6. 如果插入后長(zhǎng)度超過(guò)閾值，觸發(fā)擴(kuò)容或樹化

3. 哈希函數(shù)設(shè)計(jì)

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

目的： 減少哈希沖突，讓高位也參與運(yùn)算，提升分布均勻性。

四、擴(kuò)容機(jī)制（resize）

當(dāng)元素個(gè)數(shù)超過(guò) threshold = capacity * loadFactor 時(shí)，會(huì)觸發(fā)擴(kuò)容：

• 容量翻倍（newCap = oldCap << 1）

• 重新計(jì)算每個(gè)元素的位置（要么在原位置，要么在原位置 + oldCap）

優(yōu)化點(diǎn)： JDK 1.8 中不需要重新計(jì)算 hash，只需看新增的那一位是 0 還是 1。

五、線程安全問(wèn)題

?? HashMap 是線程不安全的！

問(wèn)題表現(xiàn)：

• 多線程 put 可能導(dǎo)致鏈表成環(huán)（JDK 1.7）

• 數(shù)據(jù)丟失、覆蓋等問(wèn)題

解決方案：

六、面試高頻問(wèn)題總結(jié)

七、總結(jié)思維導(dǎo)圖（文字版）

HashMap
├── 結(jié)構(gòu)：數(shù)組 + 鏈表 + 紅黑樹
├── 核心方法：put、get、resize、hash
├── 優(yōu)化：樹化、擴(kuò)容、hash 散列
├── 線程安全：ConcurrentHashMap
└── 面試點(diǎn)：容量、負(fù)載因子、沖突處理、樹化條件

八、附錄：手寫一個(gè)簡(jiǎn)易 HashMap（練習(xí)）

public class MyHashMap<K, V> {
    private Node<K, V>[] table;
    private int size;

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public void put(K key, V value) {
        // 簡(jiǎn)化版，省略擴(kuò)容、樹化等邏輯
    }

    public V get(K key) {
        // 簡(jiǎn)化版
        return null;
    }
}

九、結(jié)語(yǔ)

理解 HashMap 的底層實(shí)現(xiàn)，不僅能幫助你在面試中脫穎而出，更能在實(shí)際開發(fā)中避免踩坑。希望本文能為你打下堅(jiān)實(shí)的基礎(chǔ)。

如果你覺得這篇文章對(duì)你有幫助，歡迎點(diǎn)贊、收藏、評(píng)論！
后續(xù)我還會(huì)更新《ConcurrentHashMap 源碼解析》《Java 集合框架全景圖》等內(nèi)容，記得關(guān)注我哦！

十、參考資料

• Java 官方源碼（OpenJDK 1.8）

• 《Java 編程思想》

• 《Java 并發(fā)編程實(shí)戰(zhàn)》

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

最新評(píng)論