一盐类、簡(jiǎn)介

?Java為數(shù)據(jù)結(jié)構(gòu)中的鍵值對(duì)集合定義了一個(gè)接口java.util.Map忍宋，此接口主要有四個(gè)常用的實(shí)現(xiàn)類(lèi)俗或，分別是HashMap、Hashtable陨亡、LinkedHashMap和TreeMap傍衡，類(lèi)繼承關(guān)系如下圖所示：

Map相關(guān)實(shí)現(xiàn)類(lèi)的繼承關(guān)系

• HashMap：它根據(jù)鍵的hashCode值存儲(chǔ)數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值负蠕，因而具有很快的訪(fǎng)問(wèn)速度蛙埂，但遍歷順序卻是不確定的。HashMap最多只允許一條記錄的鍵為null遮糖，允許多條的記錄的值為null绣的。HashMap非線(xiàn)程安全，即任意時(shí)刻可以有多個(gè)線(xiàn)程同時(shí)寫(xiě)HashMap，可能會(huì)導(dǎo)致數(shù)據(jù)的不一致屡江。如果需要滿(mǎn)足線(xiàn)程安全芭概，可以用Collections的synchronizedMap方法使HashMap具有線(xiàn)程安全的能力，或者使用ConcurrentHashMap惩嘉。
• Hashtable：Hashtable是遺留類(lèi)罢洲，很多映射的常用功能與HashMap類(lèi)似，不同的是它繼承自Dictionary類(lèi)文黎，并且是線(xiàn)程安全的惹苗，任一時(shí)間只有一個(gè)線(xiàn)程能寫(xiě)Hashtable，并發(fā)性不如ConcurrentHashMap耸峭，因?yàn)?code>ConcurrentHashMap引入了分段鎖（JDK1.8重新使用了新的實(shí)現(xiàn)方式桩蓉，后面的文章單獨(dú)講解）。Hashtable不建議在新代碼中使用劳闹，不需要線(xiàn)程安全的場(chǎng)合可以用HashMap替換债沮，需要線(xiàn)程安全的場(chǎng)合可以用ConcurrentHashMap替換。
• LinkedHashMap：LinkedHashMap是HashMap的一個(gè)子類(lèi)妹卿，保存了記錄的插入順序毕莱，再用Iterator遍歷LinkedHashMap時(shí)，先得到的記錄肯定是先插入的偏友，也可以在構(gòu)造時(shí)帶參數(shù)蔬胯，按照訪(fǎng)問(wèn)次序排序。
• TreeMap：TreeMap實(shí)現(xiàn)SortedMap接口位他，能夠把它保存的記錄根據(jù)鍵排序氛濒，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器鹅髓，當(dāng)用Iterator遍歷TreeMap時(shí)舞竿，得到的記錄是排過(guò)序的。如果使用排序的鍵值對(duì)集合窿冯，建議使用TreeMap骗奖。在使用TreeMap時(shí)，key必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator醒串，否則會(huì)在運(yùn)行時(shí)拋出java.lang.ClassCastException類(lèi)型的異常执桌。
  ?對(duì)于上述四種Map類(lèi)型的類(lèi)，要求集合中的key是不可變對(duì)象芜赌。不可變對(duì)象是該對(duì)象在創(chuàng)建后它的哈希值不會(huì)被改變仰挣。如果對(duì)象的哈希值發(fā)生改變，Map對(duì)象很可能就定位不到映射的位置了缠沈。
  ?通過(guò)上面的比較膘壶，我們知道了HashMap是Java的Map家族中一個(gè)普通成員错蝴，鑒于它可以滿(mǎn)足大多數(shù)場(chǎng)景的使用條件，所以是使用頻度最高的一個(gè)颓芭。下文我們主要結(jié)合源碼顷锰，從存儲(chǔ)結(jié)構(gòu)、常用方法分析畜伐、擴(kuò)容以及安全性等方面深入講解HashMap的工作原理馍惹。

二、原理

? HashMap 底層是基于散列算法實(shí)現(xiàn)玛界，散列算法分為散列再探測(cè)和拉鏈?zhǔn)剑?code>散列值沖突解決方案通常是兩種方法：鏈表法和開(kāi)放定址法万矾。鏈表法就是將相同hash值的對(duì)象組織成一個(gè)鏈表放在hash值對(duì)應(yīng)的槽位；開(kāi)放定址法是通過(guò)一個(gè)探測(cè)算法慎框，當(dāng)某個(gè)槽位已經(jīng)被占據(jù)的情況下繼續(xù)查找下一個(gè)可以使用的槽位良狈。java.util.HashMap采用的鏈表法的方式，鏈表是單向鏈表笨枯。）薪丁。HashMap 則使用了拉鏈?zhǔn)降纳⒘兴惴ǎ⒃?JDK 1.8 中引入了紅黑樹(shù)優(yōu)化過(guò)長(zhǎng)的鏈表馅精。數(shù)據(jù)結(jié)構(gòu)示意圖如下：

1. 定位元素35所處的桶的位置睦优，index = 35 % 16 = 3
2. 在3號(hào)桶所指向的鏈表中繼續(xù)查找，發(fā)現(xiàn)35在鏈表中壮不。

