摘要：則使用了拉鏈?zhǔn)降纳⒘兴惴ǎ⒃谥幸肓思t黑樹(shù)優(yōu)化過(guò)長(zhǎng)的鏈表。如果大家對(duì)紅黑樹(shù)感興趣，可以閱讀我的另一篇文章紅黑樹(shù)詳細(xì)分析。構(gòu)造方法構(gòu)造方法分析的構(gòu)造方法不多，只有四個(gè)。

本篇文章我們來(lái)聊聊大家日常開(kāi)發(fā)中常用的一個(gè)集合類 - HashMap。HashMap 最早出現(xiàn)在 JDK 1.2中，底層基于散列算法實(shí)現(xiàn)。HashMap 允許 null 鍵和 null 值，在計(jì)算哈鍵的哈希值時(shí)，null 鍵哈希值為 0。HashMap 并不保證鍵值對(duì)的順序，這意味著在進(jìn)行某些操作后，鍵值對(duì)的順序可能會(huì)發(fā)生變化。另外，需要注意的是，HashMap 是非線程安全類，在多線程環(huán)境下可能會(huì)存在問(wèn)題。

在本篇文章中，我將會(huì)對(duì) HashMap 中常用方法、重要屬性及相關(guān)方法進(jìn)行分析。需要說(shuō)明的是，HashMap 源碼中可分析的點(diǎn)很多，本文很難一一覆蓋，請(qǐng)見(jiàn)諒。

上一節(jié)說(shuō)到 HashMap 底層是基于散列算法實(shí)現(xiàn)，散列算法分為散列再探測(cè)和拉鏈?zhǔn)?。HashMap 則使用了拉鏈?zhǔn)降纳⒘兴惴?，并?JDK 1.8 中引入了紅黑樹(shù)優(yōu)化過(guò)長(zhǎng)的鏈表。數(shù)據(jù)結(jié)構(gòu)示意圖如下：

對(duì)于拉鏈?zhǔn)降纳⒘兴惴?，其?shù)據(jù)結(jié)構(gòu)是由數(shù)組和鏈表（或樹(shù)形結(jié)構(gòu)）組成。在進(jìn)行增刪查等操作時(shí)，首先要定位到元素的所在桶的位置，之后再?gòu)逆湵碇卸ㄎ辉撛?。比如我們要查詢上圖結(jié)構(gòu)中是否包含元素35，步驟如下：

定位元素35所處桶的位置，index = 35 % 16 = 3

在3號(hào)桶所指向的鏈表中繼續(xù)查找，發(fā)現(xiàn)35在鏈表中。

上面就是 HashMap 底層數(shù)據(jù)結(jié)構(gòu)的原理，HashMap 基本操作就是對(duì)拉鏈?zhǔn)缴⒘兴惴ɑ静僮鞯囊粚影b。不同的地方在于 JDK 1.8 中引入了紅黑樹(shù)，底層數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表變?yōu)榱?b>數(shù)組+鏈表+紅黑樹(shù)，不過(guò)本質(zhì)并未變。好了，原理部分先講到這，接下來(lái)說(shuō)說(shuō)源碼實(shí)現(xiàn)。

本篇文章所分析的源碼版本為 JDK 1.8。與 JDK 1.7 相比，JDK 1.8 對(duì) HashMap 進(jìn)行了一些優(yōu)化。比如引入紅黑樹(shù)解決過(guò)長(zhǎng)鏈表效率低的問(wèn)題。重寫(xiě) resize 方法，移除了 alternative hashing 相關(guān)方法，避免重新計(jì)算鍵的 hash 等。不過(guò)本篇文章并不打算對(duì)這些優(yōu)化進(jìn)行分析，本文僅會(huì)分析 HashMap 常用的方法及一些重要屬性和相關(guān)方法。如果大家對(duì)紅黑樹(shù)感興趣，可以閱讀我的另一篇文章 - 紅黑樹(shù)詳細(xì)分析。

HashMap 的構(gòu)造方法不多，只有四個(gè)。HashMap 構(gòu)造方法做的事情比較簡(jiǎn)單，一般都是初始化一些重要變量，比如 loadFactor 和 threshold。而底層的數(shù)據(jù)結(jié)構(gòu)則是延遲到插入鍵值對(duì)時(shí)再進(jìn)行初始化。HashMap 相關(guān)構(gòu)造方法如下：

/** 構(gòu)造方法 1 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/** 構(gòu)造方法 2 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/** 構(gòu)造方法 3 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/** 構(gòu)造方法 4 */
public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

上面4個(gè)構(gòu)造方法中，大家平時(shí)用的最多的應(yīng)該是第一個(gè)了。第一個(gè)構(gòu)造方法很簡(jiǎn)單，僅將 loadFactor 變量設(shè)為默認(rèn)值。構(gòu)造方法2調(diào)用了構(gòu)造方法3，而構(gòu)造方法3仍然只是設(shè)置了一些變量。構(gòu)造方法4則是將另一個(gè) Map 中的映射拷貝一份到自己的存儲(chǔ)結(jié)構(gòu)中來(lái)，這個(gè)方法不是很常用。

上面就是對(duì)構(gòu)造方法簡(jiǎn)單的介紹，構(gòu)造方法本身并沒(méi)什么太多東西，所以就不說(shuō)了。接下來(lái)說(shuō)說(shuō)構(gòu)造方法所初始化的幾個(gè)的變量。

我們?cè)谝话闱闆r下，都會(huì)使用無(wú)參構(gòu)造方法創(chuàng)建 HashMap。但當(dāng)我們對(duì)時(shí)間和空間復(fù)雜度有要求的時(shí)候，使用默認(rèn)值有時(shí)可能達(dá)不到我們的要求，這個(gè)時(shí)候我們就需要手動(dòng)調(diào)參。在 HashMap 構(gòu)造方法中，可供我們調(diào)整的參數(shù)有兩個(gè)，一個(gè)是初始容量 initialCapacity，另一個(gè)負(fù)載因子 loadFactor。通過(guò)這兩個(gè)設(shè)定這兩個(gè)參數(shù)，可以進(jìn)一步影響閾值大小。但初始閾值 threshold 僅由 initialCapacity 經(jīng)過(guò)移位操作計(jì)算得出。他們的作用分別如下：

相關(guān)代碼如下：

/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

final float loadFactor;

/** The next size value at which to resize (capacity * load factor). */
int threshold;

