一、前言

在 Java 的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)里，HashMap 無疑是一個非常重要的數(shù)據(jù)結(jié)構(gòu)。這一篇文章中我們來學習并分析一下其內(nèi)部的實現(xiàn)原理。文章將基于 JDK 1.8 進行分析，暫時不考慮不同版本之間的差異。

二、Map 概述

首先我們列舉出 Map 相關(guān)大部分類，并畫成如下類圖 Map 大家族。通過對 Map 大家族類圖使得我們可以在腦海中對這些數(shù)據(jù)結(jié)構(gòu)有一個相對比較完整的輪廓。即哪些是重點，哪些是常用的類，我們在使用這些數(shù)據(jù)結(jié)構(gòu)時，它在其家族成員中大概是在什么位置，它們都有哪一些基本特性和適用場景，我們在心里應(yīng)該要有一個拿捏。

Map大家族.jpg

從上圖看 Map 大族還是挺多成員的，而實際應(yīng)用中我們常用的其實沒有這么多，所以在此基礎(chǔ)上，我精減了一下，把常用的且重要的抽了一下，得到一個簡版的，如下。

Map大家族簡版.jpg

這個簡版的圖看起來是不是舒服多了，事實上只要我們熟練常握了上述這些Map數(shù)據(jù)結(jié)構(gòu)的特性以及原理，那可以說在工作中的應(yīng)用應(yīng)當是游刃有余了。下面表格是對這些常用 Map 的一個概述。

三、HashMap 源碼分析

1. demo 測試

分析之前先來看一段 demo，除了常規(guī)的插入字符串，還重復(fù)插入了 null 引用和空字串。

HashMap<String,String> hashMap = new HashMap<>();
        hashMap.put(null,null);
        hashMap.put("","");
        hashMap.put(null,null);
        hashMap.put("","");
        hashMap.put("語文","張大爺同學");
        hashMap.put("數(shù)學","李大節(jié)同學");
        hashMap.put("英語","王大媽同學");
        hashMap.put("體育","劉部長同學");
        hashMap.put("物理","吳先生同學");
        hashMap.put("化學","成龍同學");
        hashMap.put("地理","胡歌同學");
        hashMap.put("生物","韓同學");
        hashMap.put("自然","方同學");
        hashMap.put("政治","馬同學");
        hashMap.put("音樂","舒同學");
        hashMap.put("美術(shù)","百同學");

        Log.d("HashMap","testHashMap: hashMap size = " + hashMap.size());
        Set<Map.Entry<String,String>> entries = hashMap.entrySet();
        for (Map.Entry<String,String> entry : entries) {
            Log.d("HashMap", "testHashMap: key = " + entry.getKey() + ";value = " + entry.getValue());
        }

下面來看看這段代碼的輸出結(jié)果

    testHashMap: hashMap size = 14
    testHashMap: key = 物理;value = 吳先生同學
    testHashMap: key = null;value = null
    testHashMap: key = 政治;value = 馬同學
    testHashMap: key = 自然;value = 方同學
    testHashMap: key = ;value = 
    testHashMap: key = 美術(shù);value = 百同學
    testHashMap: key = 數(shù)學;value = 李大節(jié)同學
    testHashMap: key = 地理;value = 胡歌同學
    testHashMap: key = 生物;value = 韓同學
    testHashMap: key = 體育;value = 劉部長同學
    testHashMap: key = 化學;value = 成龍同學
    testHashMap: key = 語文;value = 張大爺同學
    testHashMap: key = 英語;value = 王大媽同學
    testHashMap: key = 音樂;value = 舒同學

demo 中我們一共插入了 16 個元素，但實際 size 只有 14 個，也就是相同的 key 只能有一個，且 null 不等于空字串。這是一個愉快的過程。

2. 認知 HashMap

在概述部分，我們看到了 Map 大家族的大致輪廓。在這里我們再來看一下 HashMap 的繼承關(guān)系以及內(nèi)部結(jié)構(gòu)的概括圖，概括圖同樣也是讓我們對 HashMap 有一個全貌的了解。

HashMap.jpg

下面對這個概要類圖作一個稍微詳細的描述：

