一推溃、寫在前面

相信讀者也看過了不少講解 HashMap 源碼的文章了，筆者認為，一切脫離源碼去講原理的都是泛泛而談搔耕。一些所謂的原理大都是閱讀源碼之后的個人概括逮京，這些概括參差不齊氓癌，再加上沒有閱讀源碼坠狡，讀者們是很難有切身體會的泵三。

筆者在閱讀 HashMap 源碼的時候咽安，曾對每個內(nèi)部屬性伴网，每個內(nèi)部方法和方法調(diào)用邏輯做了簡要注釋，但在整理成文的時候妆棒，還是遇到了略微的困難澡腾。對于一些內(nèi)部屬性的解釋，需要結(jié)合它在一些方法的使用中發(fā)揮的作用來綜合說明糕珊，筆者打算按照從淺到深的順序动分，先帶讀者熟悉 HashMap 的宏觀設(shè)計思想，再通讀一遍源碼红选，然后講解源碼的設(shè)計細節(jié)澜公。要讓讀者邊看文字邊對照源碼進行學(xué)習(xí)，形成自己的領(lǐng)悟和體會喇肋，避免造成筆者一人的泛泛而談玛瘸。

無論自己的領(lǐng)悟是深是淺蜕青，終歸是自己的，無論別人的領(lǐng)悟多么高深糊渊，那也是別人的右核。希望每個讀者都能有自己的收獲和體會。

Java 版本

$ java -version
java version "1.8.0_211"
Java(TM) SE Runtime Environment (build 1.8.0_211-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.211-b12, mixed mode)

二渺绒、HashMap官方說明

以下內(nèi)容主要對 HashMap 的一些特性和注意事項做了簡單的說明贺喝，筆者對一些比較重要的知識點做了加粗處理。
基于哈希表的 Map 接口的實現(xiàn)宗兼。此實現(xiàn)提供所有可選的映射操作躏鱼，并允許使用 null 值和 null 鍵。（除了不同步和允許使用 null 之外殷绍，HashMap 類與 Hashtable 大致相同染苛。）此類不保證映射的順序，特別是它不保證該順序恒久不變主到。

此實現(xiàn)假定哈希函數(shù)將元素正確分布在各桶之間茶行，可為基本操作（get 和 put）提供穩(wěn)定的性能。迭代集合視圖所需的時間與 HashMap 實例的“容量”（桶的數(shù)量）及其大械窃俊（鍵-值映射關(guān)系數(shù)）的和成比例畔师。所以，如果迭代性能很重要牧牢，則不要將初始容量設(shè)置得太高（或?qū)⒓虞d因子設(shè)置得太低）看锉。

HashMap 的實例有兩個參數(shù)影響其性能：初始容量 和加載因子。容量 是哈希表中桶的數(shù)量塔鳍，初始容量只是哈希表在創(chuàng)建時的容量伯铣。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數(shù)超出了加載因子與當前容量的乘積時轮纫，通過調(diào)用 rehash 方法將容量翻倍懂傀。

通常，默認加載因子（0.75）在時間和空間成本上尋求一種折衷蜡感。加載因子過高雖然減少了空間開銷蹬蚁，但同時也增加了查詢成本（在大多數(shù) HashMap 類的操作中，包括 get 和 put 操作郑兴，都反映了這一點）犀斋。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地降低 rehash 操作次數(shù)情连。如果初始容量大于最大條目數(shù)除以加載因子叽粹，則不會發(fā)生 rehash 操作。

如果很多映射關(guān)系要存儲在 HashMap 實例中，則相對于按需執(zhí)行自動的 rehash 操作以增大表的容量來說虫几，使用足夠大的初始容量創(chuàng)建它將使得映射關(guān)系能更有效地存儲锤灿。

注意，此實現(xiàn)不是同步的辆脸。如果多個線程同時訪問此映射但校，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步啡氢。（結(jié)構(gòu)上的修改是指添加或刪除一個或多個映射關(guān)系的操作状囱；僅改變與實例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成倘是。如果不存在這樣的對象亭枷，則應(yīng)該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創(chuàng)建時完成這一操作搀崭，以防止對映射進行意外的不同步訪問叨粘，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));
由所有此類的“集合視圖方法”所返回的迭代器都是快速失敗 的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對映射進行修改瘤睹，除非通過迭代器自身的 remove 或 add 方法升敲，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException默蚌。因此冻晤，面對并發(fā)的修改苇羡，迭代器很快就會完全失敗绸吸，而不冒在將來不確定的時間任意發(fā)生不確定行為的風(fēng)險。