如果大家去看源碼，會(huì)發(fā)現(xiàn) HashMap 中沒(méi)有定義 initialCapacity 這個(gè)變量。這個(gè)也并不難理解，從參數(shù)名上可看出，這個(gè)變量表示一個(gè)初始容量，只是構(gòu)造方法中用一次，沒(méi)必要定義一個(gè)變量保存。但如果大家仔細(xì)看上面 HashMap 的構(gòu)造方法，會(huì)發(fā)現(xiàn)存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)并不是在構(gòu)造方法里初始化的。這就有個(gè)疑問(wèn)了，既然叫初始容量，但最終并沒(méi)有用與初始化數(shù)據(jù)結(jié)構(gòu)，那傳這個(gè)參數(shù)還有什么用呢？這個(gè)問(wèn)題我先不解釋，給大家留個(gè)懸念，后面會(huì)說(shuō)明。

默認(rèn)情況下，HashMap 初始容量是16，負(fù)載因子為 0.75。這里并沒(méi)有默認(rèn)閾值，原因是閾值可由容量乘上負(fù)載因子計(jì)算而來(lái)（注釋中有說(shuō)明），即threshold = capacity * loadFactor。但當(dāng)你仔細(xì)看構(gòu)造方法3時(shí)，會(huì)發(fā)現(xiàn)閾值并不是由上面公式計(jì)算而來(lái)，而是通過(guò)一個(gè)方法算出來(lái)的。這是不是可以說(shuō)明 threshold 變量的注釋有誤呢？還是僅這里進(jìn)行了特殊處理，其他地方遵循計(jì)算公式呢？關(guān)于這個(gè)疑問(wèn)，這里也先不說(shuō)明，后面在分析擴(kuò)容方法時(shí)，再來(lái)解釋這個(gè)問(wèn)題。接下來(lái)，我們來(lái)看看初始化 threshold 的方法長(zhǎng)什么樣的的，源碼如下：

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

上面的代碼長(zhǎng)的有點(diǎn)不太好看，反正我第一次看的時(shí)候不明白它想干啥。不過(guò)后來(lái)在紙上畫(huà)畫(huà)，知道了它的用途?？偨Y(jié)起來(lái)就一句話：找到大于或等于 cap 的最小2的冪。至于為啥要這樣，后面再解釋。我們先來(lái)看看 tableSizeFor 方法的圖解：

上面是 tableSizeFor 方法的計(jì)算過(guò)程圖，這里cap = 536,870,913 = 2²⁹ + 1，多次計(jì)算后，算出n + 1 = 1,073,741,824 = 2³⁰。通過(guò)圖解應(yīng)該可以比較容易理解這個(gè)方法的用途，這里就不多說(shuō)了。

說(shuō)完了初始閾值的計(jì)算過(guò)程，再來(lái)說(shuō)說(shuō)負(fù)載因子（loadFactor）。對(duì)于 HashMap 來(lái)說(shuō)，負(fù)載因子是一個(gè)很重要的參數(shù)，該參數(shù)反應(yīng)了 HashMap 桶數(shù)組的使用情況（假設(shè)鍵值對(duì)節(jié)點(diǎn)均勻分布在桶數(shù)組中）。通過(guò)調(diào)節(jié)負(fù)載因子，可使 HashMap 時(shí)間和空間復(fù)雜度上有不同的表現(xiàn)。當(dāng)我們調(diào)低負(fù)載因子時(shí)，HashMap 所能容納的鍵值對(duì)數(shù)量變少。擴(kuò)容時(shí)，重新將鍵值對(duì)存儲(chǔ)新的桶數(shù)組里，鍵的鍵之間產(chǎn)生的碰撞會(huì)下降，鏈表長(zhǎng)度變短。此時(shí)，HashMap 的增刪改查等操作的效率將會(huì)變高，這里是典型的拿空間換時(shí)間。相反，如果增加負(fù)載因子（負(fù)載因子可以大于1），HashMap 所能容納的鍵值對(duì)數(shù)量變多，空間利用率高，但碰撞率也高。這意味著鏈表長(zhǎng)度變長(zhǎng)，效率也隨之降低，這種情況是拿時(shí)間換空間。至于負(fù)載因子怎么調(diào)節(jié)，這個(gè)看使用場(chǎng)景了。一般情況下，我們用默認(rèn)值就可以了。

HashMap 的查找操作比較簡(jiǎn)單，查找步驟與原理篇介紹一致，即先定位鍵值對(duì)所在的桶的位置，然后再對(duì)鏈表或紅黑樹(shù)進(jìn)行查找。通過(guò)這兩步即可完成查找，該操作相關(guān)代碼如下：

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // 1. 定位鍵值對(duì)所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 類型，則調(diào)用黑紅樹(shù)查找方法
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
                
            // 2. 對(duì)鏈表進(jìn)行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

查找的核心邏輯是封裝在 getNode 方法中的，getNode 方法源碼我已經(jīng)寫(xiě)了一些注釋，應(yīng)該不難看懂。我們先來(lái)看看查找過(guò)程的第一步 - 確定桶位置，其實(shí)現(xiàn)代碼如下：

// index = (n - 1) & hash
first = tab[(n - 1) & hash]

這里通過(guò)(n - 1)& hash即可算出桶的在桶數(shù)組中的位置，可能有的朋友不太明白這里為什么這么做，這里簡(jiǎn)單解釋一下。HashMap 中桶數(shù)組的大小 length 總是2的冪，此時(shí)，(n - 1) & hash 等價(jià)于對(duì) length 取余。但取余的計(jì)算效率沒(méi)有位運(yùn)算高，所以(n - 1) & hash也是一個(gè)小的優(yōu)化。舉個(gè)例子說(shuō)明一下吧，假設(shè) hash = 185，n = 16。計(jì)算過(guò)程示意圖如下：

上面的計(jì)算并不復(fù)雜，這里就不多說(shuō)了。

在上面源碼中，除了查找相關(guān)邏輯，還有一個(gè)計(jì)算 hash 的方法。這個(gè)方法源碼如下：

