[JDK8] HashMap源碼解析

文章标題

- 寫在前面
- 底層存儲結構
- 構造HashMap
- - tableSizeFor(int cap)
- HashMap添加/更新
- - hash(key)
  - putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
  - treeifyBin(Node<K,V>[] tab, int hash)
  - resize()
- HashMap删除
- HashMap查找
- 線程安全

寫在前面

HashMap

的實作思想太有含金量了，方方面面都有值得細細品鑒的，想用一篇文章分析透徹，還是比較難的。

我也就是把這麼多年的了解嘗試着總結一下，寫的倉促，可能有錯誤的地方，歡迎指正！

底層存儲結構

HashMap

底層存儲結構是數組：

Node<K,V>

是

HashMap

中定義的一個節點類，用于存儲

(key, value)

鍵值對形式的對象：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // 省略其它
}

其中包含四個屬性：

key ：鍵值對的 key 值
value ：鍵值對的 value 值
hash ： key 的哈希值，用于計算節點在數組 table 中的存儲位置
next ：具有相同 hash 值的節點，會存儲在數組 table 相同的位置，多個節點之間構成連結清單，數量超過 8 個後，轉換成紅黑樹結構

因為數組 + 連結清單/紅黑樹這種存儲結構就像是一張二維關系表，是以

Node<K,V>[]

取名

table

，更能表達存儲結構的含義。

構造HashMap

HashMap

的構造方法有

個：

public HashMap() {...}
public HashMap(int initialCapacity) {...}
public HashMap(int initialCapacity, float loadFactor) {...}
public HashMap(Map<? extends K, ? extends V> m) {...}

最常用的是前兩個構造方法。

第一個沒什麼好說的，就是一行配置

loadFactor

預設值的代碼。

第二個最有意思，傳入了一個構造參數

initialCapacity

，這個參數是用來設定數組

table

初始長度的。

說它有意思，是因為

initialCapacity

參數并不是直接拿來用的，它經過了一次二進制轉換，變成了另外一個數值：最接近的但不小于initialCapacity本身的2的幂次方。

tableSizeFor(int cap)

跟蹤構造方法，可以發現

initialCapacity

參數最終會傳遞給這個方法，源碼如下：

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

為了更好的了解轉換過程，舉幾個例子：

構造參數為3，該方法就傳回4；
構造參數為10，該方法就傳回16；
構造參數為32，該方法就傳回32，因為32本身就是2的幂次方

假設方法參數

cap = (1<<30) + 1

，那麼

n = 1<<30

，有如下轉換過程：

01000000 00000000 00000000 00000000 (n)
01100000 00000000 00000000 00000000 (n |= n >>> 1)
01111000 00000000 00000000 00000000 (n |= n >>> 2)
01111111 10000000 00000000 00000000 (n |= n >>> 4)
01111111 11111111 10000000 00000000 (n |= n >>> 8)
01111111 11111111 11111111 11111111 (n |= n >>> 16)

認真體會源碼及示例，

tableSizeFor

方法告訴了我們三件事情：

第一，2的幂次方是怎麼轉換的

轉換過程是通過

>>>

和

兩個操作完成，全部執行完以後，第一個二進制

之後的位空間就都會變成

，最後

return

的時候再執行個

n+1

就能得到

的幂次方，巧妙！

第二，tableSizeFor的轉換最大值

Java

中的

int

是有符号類型，占用

32bit

空間，第一個

bit

是符号位，

表示正數，

表示負數。

當

n = 1<<30

的時候，

n |= n >>> 16

得到的結果就是

int

的最大值，再執行

n+1

操作，最大值就會溢出，變成最小值。

是以，

不能大于

1<<30

，進而推導可得

cap

最大值為

1<<30

，剛好是

1G

。

也就是說，通過

tableSizeFor

轉換能得到的最大值是

的

次方，這就是

1G

，最大容量字段

MAXIMUM_CAPACITY

定義的由來：

第三，先減1再加1的作用

首先提出疑問：

tableSizeFor

方法第一行先做了個減法操作

n = cap - 1

，最後

return

的時候又做了個加法操作