注意设江，迭代器的快速失敗行為不能得到保證锦茁，一般來說，存在不同步的并發(fā)修改時叉存，不可能作出任何堅決的保證码俩。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException歼捏。因此稿存，編寫依賴于此異常程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤瞳秽。

此類是 Java Collections Framework 的成員瓣履。

三、HashMap存儲結(jié)構(gòu)

學(xué)習(xí)源碼之前练俐，最好在腦海中明確 HashMap 的存儲結(jié)構(gòu)袖迎，不然后面閱讀源碼，遇到容量、數(shù)量等參數(shù)可能會有些許困惑燕锥。
相信你已經(jīng)有所耳聞辜贵，HashMap 內(nèi)部包含了一個 Node 類型的數(shù)組 table。Node 存儲著鍵值對归形。

Node 類源碼如下：

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

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

public final K getKey() {
    return key;
}

public final V getValue() {
    return value;
}

public final String toString() {
    return key + "=" + value;
}

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;

    return oldValue;
}

public final boolean equals(Object o) {
    if (o == this) {
        return true;
    }

    if (o instanceof Map.Entry) {
        Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;

        if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue())) {
            return true;
        }
    }

    return false;
 }
}

它包含了四個字段托慨，從 next 字段我們可以看出 Node 是一個鏈表。即數(shù)組中的每個位置被當成一個桶连霉，一個桶存放一個鏈表榴芳。HashMap 使用鏈地址法來解決哈希沖突，即同一個鏈表中存放哈希值和散列桶取模運算結(jié)果相同的 Node跺撼。HashMap 存儲結(jié)構(gòu)如下圖所示：

image

四窟感、HashMap 靜態(tài)屬性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默認的 table 容量，1<<4 = 2^4 = 16歉井，規(guī)定必須是 2 的冪柿祈。

static final int MAXIMUM_CAPACITY = 1 << 30;

最大的 table 容量，規(guī)定必須是 2 的冪哩至，類型為 int躏嚎，掐指一算，那只能是 0100 0000 0000 0000 0000 0000 0000 0000菩貌。因為 Java中 int 有 32 位卢佣，除第 1 位符號位外，數(shù)值部分只有 31 位箭阶，只有 1<<30 滿足條件虚茶。

這里需要說明一下，對于 2 的冪仇参，在計算機的世界里是一群特殊的存在嘹叫，它們的二進制中只有一個1，其余位全為 0诈乒。這個特性會影響與它進行位運算后的結(jié)果具有一些特殊效果罩扇。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

構(gòu)造函數(shù)中未指定時使用的負載因子。

static final int TREEIFY_THRESHOLD = 8;

相信很多人知道鏈表長度大于 8 會轉(zhuǎn)為紅黑樹怕磨，依據(jù)也就是這個字段的注釋說明喂饥。但其實這只是條件之一，另一個條件就是下面這個參數(shù)肠鲫。

static final int MIN_TREEIFY_CAPACITY = 64;
在進行鏈表轉(zhuǎn)紅黑樹的時候员帮，第一步是檢查鏈表的長度是否大于等于 8，第二步會檢查 table 數(shù)組的容量是否小于此數(shù)值滩届，若小于集侯，則取消轉(zhuǎn)為紅黑樹被啼，只對 table 數(shù)組進行擴容。

static final int UNTREEIFY_THRESHOLD = 6;
當鍵值對數(shù)量過多時需要對 table 數(shù)組進行擴容棠枉，并且將每個鍵值對放到新的桶中（或者不變）浓体。原來的桶的內(nèi)部結(jié)構(gòu)有可能是鏈表，也有可能是紅黑樹辈讶，經(jīng)過一番洗牌之后命浴，如果桶結(jié)構(gòu)為紅黑樹的鍵值對數(shù)量過低，就會重新轉(zhuǎn)變?yōu)殒湵砑５偷侥膫€程度呢生闲？就是這個字段對應(yīng)的大小。

五月幌、HashMap 成員屬性