/**
 * 計(jì)算鍵的 hash 值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看這個(gè)方法的邏輯好像是通過(guò)位運(yùn)算重新計(jì)算 hash，那么這里為什么要這樣做呢？為什么不直接用鍵的 hashCode 方法產(chǎn)生的 hash 呢？大家先可以思考一下，我把答案寫(xiě)在下面。

這樣做有兩個(gè)好處，我來(lái)簡(jiǎn)單解釋一下。我們?cè)倏匆幌律厦媲笥嗟挠?jì)算圖，圖中的 hash 是由鍵的 hashCode 產(chǎn)生。計(jì)算余數(shù)時(shí)，由于 n 比較小，hash 只有低4位參與了計(jì)算，高位的計(jì)算可以認(rèn)為是無(wú)效的。這樣導(dǎo)致了計(jì)算結(jié)果只與低位信息有關(guān)，高位數(shù)據(jù)沒(méi)發(fā)揮作用。為了處理這個(gè)缺陷，我們可以上圖中的 hash 高4位數(shù)據(jù)與低4位數(shù)據(jù)進(jìn)行異或運(yùn)算，即 hash ^ (hash >>> 4)。通過(guò)這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進(jìn)行異或，以此加大低位信息的隨機(jī)性，變相的讓高位數(shù)據(jù)參與到計(jì)算中。此時(shí)的計(jì)算過(guò)程如下：

在 Java 中，hashCode 方法產(chǎn)生的 hash 是 int 類型，32 位寬。前16位為高位，后16位為低位，所以要右移16位。

上面所說(shuō)的是重新計(jì)算 hash 的一個(gè)好處，除此之外，重新計(jì)算 hash 的另一個(gè)好處是可以增加 hash 的復(fù)雜度。當(dāng)我們覆寫(xiě) hashCode 方法時(shí)，可能會(huì)寫(xiě)出分布性不佳的 hashCode 方法，進(jìn)而導(dǎo)致 hash 的沖突率比較高。通過(guò)移位和異或運(yùn)算，可以讓 hash 變得更復(fù)雜，進(jìn)而影響 hash 的分布性。這也就是為什么 HashMap 不直接使用鍵對(duì)象原始 hash 的原因了。

和查找查找一樣，遍歷操作也是大家使用頻率比較高的一個(gè)操作。對(duì)于 遍歷 HashMap，我們一般都會(huì)用下面的方式：

for(Object key : map.keySet()) {
    // do something
}

或

for(HashMap.Entry entry : map.entrySet()) {
    // do something
}

從上面代碼片段中可以看出，大家一般都是對(duì) HashMap 的 key 集合或 Entry 集合進(jìn)行遍歷。上面代碼片段中用 foreach 遍歷 keySet 方法產(chǎn)生的集合，在編譯時(shí)會(huì)轉(zhuǎn)換成用迭代器遍歷，等價(jià)于：

Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
    Object key = ite.next();
    // do something
}

大家在遍歷 HashMap 的過(guò)程中會(huì)發(fā)現(xiàn)，多次對(duì) HashMap 進(jìn)行遍歷時(shí)，遍歷結(jié)果順序都是一致的。但這個(gè)順序和插入的順序一般都是不一致的。產(chǎn)生上述行為的原因是怎樣的呢？大家想一下原因。我先把遍歷相關(guān)的代碼貼出來(lái)，如下：

public Set keySet() {
    Set ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

/**
 * 鍵集合
 */
final class KeySet extends AbstractSet {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    // 省略部分代碼
}

/**
 * 鍵迭代器
 */
final class KeyIterator extends HashIterator 
    implements Iterator {
    public final K next() { return nextNode().key; }
}

abstract class HashIterator {
    Node next;        // next entry to return
    Node current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry 
            // 尋找第一個(gè)包含鏈表節(jié)點(diǎn)引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node nextNode() {
        Node[] t;
        Node e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 尋找下一個(gè)包含鏈表節(jié)點(diǎn)引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    //省略部分代碼
}

如上面的源碼，遍歷所有的鍵時(shí)，首先要獲取鍵集合KeySet對(duì)象，然后再通過(guò) KeySet 的迭代器KeyIterator進(jìn)行遍歷。KeyIterator 類繼承自HashIterator類，核心邏輯也封裝在 HashIterator 類中。HashIterator 的邏輯并不復(fù)雜，在初始化時(shí)，HashIterator 先從桶數(shù)組中找到包含鏈表節(jié)點(diǎn)引用的桶。然后對(duì)這個(gè)桶指向的鏈表進(jìn)行遍歷。遍歷完成后，再繼續(xù)尋找下一個(gè)包含鏈表節(jié)點(diǎn)引用的桶，找到繼續(xù)遍歷。找不到，則結(jié)束遍歷。舉個(gè)例子，假設(shè)我們遍歷下圖的結(jié)構(gòu)：

HashIterator 在初始化時(shí)，會(huì)先遍歷桶數(shù)組，找到包含鏈表節(jié)點(diǎn)引用的桶，對(duì)應(yīng)圖中就是3號(hào)桶。隨后由 nextNode 方法遍歷該桶所指向的鏈表。遍歷完3號(hào)桶后，nextNode 方法繼續(xù)尋找下一個(gè)不為空的桶，對(duì)應(yīng)圖中的7號(hào)桶。之后流程和上面類似，直至遍歷完最后一個(gè)桶。以上就是 HashIterator 的核心邏輯的流程，對(duì)應(yīng)下圖：

遍歷上圖的最終結(jié)果是 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59，為了驗(yàn)證正確性，簡(jiǎn)單寫(xiě)點(diǎn)測(cè)試代碼跑一下看看。測(cè)試代碼如下：

/**
 * 應(yīng)在 JDK 1.8 下測(cè)試，其他環(huán)境下不保證結(jié)果和上面一致
 */
public class HashMapTest {

    @Test
    public void testTraversal() {
        HashMap map = new HashMap(16);
        map.put(7, "");
        map.put(11, "");
        map.put(43, "");
        map.put(59, "");
        map.put(19, "");
        map.put(3, "");
        map.put(35, "");

        System.out.println("遍歷結(jié)果：");
        for (Integer key : map.keySet()) {
            System.out.print(key + " -> ");
        }
    }
}

遍歷結(jié)果如下：

在本小節(jié)的最后，拋兩個(gè)問(wèn)題給大家。在 JDK 1.8 版本中，為了避免過(guò)長(zhǎng)的鏈表對(duì) HashMap 性能的影響，特地引入了紅黑樹(shù)優(yōu)化性能。但在上面的源碼中并沒(méi)有發(fā)現(xiàn)紅黑樹(shù)遍歷的相關(guān)邏輯，這是為什么呢？對(duì)于被轉(zhuǎn)換成紅黑樹(shù)的鏈表該如何遍歷呢？大家可以先想想，然后可以去源碼或本文后續(xù)章節(jié)中找答案。