?上面就是HashMap底層數(shù)據(jù)結(jié)構(gòu)的原理汗盘，HashMap基本操作就是對(duì)拉鏈?zhǔn)缴⒘兴惴ɑ静僮鞯囊粚影b。不同的地方在于JDK1.8中引入紅黑樹(shù)询一，底層數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表變?yōu)榱?code>數(shù)組+鏈表+紅黑樹(shù)隐孽，不過(guò)本質(zhì)并未變。

三健蕊、源碼分析

?本篇文章所分析的源碼版本為 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)方法世舰。

3.1構(gòu)造方法

3.1.1 構(gòu)造方法分析

?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
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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)造方法2
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /** 構(gòu)造方法4
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /** 構(gòu)造方法3
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

?上面四個(gè)構(gòu)造方法茸塞，大家平時(shí)使用最多的就是構(gòu)造方法3了，這個(gè)構(gòu)造方法僅將 loadFactor 變量設(shè)為默認(rèn)值查剖。構(gòu)造方法2調(diào)用了構(gòu)造方法1钾虐，而構(gòu)造方法1仍然只是設(shè)置了一些變量。構(gòu)造方法4則是將另一個(gè) Map 中的映射拷貝一份到自己的存儲(chǔ)結(jié)構(gòu)中來(lái)笋庄，這個(gè)方法不是很常用效扫。

3.1.2 初始容量、負(fù)載因子直砂、閾值

?我們?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)參(注：阿里的Java編碼規(guī)范中明確推薦，集合初始化時(shí)籍嘹， 指定集合初始值大小闪盔。主要是針對(duì)HashMap，HashMap 使用HashMap(int initialCapacity) 初始化辱士，防止多次resize泪掀，對(duì)性能損耗比較大)。在 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; // aka 16

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

/**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

?如果大家去看源碼适掰，會(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)題我先不解釋?zhuān)o大家留個(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)造方法1時(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à)热康，知道了它的用途×恿欤總結(jié)起來(lái)就一句話(huà)：找到大于或等于 cap 的最小2的冪姐军。至于為啥要這樣，后面再解釋。我們先來(lái)看看 tableSizeFor 方法的圖解：

• 它的作用就是取最接近c(diǎn)ap這個(gè)數(shù)的2的冪次。
• 例如:4最接近的2的冪次其實(shí)就是4,即2²; 5最接近的2的冪次的為8（2³）.
• 按我們正常的思路：枚舉一遍復(fù)雜度為O(30).這里最大值為2³⁰.

?接下來(lái)我們解釋下它是怎么實(shí)現(xiàn)的：

int n = cap - 1; // 這里是為了防止cap本身就是2的冪次梆造，如果按下面的方法的話(huà)最后結(jié)果是cap*2.

?重點(diǎn)是后面的幾行代碼：

n |= n >>> 1; //取高位的2個(gè)1
n |= n >>> 2; //取高位的4個(gè)1
n |= n >>> 4; //取高位的8個(gè)1
n |= n >>> 8; //取高位的16個(gè)1
n |= n >>> 16; //取高位的32個(gè)1

?說(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)值就可以了给猾。

3.2 查找

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

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> 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 類(lèi)型池颈，則調(diào)用黑紅樹(shù)查找方法
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 3. 對(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ě)了一些注釋?zhuān)瑧?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ò)程示意圖如下：

?在上面源碼中宠互，除了查找相關(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呢？
?這樣做有兩個(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ò)程如下：

3.3 遍歷

?和查找查找一樣宜狐，遍歷操作也是大家使用頻率比較高的一個(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)车要，如下：

/**
     * Returns a {@link Set} view of the keys contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation), the results of
     * the iteration are undefined.  The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
     * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
     * operations.
     *
     * @return a set view of the keys contained in this map
     */
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> 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;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

final class KeyIterator extends HashMap<K, V>.HashIterator implements Iterator<K> {
        KeyIterator() {
            super();
        }

        public final K next() {
            return this.nextNode().key;
        }
    }

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

        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

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

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

?如上面的源碼，遍歷所有的鍵時(shí)崭倘，首先要獲取鍵集合KeySet對(duì)象翼岁，然后再通過(guò) KeySet 的迭代器KeyIterator進(jìn)行遍歷。KeyIterator 類(lèi)繼承自HashIterator類(lèi)司光，核心邏輯也封裝在 HashIterator類(lèi)中琅坡。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)桶二打。之后流程和上面類(lèi)似县忌，直至遍歷完最后一個(gè)桶。以上就是 HashIterator 的核心邏輯的流程继效，對(duì)應(yīng)下圖：

3.4 插入

3.4.1插入邏輯分析

?通過(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)看一下插入操作的源碼：

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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);
                        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;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

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

1. 當(dāng)桶數(shù)組 table 為空時(shí)吃靠，通過(guò)擴(kuò)容的方式初始化 table
2. 查找要插入的鍵值對(duì)是否已經(jīng)存在硫眨，存在的話(huà)根據(jù)條件判斷是否用新值替換舊值
3. 如果不存在，則將鍵值對(duì)鏈入鏈表中巢块，并根據(jù)鏈表長(zhǎng)度決定是否將鏈表轉(zhuǎn)為紅黑樹(shù)
4. 判斷鍵值對(duì)數(shù)量是否大于閾值礁阁，大于的話(huà)則進(jìn)行擴(kuò)容操作

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