transient Node<K,V>[] table;
HashMap 的內(nèi)部 Node 類型的數(shù)組碍讯，屬性名為 table。

transient int modCount;
該字段起標記作用扯躺，值是對該 HashMap 進行結(jié)構(gòu)修改的次數(shù)捉兴，主要用于迭代器訪問時檢測 HashMap 是否因為刪除等其它操作內(nèi)部機構(gòu)發(fā)生變化。

transient Set<Map.Entry<K,V>> entrySet;
HashMap 內(nèi)部有很多內(nèi)部類录语，擴展了 HashMap 的一些功能倍啥，EntrySet 類就是其中一種，該類較為簡單澎埠，無內(nèi)部屬性虽缕，你可以理解為一個工具類，對 HashMap 進行了簡單的封裝蒲稳，提供了方便的遍歷氮趋、刪除等操作。

調(diào)用 HashMap 的 entrySet() 方法就可以返回 EntrySet 實例對象弟塞，為了不至于每次調(diào)用該方法都返回新的 EntrySet 對象凭峡，所以設(shè)置該屬性拙已，緩存 EntrySet 實例决记。

transient int size;
鍵值對的數(shù)量。

int threshold;
size 的臨界值倍踪，當 size 大于 threshold 就必須進行擴容操作系宫。

final float loadFactor;
負載因子，被 final 修飾建车，在構(gòu)造方法中就被初始化扩借，不指定就用默認的。

六缤至、HashMap 構(gòu)造方法

HashMap 的共有三個構(gòu)造方法潮罪，源碼如下：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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);
}

初看源碼，可以發(fā)現(xiàn)，被 final 修飾的 loadFactor 一定會在構(gòu)造方法中被初始化嫉到。

帶參構(gòu)造方法主要做的就是對 initialCapacity 和 loadFactor 的校驗工作沃暗，并且會通過 tableSizeFor 方法計算其合理的初始容量，由于此時 table 數(shù)組尚未實例化何恶，所以該合理的初始容量被暫存在 threshold 屬性中孽锥，由其代為保管。

七细层、tableSizeFor(int cap) 方法

tableSizeFor(int cap) 靜態(tài)方法的作用是計算其合理的初始容量惜辑，也就是滿足 2 的冪，且大于等于參數(shù) cap疫赎，最接近的那一個數(shù)即可盛撑。該方法使用位運算設(shè)計了高效的算法邏輯，方法源碼如下：

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;
}

參數(shù) cap 的值肯定大于 0捧搞，故 n 大于等于 0 撵彻，假設(shè) n = 0，經(jīng)過右移之后实牡，依舊為 0 陌僵，0 與 0 異或依舊為 0 ，通過 return 語句的 n+ 1 計算得 1创坞，即 2 的 0 次冪碗短。

當 n 大于 0 時，n 的二進制位肯定會有位的值為 1题涨，即 001xx..xx 的形式偎谁，接著，對 n 右移 1 位得 0001xx..xx纲堵，再進行位或巡雨，由于 1 與 0 或 1 異或結(jié)果都為 1，所以結(jié)果必為 0011xx..xx 的形式席函。以此類推铐望，位移 2 位、4 位茂附、8 位正蛙、 16 位，最終該算法能讓最高位的 1 后面的所有位全變?yōu)?1营曼。

下面用一張圖舉例說明一下：

image

該算法的最后再讓結(jié)果值 n + 1乒验，所得即為 2 的整數(shù)次冪。為了讓結(jié)果使結(jié)果大于等于參數(shù) cap蒂阱，在算法開始時锻全，令 cap - 1狂塘。

八、hash(Object key) 方法

該方法是 HashMap 的核心靜態(tài)方法鳄厌，用于計算 key 的 hash 值睹耐，該方法的源碼如下：

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

方法邏輯很簡單，key 為 null 返回 0部翘，根據(jù)桶下標計算公式 (capacity - 1) & hash硝训，以及 0 與 0 或 1 位與結(jié)果均為 0，可知新思，null 鍵對應(yīng)的桶下標為 0 窖梁。

當 key 不為 null 時，調(diào)用 key.hashCode() 并將 hashCode 的低 16 位與高 16 位異或夹囚。