(1) HashMap 繼承自抽象類 AbstractMap，而 AbstractMap 以及 HashMap 本身又都實現(xiàn)了接口 Map。Map 接口規(guī)范了作為一個 key-value 類你應(yīng)該有哪一些方法，其中最重要的是 get()，put()，remove()以及用來管理內(nèi)部數(shù)據(jù)的視圖keySet(),values()，entrySet()。同時還定義用于抽象 key-value 的 Entry 接口。順便提一下，從 JDK 1.8 開始，通過關(guān)鍵字 default，Map 接口中也提供了一些方法的默認實現(xiàn)。
(2) AbstractMap 抽象了一個最簡單實現(xiàn) Map 接口的骨架，該類同時定義了 keySet 和 values 視圖 。視圖主要是用于實現(xiàn)如何遍歷，其主要是起到緩存的作用。
(3) HashMap 自然是具體的實現(xiàn)類，其定義了具體的成員變量，每個成員變量都非常的重要，分析的過程中，我們應(yīng)該要掌握每一個成員變量的定義以及作用。其中的 Node 類封裝了 Key-Value 的節(jié)點，也是存儲 key-value 的實際對象。這里先簡單了解一下各個成員變量的定義。

3.代碼分析

說到代碼分析，相對來說會難一點，但我們不要畏難，復(fù)雜的事情也可以簡單化的。我們先不考慮 HashMap 有多復(fù)雜，有多少多少的功能，我們且以 demo 為主線來分析其主要的路線，然后在這個基礎(chǔ)上再補齊相關(guān)功能的分析要簡單的多。根據(jù)上面的 demo 測試，我們先來看看時序圖。

demo時序圖.jpg

時序圖里一共 8 個步驟，但其主要其實可以分成 3 個部分：初始化、插入以及遍歷。

3.1 初始化——HashMap 的構(gòu)造方法

初始化，也就是 HashMap 的構(gòu)造方法。

/**
     * 構(gòu)造一個空的 HashMap，其 capacity 默認為 16，load factor 默認為 0.75
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

構(gòu)造方法做的事情很簡單，就是確定容量大小以及比例因子的大小。構(gòu)造方法還有 2 個比較重要的重載方法，一起來看一下。

/**
* 指定 capacity 大小，但 load factor 默認為 0.75
*/
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 同時指定 capacity 和 load factor 的大小，并且同時計算出 threshold 的值 
*/
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;
        // 約束 threshold 的大小應(yīng)該為 2 的 n 次冪
        this.threshold = tableSizeFor(initialCapacity);
}

通過 HashMap 的構(gòu)造方法其實給了我們一個優(yōu)化思路，就是根據(jù)不同的應(yīng)用場景，如果我們能夠預(yù)期其大小或者說能夠預(yù)期其未來的變化率，那么我們應(yīng)該初始化時就指定好 capacity 和 loadFactor，那么就能有效減少內(nèi)存的分配和 擴容的分配，從而提升 HashMap 的使用效率。

3.2 插入——put()方法

/**
* 使 key 和 value 產(chǎn)生關(guān)聯(lián)，但如果有相同的 key 則新的會替換掉舊的
*/
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

上面的代碼里，進行了 2 步操作，先通過 hash() 函數(shù)對 key 求 hash 碼，然后再進一步調(diào)用 putVal()。那么先來分析 hash() 函數(shù)吧。