n + 1

，為什麼？多此一舉？

并非多此一舉，減

加

是為了保證方法參數

cap

剛好等于

的幂次方時，轉換結果還是它本身，例如

cap = 128

時：

00000000 00000000 00000000 10000000 (cap = 128)
00000000 00000000 00000000 01111111 (n = cap - 1)
00000000 00000000 00000000 01111111 (n |= n >>> 1)
00000000 00000000 00000000 01111111 (n |= n >>> 2)
00000000 00000000 00000000 01111111 (n |= n >>> 4)
00000000 00000000 00000000 01111111 (n |= n >>> 8)
00000000 00000000 00000000 01111111 (n |= n >>> 16)
00000000 00000000 00000000 10000000 (return n + 1)

這就是二進制運算特性，巧妙！

最後的結果指派給了屬性變量

threshold

：

int threshold;
this.threshold = tableSizeFor(initialCapacity);

變量

threshold

是門檻值的意思，表示的含義是

HashMap

中存儲的元素超過這個數值的時候，底層數組

table

就要進行擴容了。

數組初始化之前，threshold不是門檻值的意思，這點要了解！

通過構造函數初始化

HashMap

對象之後，底層數組

table

并沒有被配置設定數組空間，此時的

threshold

儲存着數組初始長度資訊，還不是門檻值的含義！

HashMap

首次添加元素時，第一次為數組

table

配置設定空間，通過

threshold

得知第一次配置設定的數組的長度。之後，

threshold

會被重新計算，再往後才是門檻值的含義。

threshold

計算方法是：

int threshold = table.length * loadFactor

負載因子

loadFactor

預設是

0.75

：

負載因子

loadFactor

也可以在通過構造方法指定。

HashMap添加/更新

向

HashMap

添加

(key, value)

的鍵值對象，最常用的方法是：

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

順着這個方法追下去，就是完整的添加/更新邏輯。

hash(key)

添加第一步，就

key

做了一個哈希處理：

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

從中可以看到兩個知識點：

key == null ：哈希值是，是以，鍵值對象 (null,value) 永遠存儲在數組 table 的号位置，也就是第一個位置
key != null ：在 JVM 預設哈希值的基礎上，又做了一個變換，讓哈希值二進制高 16bit 參與到低 16bit 運算中

為了更好地了解，舉個具體的例子，假設

key

的哈希值是

16711680

：

00000000 11111111 00000000 00000000 (h = key.hashCode())
00000000 00000000 00000000 11111111 (h >>> 16)
00000000 11111111 00000000 11111111 (h ^ h >>> 16)

通過

Java

已有的方法

hashCode()

就可以計算出一個随機的哈希值，為什麼非要再轉換一次呢？為什麼要将哈希值的高

16bit

資料融合到低

16bit

裡面呢？

回答這個問題之前，先了解另一個知識點：

hash

值映射到數組

table

下标值的規則。

int h = key.hashCode();   // Object方法計算出的哈希值
int hash = h ^ h >>> 16;  // 哈希值高16bit融合進低16bit
int n = table.length;     // 數組table的長度
int i = (n - 1) & hash;   // hash值映射到數組下标
table[i] = value;         // 數組指派Node<K,V>對象

這段代碼是追蹤源碼後，得到的哈希值映射邏輯，映射規則是

(n - 1) & hash

。

這是個掩碼映射思想，可類比網絡

IP

設定中的掩碼。

截止到目前，數組

table

的長度始終都是

的幂次方，

n - 1

得到的就是高位一串0，低位一串1的二進制數字，也是數組下标的最大值。

舉個例子：

00000000 00000000 00000000 00010000 (n = table.length = 16)
00000000 00000000 00000000 00001111 (n - 1)
00000100 00100110 00100101 10001010 (hash)
00000000 00000000 00000000 00001010 (i = (n - 1) & hash)

計算出數組下标

i = 10

，由此可以看出，

hash

真正能決定數組下标位置的的隻有幾個低位二進制數值，高位二進制對映射規則沒有影響。

實際使用

HashMap

的時候，存儲元素的個數通常不會超過

的