這步操作是因為 table 數(shù)組使用 2 的冪作為容量纵刘，且計算桶下標是通過 (capacity - 1) & hash，所以僅在當前容量上方的位中變化的 hashCode 將始終發(fā)生沖突荸哟。

舉個例子假哎，初始容量為 16，hash 值按 32 位計算：

16 = 10000（二進制）
16 - 1 =  0000 0000 0000 0000 0000 0000 0000 1111
hash1 = 0000 0000 0000 0000 0000 0000 0001 1111
hash2 = 0000 0000 0000 0000 0000 0000 0011 1111

因為 0 與任何數(shù)位與 & 的結(jié)果都是 0 鞍历，所以無論 hash 值是多少舵抹，計算后除后 4 位外的位必定都為 0，如果 hash 值只在前 32 - 4 = 28 位發(fā)生變化劣砍，計算后的結(jié)果都是相同的惧蛹，都會放入同一個桶中，始終發(fā)生沖突刑枝。

因此香嗓，設(shè)計者們在速度，實用性和位擴展質(zhì)量之間進行權(quán)衡后應(yīng)用了一種變換装畅，通過將 hashcode 的低 16 位與高 16 位異或向下傳播較高位的影響靠娱。

由于許多常見的哈希值已經(jīng)合理分布（比如 hash 值的前 16 位都為 0 的一些數(shù)，它們的低 16 位與 高 16 位異或后值不變掠兄，因此無法從擴展中受益）像云，并且由于我們使用樹來處理容器中的大量沖突，因此我們僅以最方便的方式對一些移位后的位進行異或徽千，以減少系統(tǒng)損失苫费，以及合并最高位的影響汤锨，否則由于 table 數(shù)組容量的限制双抽，這些位將永遠不會在索引計算中使用。

九闲礼、桶下標計算公式

計算桶下標時牍汹，需要先通過 HashMap 內(nèi)部的 hash() 方法計算其 hash 值铐维，然后將 hash 值對桶個數(shù)取模，即：

hash % capacity
如果能保證 capacity 為 2 的冪慎菲，那么就可以將這個操作轉(zhuǎn)換為高效的位運算嫁蛇，也就是 HashMap 源碼中的桶下標計算公式：

(capacity - 1) & hash
以上便是 HashMap 內(nèi)部數(shù)組的容量為 2 的冪的其中一個原因，另一個原因是在 resize() 擴容方法中可以更高效的重新計算桶下標露该。

十睬棚、put(K key, V value) 方法

該方法將指定值與該映射中的指定鍵相關(guān)聯(lián)。若是 Key 已存在解幼，則覆蓋并返回舊的 Value（可為 null）抑党；若是沒有鍵值對映射，則返回 null撵摆。該方法源碼如下：

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

可以看到底靠，該方法實際是封裝的 putVal() 方法。putVal() 方法有 5 個參數(shù)特铝，依次為 key 的 hash 值暑中，key 本身，value 本身鲫剿，參數(shù) onlyIfAbsent 表示是否在鍵已存在的情況放棄覆蓋舊值鳄逾，參數(shù) evict 作為 afterNodeInsertion(evict) 方法的參數(shù)，并不為 HashMap 所用灵莲，而是交由 LinkedHashMap 處理严衬。

該方法的源碼如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步驟①：table為空則創(chuàng)建
    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 {
        // 步驟③：發(fā)生hash碰撞笆呆，若鍵已存在就返回該Node请琳，并用屬性 e 引用，若鍵不存在就創(chuàng)建一個新的Node赠幕，并直接插入到桶中
        Node<K,V> e; K k;
        // 檢查碰撞的節(jié)點是否是頭節(jié)點
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 若該桶的內(nèi)部結(jié)構(gòu)是樹
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 若該桶的內(nèi)部結(jié)構(gòu)是鏈表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 直接插入新節(jié)點到鏈表的尾部
                    p.next = newNode(hash, key, value, null);
                    // 鏈表長度大于8轉(zhuǎn)為紅黑樹處理
                    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;
            }
        }
        // 步驟④：該鍵已經(jīng)存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 直接覆蓋俄精，并返回舊值
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 步驟⑤：檢查鍵值對數(shù)量是否超過臨界值，是則擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

十一榕堰、resize() 方法

該方法的作用是初始化 table 數(shù)組竖慧，或增加 table 數(shù)組的大小。