通過(guò)前兩節(jié)的分析，大家對(duì) HashMap 低層的數(shù)據(jù)結(jié)構(gòu)應(yīng)該了然于心了。即使我不說(shuō)，大家也應(yīng)該能知道 HashMap 的插入流程是什么樣的了。首先肯定是先定位要插入的鍵值對(duì)屬于哪個(gè)桶，定位到桶后，再判斷桶是否為空。如果為空，則將鍵值對(duì)存入即可。如果不為空，則需將鍵值對(duì)接在鏈表最后一個(gè)位置，或者更新鍵值對(duì)。這就是 HashMap 的插入流程，是不是覺(jué)得很簡(jiǎn)單。當(dāng)然，大家先別高興。這只是一個(gè)簡(jiǎn)化版的插入流程，真正的插入流程要復(fù)雜不少。首先 HashMap 是變長(zhǎng)集合，所以需要考慮擴(kuò)容的問(wèn)題。其次，在 JDK 1.8 中，HashMap 引入了紅黑樹(shù)優(yōu)化過(guò)長(zhǎng)鏈表，這里還要考慮多長(zhǎng)的鏈表需要進(jìn)行優(yōu)化，優(yōu)化過(guò)程又是怎樣的問(wèn)題。引入這里兩個(gè)問(wèn)題后，大家會(huì)發(fā)現(xiàn)原本簡(jiǎn)單的操作，現(xiàn)在略顯復(fù)雜了。在本節(jié)中，我將先分析插入操作的源碼，擴(kuò)容、樹(shù)化（鏈表轉(zhuǎn)為紅黑樹(shù)，下同）以及其他和樹(shù)結(jié)構(gòu)相關(guān)的操作，隨后將在獨(dú)立的兩小結(jié)中進(jìn)行分析。接下來(lái)，先來(lái)看一下插入操作的源碼：

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // 初始化桶數(shù)組 table，table 被延遲到插入新數(shù)據(jù)時(shí)再進(jìn)行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含鍵值對(duì)節(jié)點(diǎn)引用，則將新鍵值對(duì)節(jié)點(diǎn)的引用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        // 如果鍵的值以及節(jié)點(diǎn) hash 等于鏈表中的第一個(gè)鍵值對(duì)節(jié)點(diǎn)時(shí)，則將 e 指向該鍵值對(duì)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹(shù)的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 對(duì)鏈表進(jìn)行遍歷，并統(tǒng)計(jì)鏈表長(zhǎng)度
            for (int binCount = 0; ; ++binCount) {
                // 鏈表中不包含要插入的鍵值對(duì)節(jié)點(diǎn)時(shí)，則將該節(jié)點(diǎn)接在鏈表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果鏈表長(zhǎng)度大于或等于樹(shù)化閾值，則進(jìn)行樹(shù)化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 條件為 true，表示當(dāng)前鏈表包含要插入的鍵值對(duì)，終止遍歷
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判斷要插入的鍵值對(duì)是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對(duì)的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 鍵值對(duì)數(shù)量超過(guò)閾值時(shí)，則進(jìn)行擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

插入操作的入口方法是 put(K,V)，但核心邏輯在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了這么幾件事情：

當(dāng)桶數(shù)組 table 為空時(shí)，通過(guò)擴(kuò)容的方式初始化 table

查找要插入的鍵值對(duì)是否已經(jīng)存在，存在的話根據(jù)條件判斷是否用新值替換舊值

如果不存在，則將鍵值對(duì)鏈入鏈表中，并根據(jù)鏈表長(zhǎng)度決定是否將鏈表轉(zhuǎn)為紅黑樹(shù)

判斷鍵值對(duì)數(shù)量是否大于閾值，大于的話則進(jìn)行擴(kuò)容操作

以上就是 HashMap 插入的邏輯，并不是很復(fù)雜，這里就不多說(shuō)了。接下來(lái)來(lái)分析一下擴(kuò)容機(jī)制。

在 Java 中，數(shù)組的長(zhǎng)度是固定的，這意味著數(shù)組只能存儲(chǔ)固定量的數(shù)據(jù)。但在開(kāi)發(fā)的過(guò)程中，很多時(shí)候我們無(wú)法知道該建多大的數(shù)組合適。建小了不夠用，建大了用不完，造成浪費(fèi)。如果我們能實(shí)現(xiàn)一種變長(zhǎng)的數(shù)組，并按需分配空間就好了。好在，我們不用自己實(shí)現(xiàn)變長(zhǎng)數(shù)組，Java 集合框架已經(jīng)實(shí)現(xiàn)了變長(zhǎng)的數(shù)據(jù)結(jié)構(gòu)。比如 ArrayList 和 HashMap。對(duì)于這類基于數(shù)組的變長(zhǎng)數(shù)據(jù)結(jié)構(gòu)，擴(kuò)容是一個(gè)非常重要的操作。下面就來(lái)聊聊 HashMap 的擴(kuò)容機(jī)制。

在詳細(xì)分析之前，先來(lái)說(shuō)一下擴(kuò)容相關(guān)的背景知識(shí)：

在 HashMap 中，桶數(shù)組的長(zhǎng)度均是2的冪，閾值大小為桶數(shù)組長(zhǎng)度與負(fù)載因子的乘積。當(dāng) HashMap 中的鍵值對(duì)數(shù)量超過(guò)閾值時(shí)，進(jìn)行擴(kuò)容。

HashMap 的擴(kuò)容機(jī)制與其他變長(zhǎng)集合的套路不太一樣，HashMap 按當(dāng)前桶數(shù)組長(zhǎng)度的2倍進(jìn)行擴(kuò)容，閾值也變?yōu)樵瓉?lái)的2倍（如果計(jì)算過(guò)程中，閾值溢出歸零，則按閾值公式重新計(jì)算）。擴(kuò)容之后，要重新計(jì)算鍵值對(duì)的位置，并把它們移動(dòng)到合適的位置上去。以上就是 HashMap 的擴(kuò)容大致過(guò)程，接下來(lái)我們來(lái)看看具體的實(shí)現(xiàn)：

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不為空，表明已經(jīng)初始化過(guò)了
    if (oldCap > 0) {
        // 當(dāng) table 容量超過(guò)容量最大值，則不再擴(kuò)容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按舊容量和閾值的2倍計(jì)算新容量和閾值的大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化時(shí)，將 threshold 的值賦值給 newCap，
         * HashMap 使用 threshold 變量暫時(shí)保存 initialCapacity 參數(shù)的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 調(diào)用無(wú)參構(gòu)造方法時(shí)，桶數(shù)組容量為默認(rèn)容量，
         * 閾值為默認(rèn)容量與默認(rèn)負(fù)載因子乘積
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 為 0 時(shí)，按閾值計(jì)算公式進(jìn)行計(jì)算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 創(chuàng)建新的桶數(shù)組，桶數(shù)組的初始化也是在這里完成的
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果舊的桶數(shù)組不為空，則遍歷桶數(shù)組，并將鍵值對(duì)映射到新的桶數(shù)組中
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新映射時(shí)，需要對(duì)紅黑樹(shù)進(jìn)行拆分
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    // 遍歷鏈表，并將鏈表節(jié)點(diǎn)按原順序進(jìn)行分組
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 將分組后的鏈表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

上面的源碼有點(diǎn)長(zhǎng)，希望大家耐心看懂它的邏輯。上面的源碼總共做了3件事，分別是：

計(jì)算新桶數(shù)組的容量 newCap 和新閾值 newThr

根據(jù)計(jì)算出的 newCap 創(chuàng)建新的桶數(shù)組，桶數(shù)組 table 也是在這里進(jìn)行初始化的

將鍵值對(duì)節(jié)點(diǎn)重新映射到新的桶數(shù)組里。如果節(jié)點(diǎn)是 TreeNode 類型，則需要拆分紅黑樹(shù)。如果是普通節(jié)點(diǎn)，則節(jié)點(diǎn)按原順序進(jìn)行分組。

上面列的三點(diǎn)中，創(chuàng)建新的桶數(shù)組就一行代碼，不用說(shuō)了。接下來(lái)，來(lái)說(shuō)說(shuō)第一點(diǎn)和第三點(diǎn)，先說(shuō)說(shuō) newCap 和 newThr 計(jì)算過(guò)程。該計(jì)算過(guò)程對(duì)應(yīng) resize 源碼的第一和第二個(gè)條件分支，如下：

// 第一個(gè)條件分支
if ( oldCap > 0) {
    // 嵌套條件分支
    if (oldCap >= MAXIMUM_CAPACITY) {...}
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
} 
else if (oldThr > 0) {...}
else {...}

// 第二個(gè)條件分支
if (newThr == 0) {...}

通過(guò)這兩個(gè)條件分支對(duì)不同情況進(jìn)行判斷，進(jìn)而算出不同的容量值和閾值。它們所覆蓋的情況如下：

分支一：

這里把oldThr > 0情況多帶帶拿出來(lái)說(shuō)一下。在這種情況下，會(huì)將 oldThr 賦值給 newCap，等價(jià)于newCap = threshold = tableSizeFor(initialCapacity)。我們?cè)诔跏蓟瘯r(shí)傳入的 initialCapacity 參數(shù)經(jīng)過(guò) threshold 中轉(zhuǎn)最終賦值給了 newCap。這也就解答了前面提的一個(gè)疑問(wèn)：initialCapacity 參數(shù)沒(méi)有被保存下來(lái)，那么它怎么參與桶數(shù)組的初始化過(guò)程的呢？

