前言

HashMap 是 Java 開發(fā)中使用最頻繁的集合類之一，它基于哈希表實現(xiàn) Map 接口，以鍵值對形式存儲數(shù)據(jù)。在 Java 8 中，HashMap 的實現(xiàn)經(jīng)歷了自誕生以來最大的一次重構(gòu)，引入了許多重要的優(yōu)化和改進(jìn)，旨在解決舊版本中存在的性能瓶頸和潛在問題。本文將從底層數(shù)據(jù)結(jié)構(gòu)、哈希算法、擴(kuò)容機(jī)制、線程安全性等多個維度，結(jié)合源碼深入剖析 Java 8 中 HashMap 的變革，帶你全面理解這些差異背后的設(shè)計思想。

1. HashMap 基礎(chǔ)回顧

在深入 Java 8 的改動之前，有必要先回顧一下 HashMap 的基本概念和 Java 7 及之前版本的核心實現(xiàn)。

• 存儲結(jié)構(gòu)：HashMap 內(nèi)部維護(hù)一個 Node<K,V>[] table 數(shù)組（也稱為桶數(shù)組），每個數(shù)組元素是一個單鏈表的頭節(jié)點或紅黑樹的根節(jié)點。當(dāng)插入鍵值對時，根據(jù)鍵的 hashCode 計算出數(shù)組下標(biāo)，如果該位置為空則直接放入；如果發(fā)生哈希沖突（多個鍵映射到同一桶），則采用鏈地址法，將新節(jié)點插入鏈表。

• 重要參數(shù)：

  • 初始容量（initial capacity）：默認(rèn) 16，必須是 2 的冪。

  • 負(fù)載因子（load factor）：默認(rèn) 0.75，衡量 HashMap 填充程度的指標(biāo)。

  • 閾值（threshold）：容量 * 負(fù)載因子，當(dāng)元素個數(shù)超過閾值時觸發(fā)擴(kuò)容。

• 擴(kuò)容機(jī)制：當(dāng)元素數(shù)量超過閾值，HashMap 會擴(kuò)容為原容量的兩倍，并將所有元素重新計算哈希值后分配到新數(shù)組中（rehash）。這個過程非常耗時。

• 線程安全性：HashMap 不是線程安全的。在多線程環(huán)境下，Java 7 的 HashMap 在并發(fā)擴(kuò)容時可能形成環(huán)形鏈表，導(dǎo)致后續(xù) get 操作死循環(huán)。

2. Java 7 及之前 HashMap 的局限

2.1 鏈表過長導(dǎo)致的性能退化

在哈希函數(shù)設(shè)計不佳或存在大量哈希沖突的情況下，鏈表會變得很長，使得查找、插入、刪除操作的時間復(fù)雜度從 O(1) 退化到 O(n)。例如，攻擊者可以構(gòu)造大量哈希值相同的鍵，使 HashMap 退化成單鏈表，引發(fā)拒絕服務(wù)攻擊。

2.2 擴(kuò)容時頭插法引發(fā)的死循環(huán)

Java 7 的 HashMap 在擴(kuò)容遷移元素時，采用“頭插法”將原鏈表中的節(jié)點插入新數(shù)組的對應(yīng)桶中。頭插法會導(dǎo)致鏈表反轉(zhuǎn)，在多線程并發(fā)擴(kuò)容時，兩個線程可能同時操作鏈表，使鏈表形成環(huán)，導(dǎo)致后續(xù)查詢時陷入死循環(huán)。這是 Java 7 HashMap 最著名的并發(fā)問題。

2.3 哈希算法不夠高效

Java 7 的哈希函數(shù)通過多次異或和移位運算來擾動 hashCode，以減少碰撞，但效率相對較低。其代碼如下：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

這種擾動函數(shù)雖然能夠有效降低碰撞，但計算步驟較多。

3. Java 8 HashMap 的核心改進(jìn)

Java 8 對 HashMap 進(jìn)行了徹底的重寫，主要變化體現(xiàn)在以下幾個方面：

3.1 數(shù)據(jù)結(jié)構(gòu)升級：數(shù)組 + 鏈表 + 紅黑樹

在 Java 8 中，當(dāng)鏈表長度超過一定閾值（默認(rèn)為 8）且數(shù)組長度大于等于 64 時，鏈表會轉(zhuǎn)換為紅黑樹（Treeify），將查詢時間復(fù)雜度從 O(n) 降低到 O(log n)。當(dāng)紅黑樹節(jié)點數(shù)減少到 6 時，又會轉(zhuǎn)換回鏈表（Untreeify）。引入紅黑樹的目的是在哈希碰撞嚴(yán)重的情況下，仍能保證良好的性能。