次方，也就是

個。

在這個實際應用場景的限制下，計算出來的

hash

最多隻有低

16bit

有用，高

16bit

完全沒用。如果兩個

hash

低

16bit

相同，高

16bit

不同，它們就會被映射到同一個數組下标，存儲在同一個位置。

把

hash

二進制的高

16bit

融合進低

16bit

，就會改變低

16bit

的數值，進而得到不同的數組下标，存儲在不同的位置。

現在可以回答之前的問題了：

HashMap

之是以要再次計算

hash

，将高

16bit

資料融合進低

16bit

，是為了在實際應用中，得到更好的哈希散列性，降低哈希碰撞的機率。

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

這是

HashMap

添加/更新元素的核心方法，源碼如下，排版有壓縮：

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

從這段代碼裡，可以整理出添加/更新邏輯：

首次添加元素時，數組 table 進行第一次初始化
根據哈希映射規則 (n - 1) & hash 計算出數組下标 i
如果 table[i] == null ，建立 Node<K,V> 對象，封裝插入資訊，插入數組 table[i]
如果 table[i] != null ，說明 table[i] 可能是一個 Node<K,V> 連結清單，也可能是一個紅黑樹 TreeNode
如果 table[i] 是一個 Node<K,V> 連結清單，就執行連結清單的新增/更新邏輯
如果 table[i] 是一顆 TreeNode 紅黑樹，就執行紅黑樹的新增/更新邏輯
如果連結清單新增元素後，連結清單長度超過 8 個，就立刻将連結清單轉換成紅黑樹結構。這麼說其實是不太對的，但是為了講述友善先這麼了解吧，後面講紅黑樹結構的時候，會說明為什麼不對
新增元素時，如果是連結清單結構，就添加連結清單尾部，如果是紅黑樹，就根據樹的特性添加到合适位置。但是還要知道， HashMap 使用紅黑樹的時候，依舊記錄着連結清單資訊，在這個連結清單資訊裡面，元素依然是在最後的
如果兩個元素的 hash 和 key 相同，就說明是相同的元素，執行更新操作，更新元素 value 值
方法參數 onlyIfAbsent == true 時，表示 HashMap 隻能新增元素，不能更新元素
如果是更新元素，方法傳回值是更新前的元素 value 值，如果是新增操作，方法傳回的是 null
如果集合元素數量 size 超過 threshold 門檻值，就進行擴容操作
每次新增/更新完成後，都會執行一個操作 ++modCount ，這個字段記錄的是集合寫次數，跟疊代器的使用有密切聯系，可以達到疊代器的 fail-fast 效果

treeifyBin(Node<K,V>[] tab, int hash)

這個就是連結清單結構轉化成紅黑樹的方法，源碼如下，排版略有壓縮：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null) hd.treeify(tab);
    }
}

從中整理出轉換邏輯：

如果數組 table.length < 64 ，隻進行擴容操作，不會進行紅黑樹轉換。這是 HashMap 連結清單轉換紅黑樹的另一個條件，數組長度需要滿足門檻值條件 MIN_TREEIFY_CAPACITY = 64
紅黑樹轉換過程，是先将 Node<K,V> 連結清單封裝成 TreeNode<K,V> 連結清單，然後再通過 treeify(Node<K,V>[] tab) 方法真正将其轉換成紅黑樹。是以轉換後，這些元素組成的結構既是紅黑樹，又是連結清單，兩者特性兼而有之！贊歎！巧妙！

resize()

當

HashMap

首次添加元素，或者，添加元素後

HashMap

元素數量超過

threshold

時，數組

table

就會進行擴容操作。

擴容過程包含兩件事情：

擴大底層數組 table 容量，也就是擴大 HashMap 的哈希槽，可以容納更多的 key
哈希槽增加後，集合元素需根據 hash 值重新映射數組 table 下标位置，這個過程叫做重哈希

這兩件事情都是在

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) {
        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;
    // 以下是重哈希部分，省略
}

閱讀這段代碼，可以理出數組擴容的邏輯：