嵌套分支：

這里簡(jiǎn)單說(shuō)明一下移位導(dǎo)致的溢出情況，當(dāng) loadFactor小數(shù)位為 0，整數(shù)位可被2整除且大于等于8時(shí)，在某次計(jì)算中就可能會(huì)導(dǎo)致 newThr 溢出歸零。見(jiàn)下圖：

分支二：

說(shuō)完 newCap 和 newThr 的計(jì)算過(guò)程，接下來(lái)再來(lái)分析一下鍵值對(duì)節(jié)點(diǎn)重新映射的過(guò)程。

在 JDK 1.8 中，重新映射節(jié)點(diǎn)需要考慮節(jié)點(diǎn)類型。對(duì)于樹(shù)形節(jié)點(diǎn)，需先拆分紅黑樹(shù)再映射。對(duì)于鏈表類型節(jié)點(diǎn)，則需先對(duì)鏈表進(jìn)行分組，然后再映射。需要的注意的是，分組后，組內(nèi)節(jié)點(diǎn)相對(duì)位置保持不變。關(guān)于紅黑樹(shù)拆分的邏輯將會(huì)放在下一小節(jié)說(shuō)明，先來(lái)看看鏈表是怎樣進(jìn)行分組映射的。

我們都知道往底層數(shù)據(jù)結(jié)構(gòu)中插入節(jié)點(diǎn)時(shí)，一般都是先通過(guò)模運(yùn)算計(jì)算桶位置，接著把節(jié)點(diǎn)放入桶中即可。事實(shí)上，我們可以把重新映射看做插入操作。在 JDK 1.7 中，也確實(shí)是這樣做的。但在 JDK 1.8 中，則對(duì)這個(gè)過(guò)程進(jìn)行了一定的優(yōu)化，邏輯上要稍微復(fù)雜一些。在詳細(xì)分析前，我們先來(lái)回顧一下 hash 求余的過(guò)程：

上圖中，桶數(shù)組大小 n = 16，hash1 與 hash2 不相等。但因?yàn)橹挥泻?位參與求余，所以結(jié)果相等。當(dāng)桶數(shù)組擴(kuò)容后，n 由16變成了32，對(duì)上面的 hash 值重新進(jìn)行映射：

擴(kuò)容后，參與模運(yùn)算的位數(shù)由4位變?yōu)榱?位。由于兩個(gè) hash 第5位的值是不一樣，所以兩個(gè) hash 算出的結(jié)果也不一樣。上面的計(jì)算過(guò)程并不難理解，繼續(xù)往下分析。

假設(shè)我們上圖的桶數(shù)組進(jìn)行擴(kuò)容，擴(kuò)容后容量 n = 16，重新映射過(guò)程如下:

依次遍歷鏈表，并計(jì)算節(jié)點(diǎn) hash & oldCap 的值。如下圖所示

如果值為0，將 loHead 和 loTail 指向這個(gè)節(jié)點(diǎn)。如果后面還有節(jié)點(diǎn) hash & oldCap 為0的話，則將節(jié)點(diǎn)鏈入 loHead 指向的鏈表中，并將 loTail 指向該節(jié)點(diǎn)。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節(jié)點(diǎn)。完成遍歷后，可能會(huì)得到兩條鏈表，此時(shí)就完成了鏈表分組：

最后再將這兩條鏈接存放到相應(yīng)的桶中，完成擴(kuò)容。如下圖：