static final int hash(Object key) {
        int h;
        // 如果為 null 則返回的就是 0，否則就是 hashCode 異或上 hashCode 無符號右移 16 位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

注釋里有簡要說明了 hash 值的產(chǎn)生方法，得到的結(jié)果就是 hashCode 的高 16 位不變，低 16 位與高 16 位做一個異或。這樣做的目的是同時把高 16 位和低 16 位的影響都考慮進來以減少小容量 HashMap 的散列沖突。當然，這也與 HashMap 中計算散列后的 index 的方法有關(guān)。計算散列 index 的實現(xiàn)在 putVal() 方法里，不防先來看一看。

i = (n - 1) & hash

可以看到，HashMap 并沒有采用 %(取余) 這種簡單粗暴的實現(xiàn)，而是使用 &(按位與) 來分布散列 index 的生成，其主要目的當然是盡量減少碰撞沖突。相比較來說 % 的碰撞沖突應(yīng)該是非常高的。再來說上面的為什么要同時考慮到高 16 位與低 16 位的影響。capacity 的容量大小是 2 的 n 次冪，試想一下如果不做異或，而只是用原 hashcode ，那么在小 map 中，能起作用的就永遠只是低位，雖然 hashCode 的生成已經(jīng)分布的很平衡了，但相比較而前，同時考慮到高位與低位的影響，最后計算出的散列 index 發(fā)生碰撞的沖突肯定要小的多。關(guān)于 hash() 方法的實現(xiàn)，其實設(shè)計者也作了比較詳盡的解釋，比如其還提到，沒有采用更復(fù)雜的生成 hash 方法，也是出于效率考慮。而對于大的 map 發(fā)生的散列沖突，其采用了紅黑樹來提高了查詢的效率。感興趣的可以看看原設(shè)計者的注釋。

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

hash() 就了解到這里，來進一步看看 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;
    // tab為空則通過resize()創(chuàng)建，插入第 1 個值的時候發(fā)生
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 計算散列 index，沒有沖突直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 有沖突
    else {
        Node<K,V> e; K k;
       // 存在 hash 值相同且 key 相等的，先記錄下來，后面的插入步驟會使用新值將舊值替換掉
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 該節(jié)點為樹，散列沖突過長，大于 TREEIFY_THRESHOLD = 8 時會轉(zhuǎn)換成樹
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 該節(jié)點為鏈表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 插入到鏈尾
                    p.next = newNode(hash, key, value, null);
                    // 鏈表的長度超過 TREEIFY_THRESHOLD - 1 則轉(zhuǎn)換成樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 對鏈表中的相同 hash 值且 key 相同的進一步作檢查
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 插入
        // existing mapping for key
        if (e != null) { 
            // 取出舊值，onlyIfAbsent此時為 false，所以不管 oldValue 有與否，都拿新值來替換
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超過閾值 threshold = capacity * factor，調(diào)用 resize() 進行擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

putVal() 里面作的事情比較多，每一個重要的過程都寫在了注釋里面。但這里還是來總結(jié)一下吧：
(1)通過對 hash(key) 計算出來的 hash 值，計算出散列 index。
(2)如果沒碰撞沖突直接放到 table 里。
(3)如果碰撞沖突了，先以鏈表的形式解決沖突，并把新的 node 插入到鏈尾。
(4)如果碰撞沖突導(dǎo)致鏈表過長(>= TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹，提高查詢效率。
(5)如果節(jié)點已經(jīng)存在，即key的 hash() 值相等且 key 的內(nèi)容相等，就替換 old value，從而保證 key 的唯一性
(6)如果 table 滿了( > load factor*capacity)，就要擴容resize()。

在 putVal() 方法中，其中有 3 個關(guān)鍵的調(diào)用：putTreeVal()，treeifyBin()以及resize()。putTreeVal()和treeifyBin()分別涉及到了紅黑二叉樹的插入以及初始化，這個就先不深入展開了。而對于 resize() 我們還是要深入了解一下的，否則我們怎么能體會得到擴容的代價到底有多大呢？

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) {
        // 超過最大值就不再擴充 table，但并不表示不能插入了，只是后面的只能碰撞沖突了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 沒超過最大值，就擴充為原來的 2 倍。主要是容量以及閾值都為原來的 2倍。容量和閾值本身就都必須是 2 的冪，所以擴容的倍數(shù)必須是2的倍數(shù)，那么擴2倍就非常合理了。
        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);
    }
    // 計算新的resize閾值
    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"})
        // 重新分配內(nèi)存
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把原來 tables 中的每個節(jié)點都移動到新的 tables 中
        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)// 沖突的是一棵樹節(jié)點，分裂成 2 個樹，或者如果樹很小就轉(zhuǎn)成鏈表
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order，沖突構(gòu)成的是鏈表
                    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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到 tables 里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到  tables 里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize() 里面關(guān)鍵做了2個耗時耗力的事情：一是分配了 2 倍的 tables 的空間，最糟糕的情況是擴容完后不再有插入了。二是將舊的 tables 放入新的 tables 中，這里就包括了 index 的重新計算，鏈表沖突重新分布，tree 沖突分裂或者轉(zhuǎn)化成鏈表。算法的細節(jié)展示在了注釋里面了，有興趣的同學可以跟著代碼推導(dǎo)一下，沒興趣也不影響理解。

3.3遍歷

/**
     * Returns a {@link Set} view of the mappings 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, or through the
     * <tt>setValue</tt> operation on a map entry returned by the
     * iterator) 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 mappings contained in this map
     */
public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

這段代碼實際上就是 new 了一個 EntrySet 對象，而上面的意思主要表達的是這是由 map 映射的 set，對 map 的修改將會反映到 set 中，反之亦然。怎么做到的呢？當然通過 EntrySet 也只能是修改 value，即通過 setValue()。如果在遍歷過程中進行刪除的話，也是會觸發(fā) ConcurrentModificationException 的。

再來看看 EntrySet 的實現(xiàn)，來研究一下它是怎么做到映射的。

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        ......
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
       ......

如上代碼，只列表出了一個關(guān)鍵的實現(xiàn)，即 iterator() 接口。Java 中的 foreach 之所以能夠?qū)?Collection 類進行遍歷，其原理就是要 Collection 的子類實現(xiàn) iterator() 接口并返回一個具體的迭代器，遍歷時通過 hasNext()判斷其是否還有元素，而通過 next() 來獲取下一個元素。這也是迭代器設(shè)計模式的一個實現(xiàn)。那么，再來看看 EntryIterator 的 next() 實現(xiàn)。