為什么選擇紅黑樹？

• 平衡二叉搜索樹（如 AVL 樹）雖然查找更快（O(log n)），但插入/刪除需要更多的旋轉(zhuǎn)操作，綜合性能不如紅黑樹。

• 紅黑樹是一種近似平衡的二叉搜索樹，它能夠以 O(log n) 的時間復(fù)雜度完成查找、插入和刪除，且旋轉(zhuǎn)次數(shù)相對較少。

• 在實際應(yīng)用中，哈希碰撞的概率通常較低，大多數(shù)桶中鏈表長度很小，此時鏈表操作成本低于紅黑樹（樹節(jié)點需要維護(hù)父節(jié)點、左右子節(jié)點、顏色等，占用空間更大）。因此，Java 8 只在鏈表過長時才啟用樹化，達(dá)到空間和時間的平衡。

樹化閾值的選擇：為什么是 8？
官方注釋中給出的解釋是基于泊松分布的概率計算。在理想隨機(jī)哈希碼下，桶中節(jié)點個數(shù)的概率服從泊松分布，參數(shù)約為 0.5（負(fù)載因子 0.75 時的平均填充因子）。計算得到鏈表長度達(dá)到 8 的概率已經(jīng)非常?。s 0.00000006），因此將 8 作為樹化閾值，可以在保證性能的同時，避免過度樹化帶來的空間開銷。

鏈表長度超過 8 但數(shù)組長度小于 64 時，不會立即樹化，而是優(yōu)先進(jìn)行擴(kuò)容（resize）。這是因為在數(shù)組容量較小時，擴(kuò)容可以更有效地分散哈希沖突，避免不必要的樹化開銷。

3.2 哈希算法的簡化與優(yōu)化

Java 8 中對哈希函數(shù)的實現(xiàn)做了簡化，將高位與低位進(jìn)行異或，稱為“擾動函數(shù)”：

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

它將 key 的 hashCode 的高 16 位與低 16 位進(jìn)行異或，使高位的特征也能影響最終的下標(biāo)計算。相比 Java 7，這個擾動函數(shù)只做了一次右移和異或，性能更高，同時仍然能夠有效減少碰撞（因為數(shù)組下標(biāo)由哈希值的低位決定，高位特征丟失可能導(dǎo)致沖突）。

3.3 擴(kuò)容機(jī)制的優(yōu)化

Java 8 對擴(kuò)容過程進(jìn)行了兩方面的改進(jìn)：

1. 去除了頭插法，改用尾插法，從而避免多線程環(huán)境下的環(huán)形鏈表問題（但 HashMap 本身仍非線程安全）。

2. 元素遷移不再重新計算哈希，而是利用擴(kuò)容后容量是 2 的冪這一特點，通過 hash & oldCap 來判斷元素的新位置。

原理分析：
假設(shè)原數(shù)組容量為 n（2 的冪），擴(kuò)容后容量為 2n。在計算元素存放位置時，使用的是 (n - 1) & hash。當(dāng)容量翻倍后，新的掩碼變?yōu)?nbsp;(2n - 1)，相當(dāng)于在原掩碼的最高位增加了一個 1。因此，元素的新位置要么是原位置，要么是原位置加上舊容量 n。判斷依據(jù)就是看哈希值在新增的那一位上是 0 還是 1：

• 如果 hash & n == 0，說明新增位為 0，元素留在原索引 j；

• 否則，新增位為 1，元素移動到 j + oldCap。

這樣，擴(kuò)容時無需重新計算哈希值，只需遍歷鏈表，按條件拆分成兩條鏈表，分別插入新數(shù)組的兩個對應(yīng)桶中。同時，由于采用尾插法，鏈表在拆分后仍保持原來的順序，這對于依賴順序的場景（如迭代）更友好。

3.4 樹化與去樹化的實現(xiàn)細(xì)節(jié)

樹化過程涉及 treeifyBin() 和 treeify() 方法。當(dāng)鏈表長度達(dá)到 8 且數(shù)組長度 ≥ 64 時，putVal 方法會調(diào)用 treeifyBin 將鏈表轉(zhuǎn)換為紅黑樹。轉(zhuǎn)換時，先創(chuàng)建 TreeNode 對象（繼承自 LinkedHashMap.Entry，而 LinkedHashMap.Entry 繼承自 HashMap.Node），然后通過 treeify 方法構(gòu)建紅黑樹，并設(shè)置桶的頭節(jié)點為樹的根節(jié)點。