從上圖可以發(fā)現(xiàn)，重新映射后，兩條鏈表中的節(jié)點(diǎn)順序并未發(fā)生變化，還是保持了擴(kuò)容前的順序。以上就是 JDK 1.8 中 HashMap 擴(kuò)容的代碼講解。另外再補(bǔ)充一下，JDK 1.8 版本下 HashMap 擴(kuò)容效率要高于之前版本。如果大家看過(guò) JDK 1.7 的源碼會(huì)發(fā)現(xiàn)，JDK 1.7 為了防止因 hash 碰撞引發(fā)的拒絕服務(wù)攻擊，在計(jì)算 hash 過(guò)程中引入隨機(jī)種子。以增強(qiáng) hash 的隨機(jī)性，使得鍵值對(duì)均勻分布在桶數(shù)組中。在擴(kuò)容過(guò)程中，相關(guān)方法會(huì)根據(jù)容量判斷是否需要生成新的隨機(jī)種子，并重新計(jì)算所有節(jié)點(diǎn)的 hash。而在 JDK 1.8 中，則通過(guò)引入紅黑樹(shù)替代了該種方式。從而避免了多次計(jì)算 hash 的操作，提高了擴(kuò)容效率。

本小節(jié)的內(nèi)容講就先講到這，接下來(lái)，來(lái)講講鏈表與紅黑樹(shù)相互轉(zhuǎn)換的過(guò)程。

JDK 1.8 對(duì) HashMap 實(shí)現(xiàn)進(jìn)行了改進(jìn)。最大的改進(jìn)莫過(guò)于在引入了紅黑樹(shù)處理頻繁的碰撞，代碼復(fù)雜度也隨之上升。比如，以前只需實(shí)現(xiàn)一套針對(duì)鏈表操作的方法即可。而引入紅黑樹(shù)后，需要另外實(shí)現(xiàn)紅黑樹(shù)相關(guān)的操作。紅黑樹(shù)是一種自平衡的二叉查找樹(shù)，本身就比較復(fù)雜。本篇文章中并不打算對(duì)紅黑樹(shù)展開(kāi)介紹，本文僅會(huì)介紹鏈表樹(shù)化需要注意的地方。至于紅黑樹(shù)詳細(xì)的介紹，如果大家有興趣，可以參考我的另一篇文章 - 紅黑樹(shù)詳細(xì)分析。

在展開(kāi)說(shuō)明之前，先把樹(shù)化的相關(guān)代碼貼出來(lái)，如下：

static final int TREEIFY_THRESHOLD = 8;

/**
 * 當(dāng)桶數(shù)組容量小于該值時(shí)，優(yōu)先進(jìn)行擴(kuò)容，而不是樹(shù)化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }
}

/**
 * 將普通節(jié)點(diǎn)鏈表轉(zhuǎn)換成樹(shù)形節(jié)點(diǎn)鏈表
 */
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    // 桶數(shù)組容量小于 MIN_TREEIFY_CAPACITY，優(yōu)先進(jìn)行擴(kuò)容而不是樹(shù)化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 為頭節(jié)點(diǎn)（head），tl 為尾節(jié)點(diǎn)（tail）
        TreeNode hd = null, tl = null;
        do {
            // 將普通節(jié)點(diǎn)替換成樹(shù)形節(jié)點(diǎn)
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);  // 將普通鏈表轉(zhuǎn)成由樹(shù)形節(jié)點(diǎn)鏈表
        if ((tab[index] = hd) != null)
            // 將樹(shù)形鏈表轉(zhuǎn)換成紅黑樹(shù)
            hd.treeify(tab);
    }
}

TreeNode replacementTreeNode(Node p, Node next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

在擴(kuò)容過(guò)程中，樹(shù)化要滿足兩個(gè)條件：

鏈表長(zhǎng)度大于等于 TREEIFY_THRESHOLD

桶數(shù)組容量大于等于 MIN_TREEIFY_CAPACITY

第一個(gè)條件比較好理解，這里就不說(shuō)了。這里來(lái)說(shuō)說(shuō)加入第二個(gè)條件的原因，個(gè)人覺(jué)得原因如下：

當(dāng)桶數(shù)組容量比較小時(shí)，鍵值對(duì)節(jié)點(diǎn) hash 的碰撞率可能會(huì)比較高，進(jìn)而導(dǎo)致鏈表長(zhǎng)度較長(zhǎng)。這個(gè)時(shí)候應(yīng)該優(yōu)先擴(kuò)容，而不是立馬樹(shù)化。畢竟高碰撞率是因?yàn)橥皵?shù)組容量較小引起的，這個(gè)是主因。容量小時(shí)，優(yōu)先擴(kuò)容可以避免一些列的不必要的樹(shù)化過(guò)程。同時(shí)，桶容量較小時(shí)，擴(kuò)容會(huì)比較頻繁，擴(kuò)容時(shí)需要拆分紅黑樹(shù)并重新映射。所以在桶容量比較小的情況下，將長(zhǎng)鏈表轉(zhuǎn)成紅黑樹(shù)是一件吃力不討好的事。

回到上面的源碼中，我們繼續(xù)看一下 treeifyBin 方法。該方法主要的作用是將普通鏈表轉(zhuǎn)成為由 TreeNode 型節(jié)點(diǎn)組成的鏈表，并在最后調(diào)用 treeify 是將該鏈表轉(zhuǎn)為紅黑樹(shù)。TreeNode 繼承自 Node 類，所以 TreeNode 仍然包含 next 引用，原鏈表的節(jié)點(diǎn)順序最終通過(guò) next 引用被保存下來(lái)。我們假設(shè)樹(shù)化前，鏈表結(jié)構(gòu)如下：

HashMap 在設(shè)計(jì)之初，并沒(méi)有考慮到以后會(huì)引入紅黑樹(shù)進(jìn)行優(yōu)化。所以并沒(méi)有像 TreeMap 那樣，要求鍵類實(shí)現(xiàn) comparable 接口或提供相應(yīng)的比較器。但由于樹(shù)化過(guò)程需要比較兩個(gè)鍵對(duì)象的大小，在鍵類沒(méi)有實(shí)現(xiàn) comparable 接口的情況下，怎么比較鍵與鍵之間的大小了就成了一個(gè)棘手的問(wèn)題。為了解決這個(gè)問(wèn)題，HashMap 是做了三步處理，確?？梢员容^出兩個(gè)鍵的大小，如下：

比較鍵與鍵之間 hash 的大小，如果 hash 相同，繼續(xù)往下比較