// EntryIterator 又繼承了 HashIterator
final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
}
// HashIterator 的定義，這里只列出了HashIterator構(gòu)造方法 nextNode() 方法
 abstract class HashIterator {
   ......
  HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            // 初始時 next 為 tables 中的第一個節(jié)點的第一個 node
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == 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();
            // 先獲取當前 next 節(jié)點的 next
            if ((next = (current = e).next) == null && (t = table) != null) {
                // 如果為空則再到 tables 中的下一個節(jié)點中的 Node 中去找
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
......
}

從上面代碼以及增加的注釋知道，首先是初始化HashIterator時，next 為 tables 中的第 1 個節(jié)點，后面的遍歷過程中會先看當前這個節(jié)點是否已經(jīng)沒有 next 了，如果沒有了再 index + 1 取下一個節(jié)點，以此類推來遍歷完所有的節(jié)點。

entrySet()的遍歷就分析到這里了，entrySet()遍歷只是遍歷方式中的其中的一種，其他幾種我們也一并列出來了解一下 。

        //方法一：通過 Map.keySet 遍歷 key 和 value，多了個 getValue 的過程
        for (String key : hashMap.keySet()) {
            System.out.println("Key: " + key + " Value: " + hashMap.get(key));
        }

        //方法二：通過 Map.values() 遍歷所有的 value，但不能遍歷 key
        for (String v : hashMap.values()) {
            System.out.println("The value is " + v);
        }

        //方法三：通過 Map.entrySet 使用 iterator 遍歷 key 和 value，而 iterator 又是要取出 entrySet的，相當于又多了一步。但其最大的特點是適用于一邊遍歷一邊刪除的場景。不需要用一個 set 先保存下來再刪除了。
        Iterator iterator = hashMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> entry = (Map.Entry<String, String>) iterator.next();
            System.out.println("Key: " + entry.getKey() + " Value: " + entry.getValue());
            // 遍歷完成后馬上進行刪除
            iterator.remove();
        }
        // 方法四：通過 entrySet 進行遍歷，直接遍歷出key和value。對于 size 比較大的情況下，又需要全部遍歷的時候，效率是最高的。
        for (Map.Entry<String, String> entry : entries) {
            System.out.println("testHashMap: key = " + entry.getKey() + ";value = " + entry.getValue());
        }

觀察這 4 種遍歷方式會發(fā)現(xiàn)，只有方法三是可以在遍歷過程中通過迭代器進行刪除的，其他的方法都會報 ConcurrentModificationException，而方法四是最快的。