去樹化發(fā)生在擴(kuò)容或刪除元素時，如果紅黑樹節(jié)點數(shù)小于 6，untreeify 會將樹轉(zhuǎn)換回鏈表。注意，樹化閾值與去樹化閾值不同（8 和 6），中間留有緩沖，避免頻繁樹化和去樹化帶來的抖動。

3.5 迭代器與 Spliterator 的適配

由于引入了紅黑樹，HashMap 的迭代器（如 KeyIterator、ValueIterator、EntryIterator）以及 Java 8 新增的 Spliterator 都需要同時支持鏈表和樹的遍歷。TreeNode 本身是 Node 的子類，因此迭代器可以通過 nextNode 方法統(tǒng)一遍歷，但樹的遍歷需要額外處理（樹節(jié)點也有 next 指針，維護(hù)著鏈表順序）。

4. Java 8 HashMap 源碼深度剖析

為了更深入地理解上述改進(jìn)，我們直接分析 Java 8 中 HashMap 的核心源碼片段。

4.1 基本屬性定義

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // 默認(rèn)初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默認(rèn)負(fù)載因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 樹化閾值：鏈表長度超過 8 時考慮樹化
    static final int TREEIFY_THRESHOLD = 8;
    // 去樹化閾值：紅黑樹節(jié)點數(shù)小于 6 時退化為鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小樹化容量：數(shù)組長度小于 64 時不進(jìn)行樹化，優(yōu)先擴(kuò)容
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲桶數(shù)組，每個元素是 Node 或 TreeNode
    transient Node<K,V>[] table;
    // entrySet 緩存
    transient Set<Map.Entry<K,V>> entrySet;
    // 元素個數(shù)
    transient int size;
    // 修改次數(shù)，用于 fail-fast 機(jī)制
    transient int modCount;
    // 擴(kuò)容閾值 = capacity * load factor
    int threshold;
    // 負(fù)載因子
    final float loadFactor;
    // ...
}

4.2 節(jié)點定義

鏈表節(jié)點 Node<K,V>：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // 構(gòu)造器、getter、setter、equals、hashCode
}

紅黑樹節(jié)點 TreeNode<K,V> 繼承自 LinkedHashMap.Entry<K,V>，而 LinkedHashMap.Entry 繼承自 HashMap.Node，因此 TreeNode 同時擁有 next 指針（用于維護(hù)鏈表順序）和樹相關(guān)的屬性（parent、left、right、prev、red）。這種設(shè)計使得樹節(jié)點既能作為紅黑樹節(jié)點，又能作為鏈表節(jié)點，簡化了遍歷。

4.3 hash 方法

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

這里將 key 的 hashCode 右移 16 位，再與原值異或，讓高 16 位也參與后續(xù)的取模運算。因為數(shù)組下標(biāo)使用的是 (n - 1) & hash，只有低 n 位有效，如果哈希值的高位變化而低位不變，就容易沖突。通過擾動，使低位也能混合高位的信息，降低碰撞概率。

4.4 put 方法流程

put(K key, V value) 實際調(diào)用 putVal 方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果數(shù)組為空，則通過 resize 初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 計算桶索引，如果該位置為空，直接插入新節(jié)點
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果桶的第一個節(jié)點與待插入鍵匹配，記錄為 e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是樹節(jié)點，調(diào)用樹的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 鏈表遍歷
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果鏈表長度達(dá)到樹化閾值（8），嘗試樹化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果找到了相同鍵，更新值并返回舊值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 元素個數(shù)超過閾值，擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

關(guān)鍵點：

• 插入新節(jié)點時，如果鏈表長度達(dá)到 7（binCount 從 0 開始，到 7 時意味著鏈表已有 8 個節(jié)點），會調(diào)用 treeifyBin 嘗試樹化。

• treeifyBin 內(nèi)部會檢查數(shù)組長度是否小于 64，若是則進(jìn)行擴(kuò)容（resize），否則才真正執(zhí)行鏈表到樹的轉(zhuǎn)換。

4.5 treeifyBin 方法

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果數(shù)組為空或長度小于 MIN_TREEIFY_CAPACITY，優(yōu)先擴(kuò)容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 將鏈表節(jié)點依次替換為 TreeNode，并組成雙向鏈表
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 調(diào)用樹節(jié)點的 treeify 方法構(gòu)建紅黑樹
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

這里將普通 Node 替換為 TreeNode，同時維護(hù)了 prev 指針，形成雙向鏈表，方便后續(xù)遍歷和去樹化。

4.6 resize 擴(kuò)容方法