檢測(cè)鍵類是否實(shí)現(xiàn)了 Comparable 接口，如果實(shí)現(xiàn)調(diào)用 compareTo 方法進(jìn)行比較

如果仍未比較出大小，就需要進(jìn)行仲裁了，仲裁方法為 tieBreakOrder（大家自己看源碼吧）

tie break 是網(wǎng)球術(shù)語(yǔ)，可以理解為加時(shí)賽的意思，起這個(gè)名字還是挺有意思的。

通過(guò)上面三次比較，最終就可以比較出孰大孰小。比較出大小后就可以構(gòu)造紅黑樹(shù)了，最終構(gòu)造出的紅黑樹(shù)如下：

橙色的箭頭表示 TreeNode 的 next 引用。由于空間有限，prev 引用未畫(huà)出?？梢钥闯?，鏈表轉(zhuǎn)成紅黑樹(shù)后，原鏈表的順序仍然會(huì)被引用仍被保留了（紅黑樹(shù)的根節(jié)點(diǎn)會(huì)被移動(dòng)到鏈表的第一位），我們?nèi)匀豢梢园幢闅v鏈表的方式去遍歷上面的紅黑樹(shù)。這樣的結(jié)構(gòu)為后面紅黑樹(shù)的切分以及紅黑樹(shù)轉(zhuǎn)成鏈表做好了鋪墊，我們繼續(xù)往下分析。

紅黑樹(shù)拆分

擴(kuò)容后，普通節(jié)點(diǎn)需要重新映射，紅黑樹(shù)節(jié)點(diǎn)也不例外。按照一般的思路，我們可以先把紅黑樹(shù)轉(zhuǎn)成鏈表，之后再重新映射鏈表即可。這種處理方式是大家比較容易想到的，但這樣做會(huì)損失一定的效率。不同于上面的處理方式，HashMap 實(shí)現(xiàn)的思路則是上好佳（上好佳請(qǐng)把廣告費(fèi)打給我）。如上節(jié)所說(shuō)，在將普通鏈表轉(zhuǎn)成紅黑樹(shù)時(shí)，HashMap 通過(guò)兩個(gè)額外的引用 next 和 prev 保留了原鏈表的節(jié)點(diǎn)順序。這樣再對(duì)紅黑樹(shù)進(jìn)行重新映射時(shí)，完全可以按照映射鏈表的方式進(jìn)行。這樣就避免了將紅黑樹(shù)轉(zhuǎn)成鏈表后再進(jìn)行映射，無(wú)形中提高了效率。

以上就是紅黑樹(shù)拆分的邏輯，下面看一下具體實(shí)現(xiàn)吧：

// 紅黑樹(shù)轉(zhuǎn)鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;