至此，HashMap 的初始化--插入--再到遍歷的主路徑已經(jīng)分析完了?？墒菍τ?HashMap 來說還沒有完，還有我們的 get() 操作和 remove() 操作。

3.4 get()

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
        // 命中
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 直接命中了 tables 中的 node
            return first;
        // 未命中 tables 中的 node
        if ((e = first.next) != null) {// 存在碰撞沖突的情況
            // 如果是紅黑樹
            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);
        }
    }
    // 未命中返回 null
    return null;
}

果然在理解了 put() 的基礎(chǔ)上，再來看 get() 就輕松多了。一切都在注釋中，就不重復(fù)了。

3.5 remove()

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 &&
            (p = tab[index = (n - 1) & hash]) != null) {
           // 命中
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
               // 在 tables 中就命中了
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    // 在紅黑樹中找
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                   // 在鏈表中找
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
           // 第二步：刪除
            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)
                    // 從tables節(jié)點中刪除
                    tab[index] = node.next;
                else
                    // 從鏈表中刪除
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
       // 未命中直接返回 null
        return null;
    }

同理，這里理解 remove() 的實現(xiàn)也是非常輕松的一件事情。詳細的過程都在代碼的注釋里，其也是分了兩個大步驟進行的，先查找再刪除，而且查找的過程與 get() 實現(xiàn)非常類似。

3.6 關(guān)于 ConcurrentModificationException

在 HashMap 的代碼中有很多地方都可能會發(fā)生 ConcurrentModificationException，從代碼上看其原因是 modCount != expectedModCount。那這又代表了什么呢？這里以 HashIterator的 next() 為例來分析。貼一下相關(guān)代碼。

HashIterator() {
            expectedModCount = modCount;
           ......
        }
final Node<K,V> nextNode() {
            ......
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            ......
            return e;
        }

在遍歷時，foreach 會調(diào)用 Collection 的 iterator() 接口，而從 EntrySet 的實現(xiàn)中我們知道每次遍歷都會 new 一個新的 Iterator ，也就是說 HashIterator 每次遍歷時都會被初始化。有了這個基礎(chǔ)，我們再來看一看其發(fā)生的過程。
(1) HashIterator 在初始化時，令 modCount 賦值給了 expectedModCount，這個時候也進行了迭代的時候。
(2) 當 HashMap 發(fā)生 put() 或者 remove() 時都會修改到 modCount 的值
(3) 一旦 modCount 的值被修改，那么再遍歷到 nextNode() 時就會發(fā)生 ConcurrentModificationException 了。

至此，HashMap 中關(guān)于初始化，遍歷，put，get , remove 以及 ConcurrentModificationException 產(chǎn)生的原因都分析完了。

四、總結(jié)

(1) HashMap 中的 index 的計算是擾動了 hashCode ，并且通過位運算 & 來計算的，這也是因為其長度為 2 的 n 次冪才能通過位運算來計算的。
(2) 關(guān)于碰撞沖突，可能會連接成一個鏈表。當鏈表長度過長會將鏈表轉(zhuǎn)成紅黑二叉樹，默認的長度閾值是 8 個。
(3) 關(guān)于擴容，默認容量是 16 個，當容量到達當前容量 * 比例因子時，就會發(fā)生擴容。默認的比例因子是 0.75，擴容時是擴大原 tables 的 1 倍。擴容的代價是比較大的，內(nèi)存是擴充一倍，且元素的存儲都要進行相應(yīng)的調(diào)整。
(4) 關(guān)于遍歷，遍歷時一般不能再修改 HashMap ，否則可能會造成 ConcurrentModificationException。

五、后記

文章先是總結(jié)了 Java 中 Map 大家族的類圖，再總結(jié)了 HashMap 的概括類圖，這讓我們對 Map 以及 HashMap 有一個整體的輪廓。有了一個輪廓后再去看各個類的實現(xiàn)細節(jié)就會產(chǎn)生迷失在細節(jié)里的情況，也能大概知道各個類之間的關(guān)聯(lián)性。

最后，感謝你能讀到并讀完此文章，如果分析的過程中存在錯誤或者疑問都歡迎留言討論。如果我的分享能夠幫助到你，還請記得幫忙點個贊吧，謝謝。