table 第一次初始化時， threshold 表示數組長度資訊，如果沒有指定，就使用預設值 DEFAULT_INITIAL_CAPACITY = 16
預設負載因子是 DEFAULT_LOAD_FACTOR = 0.75f ，表示當集合元素數量達到 table.length * 0.75 的時候，就觸發擴容機制
擴容時，數組長度以 2 倍的速度遞增，建立 2 倍長度新數組，取代原數組
數組長度最大值是 Integer.MAX_VALUE ，它跟 MAXIMUM_CAPACITY 的關系是 Integer.MAX_VALUE = MAXIMUM_CAPACITY * 2 - 1
當數組長度達到 Integer.MAX_VALUE 時， threshold 門檻值也會設定成 Integer.MAX_VALUE

理清了擴容的邏輯，再來看看重哈希的邏輯，相關源碼：

final Node<K,V>[] resize() {
    // 以上是數組擴容邏輯，省略
    Node<K,V>[] oldTab = table;
    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, hiHead = null, hiTail = null, 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;
}

源碼有點長，排版上做點壓縮。分析這段代碼，理出重哈希邏輯：

基本思路，周遊原數組，根據 hash 計算元素在新數組中的存儲位置，存入新數組
原數組 table[j] ，可能是 null ，可能是一個 Node<K,V> 對象，也可能是多個 Node<K,V> 對象組成的連結清單，還可能是個 TreeNode<K,V> 紅黑樹
如果 table[j] == null ，說明這個位置沒有存儲對象，也就不需要處理
如果 table[j] 隻是一個 Node<K,V> 對象，直接計算新的下标值 e.hash & (newCap - 1) ，存入新數組即可
如果 table[j] 是一個 Node<K,V> 連結清單，就根據規則 e.hash & oldCap 将其拆分成兩個連結清單，分别存儲在新數組 newTab[j] 和 newTab[j + oldCap] 的位置。這與直接計算元素下标 e.hash & (newCap - 1) 效果是一樣的，且更為簡單直接
如果 table[j] 是一個 TreeNode<K,V> 紅黑樹，拆分就稍微複雜一點，需要詳細分析 TreeNode<K,V> 的 split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) 方法，這裡先擱置，另起一節細說

對于第

點和第

點，有必要單獨拿出來再細說一下。

關于第5點

舉個例子，了解

table[j]

是個

Node<K,V>

連結清單的情況：

假設目前

HashMap

為

，現有兩個

Node<K,V>

對象

node1

和

node2

，它們的資訊如下：

n = table.length = 8

node1.hash == 0001
(n - 1) & hash = 0111 & 0001 = 0001 = 1
node2.hash == 1001
(n - 1) & hash = 0111 & 1001 = 0001 = 1

table[1] = node1, node2

是以，

node1

和

node2

分别都存儲在數組

table[1]

的位置，形成連結清單。

現在要進行擴容，重哈希，

node1

和

node2

在新數組中的情況：

oldCap = 8
n = table.length = 16

node1.hash == 0001
(n - 1) & hash = 01111 & 0001 = 0001 = 1
table[1] = node1 // 連結清單拆分規則：hash & oldCap = 0001 & 1000 = 0000

node2.hash == 1001
(n - 1) & hash = 01111 & 1001 = 1001 = 9
table[9] = node2 // 連結清單拆分規則：hash & oldCap = 1001 & 1000 = 1000

可以發現，其實有兩種規則方法，可以完成擴容時的重哈希操作：

哈希映射規則： (n - 1) & hash
連結清單拆分規則： hash & oldCap

關于第6點

拆分紅黑樹後需要考慮的問題是拆分後的兩個結構應該如何存儲？是使用

TreeNode<K,V>

紅黑樹結構？還是使用

Node<K,V>

連結清單結構？

相關源碼如下：

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;
    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) {
        if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) loHead.treeify(tab); // (else is already treeified)
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null) hiHead.treeify(tab);
        }
    }
}

整理出拆分邏輯：