final void split(HashMap map, Node[] tab, int index, int bit) {
    TreeNode b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode loHead = null, loTail = null;
    TreeNode hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    /* 
     * 紅黑樹(shù)節(jié)點(diǎn)仍然保留了 next 引用，故仍可以按鏈表方式遍歷紅黑樹(shù)。
     * 下面的循環(huán)是對(duì)紅黑樹(shù)節(jié)點(diǎn)進(jìn)行分組，與上面類似
     */
    for (TreeNode e = b, next; e != null; e = next) {
        next = (TreeNode)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        // 如果 loHead 不為空，且鏈表長(zhǎng)度小于等于 6，則將紅黑樹(shù)轉(zhuǎn)成鏈表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            /* 
             * hiHead == null 時(shí)，表明擴(kuò)容后，
             * 所有節(jié)點(diǎn)仍在原位置，樹(shù)結(jié)構(gòu)不變，無(wú)需重新樹(shù)化
             */
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    // 與上面類似
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

從源碼上可以看得出，重新映射紅黑樹(shù)的邏輯和重新映射鏈表的邏輯基本一致。不同的地方在于，重新映射后，會(huì)將紅黑樹(shù)拆分成兩條由 TreeNode 組成的鏈表。如果鏈表長(zhǎng)度小于 UNTREEIFY_THRESHOLD，則將鏈表轉(zhuǎn)換成普通鏈表。否則根據(jù)條件重新將 TreeNode 鏈表樹(shù)化。舉個(gè)例子說(shuō)明一下，假設(shè)擴(kuò)容后，重新映射上圖的紅黑樹(shù)，映射結(jié)果如下：

紅黑樹(shù)鏈化

前面說(shuō)過(guò)，紅黑樹(shù)中仍然保留了原鏈表節(jié)點(diǎn)順序。有了這個(gè)前提，再將紅黑樹(shù)轉(zhuǎn)成鏈表就簡(jiǎn)單多了，僅需將 TreeNode 鏈表轉(zhuǎn)成 Node 類型的鏈表即可。相關(guān)代碼如下：

final Node untreeify(HashMap map) {
    Node hd = null, tl = null;
    // 遍歷 TreeNode 鏈表，并用 Node 替換
    for (Node q = this; q != null; q = q.next) {
        // 替換節(jié)點(diǎn)類型
        Node p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

Node replacementNode(Node p, Node next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

上面的代碼并不復(fù)雜，不難理解，這里就不多說(shuō)了。到此擴(kuò)容相關(guān)內(nèi)容就說(shuō)完了，不知道大家理解沒(méi)。

如果大家堅(jiān)持看完了前面的內(nèi)容，到本節(jié)就可以輕松一下。當(dāng)然，前提是不去看紅黑樹(shù)的刪除操作。不過(guò)紅黑樹(shù)并非本文講解重點(diǎn)，本節(jié)中也不會(huì)介紹紅黑樹(shù)相關(guān)內(nèi)容，所以大家不用擔(dān)心。

HashMap 的刪除操作并不復(fù)雜，僅需三個(gè)步驟即可完成。第一步是定位桶位置，第二步遍歷鏈表并找到鍵值相等的節(jié)點(diǎn)，第三步刪除節(jié)點(diǎn)。相關(guān)源碼如下：

public V remove(Object key) {
    Node e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node[] tab; Node p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node node = null, e; K k; V v;
        // 如果鍵的值與鏈表第一個(gè)節(jié)點(diǎn)相等，則將 node 指向該節(jié)點(diǎn)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {  
            // 如果是 TreeNode 類型，調(diào)用紅黑樹(shù)的查找邏輯定位待刪除節(jié)點(diǎn)
            if (p instanceof TreeNode)
                node = ((TreeNode)p).getTreeNode(hash, key);
            else {
                // 2. 遍歷鏈表，找到待刪除節(jié)點(diǎn)
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 3. 刪除節(jié)點(diǎn)，并修復(fù)鏈表或紅黑樹(shù)
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

刪除操作本身并不復(fù)雜，有了前面的基礎(chǔ)，理解起來(lái)也就不難了，這里就不多說(shuō)了。

前面的內(nèi)容分析了 HashMap 的常用操作及相關(guān)的源碼，本節(jié)內(nèi)容再補(bǔ)充一點(diǎn)其他方面的東西。

如果大家細(xì)心閱讀 HashMap 的源碼，會(huì)發(fā)現(xiàn)桶數(shù)組 table 被申明為 transient。transient 表示易變的意思，在 Java 中，被該關(guān)鍵字修飾的變量不會(huì)被默認(rèn)的序列化機(jī)制序列化。我們?cè)倩氐皆创a中，考慮一個(gè)問(wèn)題：桶數(shù)組 table 是 HashMap 底層重要的數(shù)據(jù)結(jié)構(gòu)，不序列化的話，別人還怎么還原呢？

這里簡(jiǎn)單說(shuō)明一下吧，HashMap 并沒(méi)有使用默認(rèn)的序列化機(jī)制，而是通過(guò)實(shí)現(xiàn)readObject/writeObject兩個(gè)方法自定義了序列化的內(nèi)容。這樣做是有原因的，試問(wèn)一句，HashMap 中存儲(chǔ)的內(nèi)容是什么？不用說(shuō)，大家也知道是鍵值對(duì)。所以只要我們把鍵值對(duì)序列化了，我們就可以根據(jù)鍵值對(duì)數(shù)據(jù)重建 HashMap。有的朋友可能會(huì)想，序列化 table 不是可以一步到位，后面直接還原不就行了嗎？這樣一想，倒也是合理。但序列化 talbe 存在著兩個(gè)問(wèn)題：

table 多數(shù)情況下是無(wú)法被存滿的，序列化未使用的部分，浪費(fèi)空間

同一個(gè)鍵值對(duì)在不同 JVM 下，所處的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能會(huì)發(fā)生錯(cuò)誤。

以上兩個(gè)問(wèn)題中，第一個(gè)問(wèn)題比較好理解，第二個(gè)問(wèn)題解釋一下。HashMap 的get/put/remove等方法第一步就是根據(jù) hash 找到鍵所在的桶位置，但如果鍵沒(méi)有覆寫(xiě) hashCode 方法，計(jì)算 hash 時(shí)最終調(diào)用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能會(huì)有不同的實(shí)現(xiàn)，產(chǎn)生的 hash 可能也是不一樣的。也就是說(shuō)同一個(gè)鍵在不同平臺(tái)下可能會(huì)產(chǎn)生不同的 hash，此時(shí)再對(duì)在同一個(gè) table 繼續(xù)操作，就會(huì)出現(xiàn)問(wèn)題。

綜上所述，大家應(yīng)該能明白 HashMap 不序列化 table 的原因了。

本章對(duì) HashMap 常見(jiàn)操作相關(guān)代碼進(jìn)行了詳細(xì)分析，并在最后補(bǔ)充了一些其他細(xì)節(jié)。在本章中，插入操作一節(jié)的內(nèi)容說(shuō)的最多，主要是因?yàn)椴迦氩僮魃婕暗狞c(diǎn)特別多，一環(huán)扣一環(huán)。包含但不限于“table 初始化、擴(kuò)容、樹(shù)化”等，總體來(lái)說(shuō)，插入操作分析起來(lái)難度還是很大的。好在，最后分析完了。

本章篇幅雖比較大，但仍未把 HashMap 所有的點(diǎn)都分析到。比如，紅黑樹(shù)的增刪查等操作。當(dāng)然，我個(gè)人看來(lái)，以上的分析已經(jīng)夠了。畢竟大家是類庫(kù)的使用者而不是設(shè)計(jì)者，沒(méi)必要去弄懂每個(gè)細(xì)節(jié)。所以如果某些細(xì)節(jié)實(shí)在看不懂的話就跳過(guò)吧，對(duì)我們開(kāi)發(fā)來(lái)說(shuō)，知道 HashMap 大致原理即可。

好了，本章到此結(jié)束。

寫(xiě)到這里終于可以松一口氣了，這篇文章前前后后花了我一周多的時(shí)間。在我寫(xiě)這篇文章之前，對(duì) HashMap 認(rèn)識(shí)僅限于原理層面，并未深入了解。一開(kāi)始，我覺(jué)得關(guān)于 HashMap 沒(méi)什么好寫(xiě)的，畢竟大家對(duì) HashMap 多少都有一定的了解。但等我深入閱讀 HashMap 源碼后，發(fā)現(xiàn)之前的認(rèn)知是錯(cuò)的。不是沒(méi)什么可寫(xiě)的，而是可寫(xiě)的點(diǎn)太多了，不知道怎么寫(xiě)了。JDK 1.8 版本的 HashMap 實(shí)現(xiàn)上比之前版本要復(fù)雜的多，想弄懂眾多的細(xì)節(jié)難度還是不小的。僅自己弄懂還不夠，還要寫(xiě)出來(lái)，難度就更大了，本篇文章基本上是在邊讀源碼邊寫(xiě)的狀態(tài)下完成的。由于時(shí)間和能力有限，加之文章篇幅比較大，很難保證不出錯(cuò)分析過(guò)程及配圖不出錯(cuò)。如果有錯(cuò)誤，希望大家指出來(lái)，我會(huì)及時(shí)修改，這里先謝謝大家。

好了，本文就到這里了，謝謝大家的閱讀！

JDK 源碼中 HashMap 的 hash 方法原理是什么？- 知乎

Java 8系列之重新認(rèn)識(shí)HashMap - 美團(tuán)技術(shù)博客

python內(nèi)置的hash函數(shù)對(duì)于字符串來(lái)說(shuō)，每次得到的值不一樣？- 知乎

Java中HashMap關(guān)鍵字transient的疑惑 - segmentFault

本文在知識(shí)共享許可協(xié)議 4.0 下發(fā)布，轉(zhuǎn)載請(qǐng)注明出處
作者：coolblog
為了獲得更好的分類閱讀體驗(yàn)，
請(qǐng)移步至本人的個(gè)人博客：http://www.coolblog.xyz

本作品采用知識(shí)共享署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際許可協(xié)議進(jìn)行許可。