擴(kuò)容方法相對復(fù)雜，這里只分析關(guān)鍵部分，特別是元素遷移的優(yōu)化：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 計算新容量和閾值...
    // 創(chuàng)建新數(shù)組
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍歷舊數(shù)組
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 單個節(jié)點直接放入新數(shù)組
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 樹節(jié)點拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 鏈表節(jié)點拆分，維護(hù)順序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 判斷 hash 與 oldCap 的位
                        if ((e.hash & oldCap) == 0) {
                            // 留在原索引的鏈表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            // 移到原索引+oldCap 的鏈表
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 將兩條鏈表放入新數(shù)組
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

關(guān)鍵優(yōu)化點：

• 使用 e.hash & oldCap 替代 e.hash & (newCap-1) 來區(qū)分高低位，避免重新計算哈希值。

• 鏈表拆分時，保持了原來的順序（尾插法），因此不會出現(xiàn) Java 7 中的鏈表反轉(zhuǎn)。

• 紅黑樹的拆分通過 split 方法完成，類似于鏈表的拆分，但需要根據(jù)節(jié)點數(shù)決定是否需要去樹化。

4.7 get 方法流程

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 檢查第一個節(jié)點
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 如果是樹節(jié)點，在樹中查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 否則遍歷鏈表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

樹查找通過 getTreeNode 調(diào)用 find 方法，在紅黑樹中二分查找，復(fù)雜度 O(log n)。

5. 性能對比與分析

5.1 最壞情況下的性能提升

在極端哈希沖突的情況下，Java 7 的 HashMap 會退化為鏈表，查找復(fù)雜度 O(n)。假設(shè)有 10,000 個元素全部映射到同一個桶，一次查找需要遍歷整個鏈表，耗時與元素數(shù)量成正比。而在 Java 8 中，當(dāng)鏈表長度超過 8 且數(shù)組足夠大時，鏈表會轉(zhuǎn)換為紅黑樹，查找復(fù)雜度降為 O(log n)，10,000 個元素時最多比較 14 次，性能提升顯著。

5.2 平均性能

在正常哈希分布下，大多數(shù)桶的鏈表長度很短（0 或 1），此時 Java 8 的額外開銷僅在于判斷節(jié)點類型（是否是 TreeNode）和可能的一兩次擾動計算，與 Java 7 相比差別不大。但由于紅黑樹的引入，內(nèi)存占用略有增加（每個樹節(jié)點比鏈表節(jié)點多存儲 parent、left、right、red 等字段），但考慮到現(xiàn)代服務(wù)器內(nèi)存容量，這點開銷通常可以接受。

5.3 擴(kuò)容性能

Java 8 的擴(kuò)容不再重新計算哈希值，僅通過位運算判斷新位置，效率更高。同時尾插法避免了死循環(huán)，但這也導(dǎo)致多線程環(huán)境下仍可能丟失數(shù)據(jù)（因為多個線程修改共享數(shù)組），所以 HashMap 依然不是線程安全的。

6. 線程安全與并發(fā)問題

Java 8 的 HashMap 解決了 Java 7 中并發(fā)擴(kuò)容導(dǎo)致死循環(huán)的問題，因為尾插法不會形成環(huán)。但這并不意味著 HashMap 可以在多線程環(huán)境下安全使用。例如：

• 兩個線程同時執(zhí)行 put 操作，可能都發(fā)現(xiàn)桶為空，然后各自插入自己的節(jié)點，導(dǎo)致數(shù)據(jù)覆蓋。

• 擴(kuò)容時多個線程同時修改 table 引用，可能導(dǎo)致數(shù)據(jù)丟失。

• 迭代器仍然是 fail-fast 的，如果在迭代過程中被其他線程修改，會拋出 ConcurrentModificationException。

因此，在多線程環(huán)境中，應(yīng)使用 ConcurrentHashMap、Collections.synchronizedMap 或 Hashtable。特別地，Java 8 也對 ConcurrentHashMap 進(jìn)行了大量優(yōu)化，引入了紅黑樹和 CAS 操作，性能大幅提升。

7. 其他細(xì)節(jié)變化

7.1 鍵和值的 null 處理

與 Java 7 一樣，Java 8 的 HashMap 允許一個 null 鍵和多個 null 值。null 鍵的哈希值為 0，因此總是存放在 table[0] 桶中。

7.2 初始容量與負(fù)載因子

最佳實踐：如果已知存儲元素數(shù)量，應(yīng)指定初始容量，避免頻繁擴(kuò)容。負(fù)載因子的默認(rèn)值 0.75 是時間和空間成本的折中，一般不建議修改。

7.3 迭代順序

HashMap 不保證迭代順序，但隨著 Java 8 的改進(jìn)，由于鏈表尾插法，在擴(kuò)容后鏈表順序保持不變，但紅黑樹的存在使得迭代順序更加復(fù)雜?？傮w而言，不應(yīng)依賴 HashMap 的迭代順序。

7.4 新增的 API

Java 8 為 Map 接口添加了一些默認(rèn)方法，如 getOrDefault、putIfAbsent、remove（鍵值對）、replace 等，HashMap 實現(xiàn)了這些方法，方便了開發(fā)。

8. 總結(jié)：Java 8 HashMap 的改進(jìn)與不足

改進(jìn)點：

1. 引入紅黑樹，解決鏈表過長導(dǎo)致的性能問題，將最壞情況時間復(fù)雜度從 O(n) 降到 O(log n)。

2. 優(yōu)化哈希算法，簡化計算同時保持低位隨機(jī)性。

3. 改進(jìn)擴(kuò)容機(jī)制，采用位運算判斷新位置，避免重新計算哈希，且使用尾插法消除死循環(huán)風(fēng)險。

4. 引入樹化閾值和去樹化閾值，平衡時間和空間。

5. 增加新的實用方法，提升 API 友好性。

仍然存在的問題：

1. 非線程安全，并發(fā)環(huán)境下仍需使用 ConcurrentHashMap。

2. 內(nèi)存占用：紅黑樹節(jié)點比鏈表節(jié)點更占內(nèi)存，但在大多數(shù)情況下可接受。

3. 樹化條件限制：當(dāng)數(shù)組長度較小時，即使鏈表很長也不樹化，而是先擴(kuò)容，這可能導(dǎo)致在特定場景下性能下降（例如數(shù)組大小固定為 16 且無法擴(kuò)容時，鏈表會一直很長）。不過這種情況較少見。

9. 面試常見問題與回答思路

• Q：Java 8 中 HashMap 為什么要引入紅黑樹？
  A：為了防止哈希沖突嚴(yán)重時鏈表過長，導(dǎo)致查找效率低下。紅黑樹能夠提供 O(log n) 的查找性能，而鏈表是 O(n)。通過設(shè)置閾值，只在必要時樹化，平衡性能與空間。

• Q：樹化閾值為什么是 8？
  A：根據(jù)泊松分布，在理想隨機(jī)哈希碼下，鏈表長度達(dá)到 8 的概率已經(jīng)非常低（約 0.00000006），因此將 8 作為閾值可以在保證性能的同時避免過度樹化。同時，如果數(shù)組長度小于 64，會優(yōu)先擴(kuò)容，因為擴(kuò)容能更好地分散數(shù)據(jù)。

• Q：Java 8 中 HashMap 是如何解決擴(kuò)容死循環(huán)問題的？
  A：Java 8 改用尾插法，且擴(kuò)容時不會改變鏈表順序，因此不會形成環(huán)形鏈表。但 HashMap 本身仍不是線程安全的，多線程下仍可能出現(xiàn)數(shù)據(jù)丟失等問題。

• Q：Java 8 的 HashMap 擴(kuò)容時如何確定元素新位置？
  A：通過 hash & oldCap 判斷，如果結(jié)果為 0 則留在原索引，否則移動到“原索引 + oldCap”。這是因為擴(kuò)容后容量變?yōu)?2n，索引計算掩碼新增了最高位，而該位的值正是 hash 在 oldCap 對應(yīng)位上的值。

• Q：HashMap 的哈希函數(shù)為什么要高 16 位異或低 16 位？
  A：為了使高位也能參與數(shù)組下標(biāo)計算，減少沖突。因為數(shù)組下標(biāo)由 hash 的低 n 位決定，如果哈希值的高位變化而低位相同，容易發(fā)生碰撞。通過異或，將高位的特征混合到低位，提高散列性。

• Q：HashMap 和 ConcurrentHashMap 在 Java 8 中的改進(jìn)有何異同？
  A：兩者都引入了紅黑樹，但 ConcurrentHashMap 在 Java 8 中采用了 CAS + synchronized 實現(xiàn)更細(xì)粒度的并發(fā)控制，并取消了分段鎖，結(jié)構(gòu)更簡單，并發(fā)性能更好。

10. 結(jié)語

Java 8 對 HashMap 的重構(gòu)是一次經(jīng)典的性能優(yōu)化案例，它不僅解決了舊版本中存在的缺陷，還為后續(xù)的集合框架演進(jìn)奠定了基礎(chǔ)。

到此這篇關(guān)于Java8中HashMap到底有啥不同的文章就介紹到這了,更多相關(guān)Java8中HashMap不同內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論