因為 TreeNode<K,V> 本身也儲存有連結清單資訊，是以先根據上面第 5 點講的連結清單拆分規則 hash & oldCap 将其拆分成兩個子連結清單
如果子連結清單長度不大于 UNTREEIFY_THRESHOLD = 6 這個門檻值，就轉換成 Node<K,V> 連結清單，存入新數組對應位置
如果子連結清單長度大于 UNTREEIFY_THRESHOLD = 6 這個門檻值，就轉換成 TreeNode<K,V> 紅黑樹，存入新數組對應位置

關于連結清單和紅黑樹互轉的小總結：

連結清單轉紅黑樹的時候，需要元素數量大于等于 9
紅黑樹轉連結清單的時候，需要元素數量小于等于 6

HashMap删除

删除邏輯相對簡單，核心源碼是：

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))))
            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) tab[index] = node.next;
            else p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

邏輯整理如下：

根據 hash 規則映射數組 table 下标 i ，如果 table[i] == null ，證明元素不存在，無需删除，直接傳回 null
如果 table[i] != null ，那麼 table[i] 可能是連結清單，也可能是紅黑樹，是以要區分節點類型，從連結清單中查找，或者從紅黑樹中查找
如果找到元素，就從相應結構中删除，并傳回删除元素
方法參數 matchValue == true ，表示删除的時候，不僅要 key 相等，而且 value 也要相等，才能删除。當然，這個特性很少用到
方法參數 matchValue == false ，表示從紅黑樹結構中删除元素後，不重新移動樹的其它節點。這個也不常用，僅作了解

HashMap查找

查找邏輯也簡單，核心源碼：

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 && ((k = first.key) == key || (key != null && key.equals(k))))  // always check first node
            return first;
        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);
        }
    }
    return null;
}

邏輯整理如下：

根據 hash 映射數組 table 下标位置 i
如果 table[i] == null ，說明沒有該元素，傳回 null
如果 table[i] != null ，說明 table[i] 可能是連結清單，可能是紅黑樹
如果 table[i] 是連結清單，就以連結清單方式找，有就傳回節點，沒有就傳回 null
如果 table[i] 是紅黑樹，就以紅黑樹方式找，有就傳回節點，沒有就傳回 null
如果存在節點，上層的封裝方法 get(Object key) 也就是從節點中再傳回節點的 value 值就行了

線程安全

并發場景下，

HashMap

是非線程安全的。

如果要線程安全，就用

ConcurrentHashMap

類。

數組

table

擴容、集合資料重哈希，這兩個過程是最容易出現線程問題的。

因為随着集合資料量的增加，重哈希是一個比較耗時的操作，擴容過程其實就是原有集合資料重新寫入新數組的過程。

多線程場景下，短時間内向同一個地方大量寫入資料，就是容易出現線程安全問題。

如果出現線程安全問題，

HashMap

最可能出現的現象就是資料丢失，具體過程就不分析了。

寫的夠多了，就到這裡吧，

Markdown

編輯器已經頂不住了，太卡了。

[JDK8] HashMap源碼解析

文章标題

寫在前面

底層存儲結構

構造HashMap

tableSizeFor(int cap)

HashMap添加/更新

hash(key)

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

treeifyBin(Node<K,V>[] tab, int hash)

resize()

HashMap删除

HashMap查找

線程安全

繼續閱讀

centos 下安裝 jdk

Mybatis源碼閱讀（一）：Mybatis初始化1.1 解析properties、settings前言入口引申結語

MyBatis源碼解析(一)——MyBatis初始化過程解MyBatis源碼解析(一)——MyBatis初始化過程解1. 準備工作2. MyBatis初始化過程

《資料結構》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明先附上文檔歸類目錄：部落客有話說：(已遷移到部落格園 ☛☛☛ 新部落格連結)

i = i++ 的困惑

一步一步解析集合架構ArrayList源碼（2）

Java1.8 對HashMap的resize()的了解

如何配置Eclipse進行Perl開發

JAVA導入項目報錯Description Resource PathLocation Type Java compiler level does not match the version of

Java中Integer和int的差別

數組複制

JDK6新特性

關于JSch的問題描述

基于jdk1.8的Vector源碼分析

如何提高個人開源網站源碼開發使用率

JBoss,Geronimo和Glassfish初窺