如果 table 數(shù)組為 null逆屡，則根據(jù)字段 threshold 中保持的初始容量進行分配圾旨。否則擴容，因為我們使用的是 2 的冪魏蔗，所以每個桶中的元素必須保持相同的索引砍的，或者在新 table 中以 2 的冪偏移。

舉個例子莺治，例如容量從 16 擴展為 32 時廓鞠，具體變化如下：

16-1  =  0000 0000 0000 0000 0000 0000 0000 1111
hash1 =  0000 0000 0000 0000 0000 0000 0000 1111
hash2 =  0000 0000 0000 0000 0000 0000 0001 1111
// 桶下標為
(16-1)&hash1 = 0000 0000 0000 0000 0000 0000 0000 1111
(16-1)&hash2 = 0000 0000 0000 0000 0000 0000 0000 1111
容量為 16 時帚稠，hash1 和 hash2 經(jīng)過桶下標計算后結(jié)果相同，會進入同一個桶中床佳。當容量擴展為 32 后滋早，新的桶下標計算過程如下所示：

32-1  =  0000 0000 0000 0000 0000 0000 0001 1111
hash1 =  0000 0000 0000 0000 0000 0000 0000 1111
hash2 =  0000 0000 0000 0000 0000 0000 0001 1111
// 桶下標為
(32-1)&hash1 = 0000 0000 0000 0000 0000 0000 0000 1111
(32-1)&hash2 = 0000 0000 0000 0000 0000 0000 0001 1111

hash1 和 hash2 經(jīng)過桶下標公式重新計算之后，hash1的結(jié)果不變砌们，所以依舊在原來的桶里杆麸；而 hash2 的結(jié)果比原來多了 1 位，即 2^4 = 16浪感，也就是偏移了原來的容量大小角溃。如下圖所示：

image

因此，在擴充 HashMap 的時候篮撑，不需要重新計算 hash减细，只需要檢查二進制 hash 中與二進制桶下標中新增的有效位的位置相同的那個位（以下簡稱“新增位”）是 0 還是 1 即可，是 0 的話索引沒變赢笨，是 1 的話索引變成“原索引+oldCap”未蝌。