3.4.2 擴(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ì)于這類(lèi)基于數(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)：

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            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
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        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件事，分別是：

1. 計(jì)算新桶數(shù)組的容量 newCap 和新閾值 newThr
2. 根據(jù)計(jì)算出的 newCap 創(chuàng)建新的桶數(shù)組叉讥，桶數(shù)組 table 也是在這里進(jìn)行初始化的
3. 將鍵值對(duì)節(jié)點(diǎn)重新映射到新的桶數(shù)組里砾跃。如果節(jié)點(diǎn)是 TreeNode 類(lèi)型，則需要拆分紅黑樹(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情況單獨(dú)拿出來(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)類(lèi)型亿柑。對(duì)于樹(shù)形節(jié)點(diǎn)邢疙，需先拆分紅黑樹(shù)再映射。對(duì)于鏈表類(lèi)型節(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位的值是不一樣可岂，所以?xún)蓚€(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的話(huà)欺税，則將節(jié)點(diǎn)鏈入 loHead 指向的鏈表中，并將 loTail 指向該節(jié)點(diǎn)揭璃。如果值為非0的話(huà)晚凿，則讓 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ò)程另伍。

3.4.3 鏈表樹(shù)化鼻百、紅黑樹(shù)鏈化與拆分

?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ù)化需要注意的地方视哑。
?在展開(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<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

/**
 * 將普通節(jié)點(diǎn)鏈表轉(zhuǎn)換成樹(shù)形節(jié)點(diǎn)鏈表
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> 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<K,V> hd = null, tl = null;
        do {
            // 將普通節(jié)點(diǎn)替換成樹(shù)形節(jié)點(diǎn)
            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);  // 將普通鏈表轉(zhuǎn)成由樹(shù)形節(jié)點(diǎn)鏈表
        if ((tab[index] = hd) != null)
            // 將樹(shù)形鏈表轉(zhuǎn)換成紅黑樹(shù)
            hd.treeify(tab);
    }
}

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

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

1. 鏈表長(zhǎng)度大于等于TREEIFY_THRESHOLD
2. 桶數(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 類(lèi)本股，所以 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那樣躬审，要求鍵類(lèi)實(shí)現(xiàn) comparable接口或提供相應(yīng)的比較器棘街。但由于樹(shù)化過(guò)程需要比較兩個(gè)鍵對(duì)象的大小，在鍵類(lèi)沒(méi)有實(shí)現(xiàn) comparable 接口的情況下承边，怎么比較鍵與鍵之間的大小了就成了一個(gè)棘手的問(wèn)題遭殉。為了解決這個(gè)問(wèn)題，HashMap 是做了三步處理博助，確毕瘴郏可以比較出兩個(gè)鍵的大小，如下：

1. 比較鍵與鍵之間 hash 的大小，如果 hash 相同蛔糯，繼續(xù)往下比較
2. 檢測(cè)鍵類(lèi)是否實(shí)現(xiàn)了 Comparable 接口拯腮，如果實(shí)現(xiàn)調(diào)用compareTo 方法進(jìn)行比較
3. 如果仍未比較出大小，就需要進(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<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    /* 
     * 紅黑樹(shù)節(jié)點(diǎn)仍然保留了 next 引用荠察，故仍可以按鏈表方式遍歷紅黑樹(shù)置蜀。
     * 下面的循環(huán)是對(duì)紅黑樹(shù)節(jié)點(diǎn)進(jìn)行分組奈搜，與上面類(lèi)似
     */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)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);
        }
    }
    // 與上面類(lèi)似
    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 類(lèi)型的鏈表即可。相關(guān)代碼如下：

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

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

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

3.5 刪除

?如果大家堅(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<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> 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 類(lèi)型粘咖，調(diào)用紅黑樹(shù)的查找邏輯定位待刪除節(jié)點(diǎn)
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)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<K,V>)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ō)了讽坏。

3.6 其他細(xì)節(jié)

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

?被 transient 所修飾 table 變量
?如果大家細(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)巡社，不序列化的話(huà)膛堤，別人還怎么還原呢？

?這里簡(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)題：

1. table 多數(shù)情況下是無(wú)法被存滿(mǎn)的晨抡，序列化未使用的部分氛悬，浪費(fèi)空間
2. 同一個(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 的原因了跳昼。

3.7 總結(jié)

?本章對(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)夠了恼除。畢竟大家是類(lèi)庫(kù)的使用者而不是設(shè)計(jì)者踪旷，沒(méi)必要去弄懂每個(gè)細(xì)節(jié)曼氛。所以如果某些細(xì)節(jié)實(shí)在看不懂的話(huà)就跳過(guò)吧，對(duì)我們開(kāi)發(fā)來(lái)說(shuō)令野，知道 HashMap 大致原理即可舀患。

參考

1. https://segmentfault.com/a/1190000012926722