如何檢查新增位是 0 還是 1 呢？HashMap 中使用 hash & oldCap 位與運算檢查該新增位茧妒。oldCap 是 2 的冪萧吠，故二進制表示只有 1 位是 1，且該位正好與之對應(yīng)桐筏。不得不說這個設(shè)計還是非常巧妙的纸型，既省去了重新計算 hash 值的時間，而且梅忌，由于新增的 1 位是 0 還是 1 可以認為是隨機的狰腌，因此在擴容的過程，均勻的把之前碰撞的節(jié)點分散到新舊桶中牧氮。

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;
    // 步驟①：根據(jù) oldCap 判斷是擴容還是初始化數(shù)組琼腔，若是擴容..
    if (oldCap > 0) {
        // 超過最大容量就不再擴容，隨它去碰撞
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 沒超過最大值踱葛，就擴容為原來的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 步驟②：若是初始化數(shù)組丹莲，若是字段 threshold 中已經(jīng)保存初始容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 步驟③：若是初始化數(shù)組，若是字段 threshold 中沒有保存初始容量尸诽，則使用默認容量
    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"})
    // 步驟⑤：實例化新的 table 數(shù)組
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 步驟⑥：將每個桶及內(nèi)部節(jié)點都移到新的 table 數(shù)組中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 去掉舊數(shù)組對該桶的引用
                oldTab[j] = null;
                // 若是該桶無哈希碰撞甥材，重新計算桶下標
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 若是該桶內(nèi)部結(jié)構(gòu)為樹
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 若是該桶內(nèi)部結(jié)構(gòu)為鏈表，則碰撞的節(jié)點要么在原桶性含，要么在新桶
                else { // preserve order
                    // 原桶的頭尾節(jié)點引用
                    Node<K,V> loHead = null, loTail = null;
                    // 新桶的頭尾節(jié)點引用
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 循環(huán)遍歷桶內(nèi)碰撞節(jié)點
                    do {
                        next = e.next;
                        // 新增位是 0 放原桶
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 新增位是 1 放新桶
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原桶放新 table 數(shù)組
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 新桶放新 table 數(shù)組
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

十二洲赵、get(Object key) 方法

該方法返回指定鍵所映射到的值，如果不包含該鍵對應(yīng)的映射關(guān)系，則返回 null板鬓。

返回值為 null 不一定表示不包含該鍵對應(yīng)的映射關(guān)系悲敷，也可能表示該鍵對應(yīng)的值為 null究恤。如果需要驗證是否存在該鍵對應(yīng)的映射關(guān)系可以調(diào)用 containsKey() 方法俭令。

該方法的源碼如下：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
方法內(nèi)部調(diào)用的 getNode() 方法，參數(shù)為 key 的 hash 值與 key 本身部宿，方法的源碼如下：

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) {
        // 步驟②：每次 get 都要先檢查該桶頭節(jié)點是否是要找的鍵值對抄腔，因為不存在哈希碰撞的可能性較大
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 步驟③：若是該桶存在哈希碰撞，則遍歷桶內(nèi)節(jié)點
        if ((e = first.next) != null) {
            // 如果桶的內(nèi)部結(jié)構(gòu)是樹..
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 如果桶的內(nèi)部結(jié)構(gòu)是鏈表..
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

十三理张、treeifyBin(Node[] tab, int hash) 方法

在前面對 put 操作的介紹中赫蛇，當鏈表的長度大于等于 TREEIFY_THRESHOLD 也就是 8 時，會調(diào)用 treeifyBin() 方法將桶的結(jié)構(gòu)由 Node 轉(zhuǎn)為 TreeNode雾叭，即鏈表轉(zhuǎn)化為紅黑樹悟耘。但嚴格來說，這句話不應(yīng)該如此表述织狐。因為 treeifyBin() 方法會判斷當前 table 數(shù)組的容量是否小于 MIN_TREEIFY_CAPACITY（64）暂幼，若是，則放棄鏈表轉(zhuǎn)為紅黑樹移迫，而選擇擴容旺嬉。

該方法的源碼如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果當前 table 數(shù)組的容量小于 64 就放棄樹化，選擇擴容厨埋。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 鏈表轉(zhuǎn)為紅黑樹
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd：鏈表頭節(jié)點邪媳，tl：鏈表尾節(jié)點
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 將Node轉(zhuǎn)為TreeNode，并保持鏈表的結(jié)構(gòu)
            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);
        if ((tab[index] = hd) != null)
            // 這一步才是真正的鏈表轉(zhuǎn)為紅黑樹
            hd.treeify(tab);
    }
}

十四荡陷、TreeNode.treeify(Node[] tab) 方法

HashMap 的桶類型除了 Node（鏈表）外雨效，還有 TreeNode（樹）。TreeNode 類包含成員方法 treeify()废赞，該方法的作用是形成以當前 TreeNode 對象為根節(jié)點的紅黑樹设易。該方法源碼如下：

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 步驟①：遍歷當前TreeNode鏈表
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // 步驟②：如果還未設(shè)置根節(jié)點..
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        // 步驟③：如果已設(shè)置根節(jié)點..
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 步驟④：從根節(jié)點開始遍歷，插入新節(jié)點
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 步驟⑤：比較當前節(jié)點的hash值與新節(jié)點的hash值
                // 若是新節(jié)點hash值較小
                if ((ph = p.hash) > h)
                    dir = -1;
                // 若是新節(jié)點的hash值較大
                else if (ph < h)
                    dir = 1;
                // 若是新節(jié)點與當前節(jié)點的hash值相等
                else if (
                    // 如果新節(jié)點的key沒有實現(xiàn)Comparable接口..
                    (kc == null && (kc = comparableClassFor(k)) == null)
                    // 或者實現(xiàn)了Comparable接口但是k.compareTo(pk)結(jié)果為0
                    ||(dir = compareComparables(kc, k, pk)) == 0)
                    // 則調(diào)用tieBreakOrder繼續(xù)比較大小
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                // 步驟⑥：如果新節(jié)點經(jīng)比較后小于等于當前節(jié)點且當前節(jié)點的左子節(jié)點為null蛹头，則插入新節(jié)點顿肺，反之亦然
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 步驟⑦：平衡紅黑樹
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 步驟⑧：確保給定的根節(jié)點是所在桶的第一個節(jié)點
    moveRootToFront(tab, root);
}