溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹經典數據結構HashMap以及逐行分析每一個關鍵點，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
基于JDK-8u261源碼分析
??HashMap是一個使用非常頻繁的鍵值對形式的工具類，其使用起來十分方便。但是需要注意的是，HashMap不是線程安全的，線程安全的是ConcurrentHashMap（Hashtable這種過時的工具類就不要再提了），在Spring框架中也會用到HashMap和ConcurrentHashMap來做各種緩存。從Java 8開始，HashMap的源碼做了一定的修改，以此來提升其性能。首先來看一下HashMap的數據結構：
??整體上可以看作是數組+鏈表的形式。數組是為了進行快速檢索，而如果hash函數沖突了的話，就會在同一個位置處后面進行掛鏈表的操作。也就是說，同一個鏈表上的節點，它們的hash值計算出來都是一樣的。但是如果hash沖突比較多的時候，生成的鏈表也會拉的比較長，這個時候檢索起來就會退化成遍歷操作，性能就比較低了。在Java 8中為了改善這種情況，引入了紅黑樹。
??紅黑樹是一種高級的平衡二叉樹結構，其能保證查找、插入、刪除的時間復雜度最壞為O(logn)。在大數據量的場景下，相比于AVL樹，紅黑樹的插入刪除性能要更高。當鏈表中的節點數量大于等于8的時候，同時當前數組中的長度大于等于MIN_TREEIFY_CAPACITY時（注意這里是考點！所以以后不要再說什么當鏈表長度大于8的時候就會轉成紅黑樹，這么說只會讓別人覺得你沒有認真看源碼），鏈表中的所有節點會被轉化成紅黑樹，而如果當前鏈表節點的數量小于等于6的時候，紅黑樹又會被退化成鏈表。其中MIN_TREEIFY_CAPACITY的值為64，也就是說當前數組中的長度（也就是桶bin的個數）必須大于等于64的時候，同時當前這個鏈表的長度大于等于8的時候，才能轉化。如果當前數組中的長度小于64，即使當前鏈表的長度已經大于8了，也不會轉化。這點需要特別注意。以下的treeifyBin方法是用來將鏈表轉化成紅黑樹操作的：
1/**
2 * Replaces all linked nodes in bin at index for given hash unless
3 * table is too small, in which case resizes instead.
4 */
5final void treeifyBin(Node<K,V>[] tab, int hash) {
6 int n, index; Node<K,V> e;
7 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
8 resize();
9 else if ((e = tab[index = (n - 1) & hash]) != null) {
10 TreeNode<K,V> hd = null, tl = null;
11 do {
12 TreeNode<K,V> p = replacementTreeNode(e, null);
13 if (tl == null)
14 hd = p;
15 else {
16 p.prev = tl;
17 tl.next = p;
18 }
19 tl = p;
20 } while ((e = e.next) != null);
21 if ((tab[index] = hd) != null)
22 hd.treeify(tab);
23 }
24}??從上面的第7行和第8行代碼處可以看出，如果當前數組的長度也就是桶的數量小于MIN_TREEIFY_CAPACITY的時候，會選擇resize擴容操作，此時就不會走轉成紅黑樹的邏輯了。這里的意思就是說如果當前的hash沖突達到8的時候，根本的原因就是因為桶分配的太少才產生那么多沖突的。那么此時我選擇擴容操作，以此來降低hash沖突的產生。等到數組的長度大于等于MIN_TREEIFY_CAPACITY的時候，如果當前鏈表的長度還是8的話，才會去轉化成紅黑樹。
??由此可以看出加入MIN_TREEIFY_CAPACITY這個參數的意義就是在于要保證hash沖突多的原因不是因為數組容量少才導致的；還有一個意義在于，假如說當前數組的所有數據都放在了一個桶里面（或者類似于這種情況，絕大部分的節點都掛在了一個桶里（hash函數散列效果不好，一般不太可能出現）），此時如果沒有MIN_TREEIFY_CAPACITY這個參數進行限制的話，那我就會去開開心心去生成紅黑樹去了（紅黑樹的生成過程以及后續的維護還是比較復雜的，所以原則上是能不生成就不生成，后面會有說明）。而有了MIN_TREEIFY_CAPACITY這個參數進行限制的話，在上面的第8行代碼處就會觸發擴容操作。這里的擴容更多的意義在于把這個hash沖突盡量削減。比如把鏈表長度為8的八個節點再平分到擴容后新的兩倍數組的兩處新的桶里面，每個桶由原來的八個節點到現在的四個節點（也可能是一個桶5個另一個桶3個，極端情況下也可能一個桶8個另一個桶0個。但不管怎樣，從統計學上考量的話，原來桶中的節點數大概率會被削減），這樣就相當于減少了鏈表的個數，也就是說減少了在同一個位置上的hash沖突的發生。還有一點需要提一下，源碼注釋中說明MIN_TREEIFY_CAPACITY的大小要至少為4倍的轉成紅黑樹閾值的數量，這么做的原因也是更多的希望能減少hash沖突的發生。
??**那么為什么不直接用紅黑樹來代替鏈表，而是采用鏈表和紅黑樹來搭配在一起使用呢？**原因就在于紅黑樹雖然性能更好，但是這也僅是在大數據量下才能看到差異。如果當前數據量很小，就幾個節點的話，那么此時顯然用鏈表的方式會更劃算。因為要知道紅黑樹的插入和刪除操作會涉及到大量的自旋，以此來保證樹結構的平衡。如果數據量小的話，插入刪除的性能高效根本抵消不了自旋操作所帶來的成本。
??**還有一點需要留意的是鏈表轉為紅黑樹的閾值是8，而紅黑樹退化成鏈表的閾值是6。**為什么這兩個值會不一樣呢？可以試想一下，如果這兩個值都為8的話，而當前鏈表的節點數量為7，此時一個新的節點進來了，計算出hash值和這七個節點的hash值相同，即發生了hash沖突。于是就會把這個節點掛在第七個節點的后面，但是此時已經達到了變成紅黑樹的閾值了（MIN_TREEIFY_CAPACITY條件假定也滿足），于是就轉成紅黑樹。但是此時調用了一次remove操作需要刪掉這個新加的節點，刪掉之后當前紅黑樹的節點數量就又變成了7，于是就退化成了鏈表。然后此時又新加了一個節點，正好又要掛在第七個節點的后面，于是就又變成紅黑樹，然后又要remove，又退化成鏈表…可以看到在這種場景下，會不斷地出現鏈表和紅黑樹之間的相互轉換，這個性能是很低的，因為大部分的執行時間都花費在了轉換數據結構上面，而我僅僅是做了幾次連續的增刪操作而已。所以為了避免這種情況的發生，將兩個閾值錯開一些，以此來盡量避免在閾值點附近可能存在的、頻繁地做轉換數據結構操作而導致性能變低的情況出現。
??這里之所以閾值會選擇為8是通過數學統計上的結論得出的，在源碼中也有相關注釋：
其中中間的數字表示當前這個位置預計發生指定次數哈希沖突的概率是多少。可以看到當沖突概率為8的時候，概率已經降低到了0.000006%，幾乎是不可能發生的概率。從這里也可以看出，HashMap作者選擇這個數作為閾值是不希望生成紅黑樹的（紅黑樹的維護成本高昂）。而同樣負載因子默認選擇為0.75也是基于統計分析出來的，以下是源碼中對負載因子的解釋：
??負載因子衡量的是數組在擴容前的填充程度，也就是說一個數組真正能存進去的實際容量 = 數組的長度 * 負載因子（比如當前數組的長度為16（桶的個數），負載因子為0.75，那么當數組存進了16 * 0.75 = 12個桶的時候，就會進行擴容操作，而不是等到數組空間滿了的時候）。如果為0.5表示的就是數組填充一半后就進行擴容；為1就表示的是數組全部填滿后再進行擴容。之所以默認值選擇為0.75是在時間和空間成本上做的一個折中方案，一般不建議自己更改。這個值越高，就意味著數組中能存更多的值，減少空間開銷，但是會增加hash沖突的概率，增加查找的成本；這個值越低，就會減少hash沖突的概率，但是會比較費空間。
??而數組的默認容量為16也是統計上的結果。值得一說的是，如果事先知道了HashMap所要存儲的數量的時候，就可以將數組容量傳進構造器中，以此來避免頻繁地擴容操作。比如我現在要往HashMap中大約放進200個數據，如果不設置初始值的話，默認容量就是16，當存進16 * 0.75 = 12個數據的時候就會擴容一次，擴容到兩倍容量32，然后等再存進32 * 0.75 = 24個數據的時候再繼續擴容…直到擴容到能存進200個數據為止。所以說，如果能提前先設置好初始容量的話，就不需要再擴容這么多次了。
1/**
2 * HashMap:
3 * 無參構造器
4 */
5public HashMap() {
6 //負載因子設置為默認值0.75，其他的屬性值也都是走默認的
7 this.loadFactor = DEFAULT_LOAD_FACTOR;
8}
9
10/**
11 * 有參構造器
12 */
13public HashMap(int initialCapacity) {
14 //初始容量是自己指定的，而負載因子是默認的0.75
15 this(initialCapacity, DEFAULT_LOAD_FACTOR);
16}
17
18public HashMap(int initialCapacity, float loadFactor) {
19 //initialCapacity非負校驗
20 if (initialCapacity < 0)
21 throw new IllegalArgumentException("Illegal initial capacity: " +
22 initialCapacity);
23 //initialCapacity如果超過了設定的最大值（2的30次方），就重置為2的30次方
24 if (initialCapacity > MAXIMUM_CAPACITY)
25 initialCapacity = MAXIMUM_CAPACITY;
26 //負載因子非負校驗和非法數字校驗（當被除數是0或0.0，而除數是0.0的時候，得出來的結果就是NaN）
27 if (loadFactor <= 0 || Float.isNaN(loadFactor))
28 throw new IllegalArgumentException("Illegal load factor: " +
29 loadFactor);
30 this.loadFactor = loadFactor;
31 /*
32 將threshold設置為大于等于當前設置的數組容量的最小2次冪
33 threshold會在resize擴容方法中被重新更新為新數組容量 * 負載因子，也就是下一次的擴容點
34 */
35 this.threshold = tableSizeFor(initialCapacity);
36}
37
38/**
39 * 這個方法是用來計算出大于等于cap的最小2次冪的，但是實現的方式很精巧，充分利用了二進制的特性
40 */
41static final int tableSizeFor(int cap) {
42 /*
43 這里的-1操作是為了防止cap現在就已經是2的冪的情況，后面會進行說明。為了便于理解，這里舉個例子：
44 假設此時cap為34（100010），n就是33（100001）。我們其實只要關注第一個最高位是1的這個位置，即從左
45 到右第一個為1的位置。通用的解釋是01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx（x代表不確定，不用關心這個位置上是0還是1）
46 */
47 int n = cap - 1;
48 /*
49 經過一次右移操作并按位或之后，n變成了110001（100001 | 010000）
50 通用解釋：此時變成了011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
51 */
52 n |= n >>> 1;
53 /*
54 此時經過兩次右移操作并按位或之后，n變成了111101（110001 | 001100）
55 通用解釋：此時變成了01111xxxxxxxxxxxxxxxxxxxxxxxxxxx
56 */
57 n |= n >>> 2;
58 /*
59 此時經過四次右移操作并按位或之后，n變成了111111（111101 | 000011）
60 通用解釋：此時變成了011111111xxxxxxxxxxxxxxxxxxxxxxx
61 */
62 n |= n >>> 4;
63 /*
64 此時經過八次右移操作并按位或，對于上面的示例數據來說，此時已經變成了所有位都是1的情況，
65 那么下面的兩次右移操作做了和沒做已經沒區別了（因為右移后的結果肯定是0，和原來的數按位或之后是沒有變的）
66 其實經過這么多次的右移并按位或，就是為了最后能得出一個全是1的數
67 通用解釋：此時變成了01111111111111111xxxxxxxxxxxxxxx
68 */
69 n |= n >>> 8;
70 /*
71 此時經過十六次右移操作并按位或，通用解釋：此時變成了01111111111111111111111111111111
72 需要說明一下的是int的位數是32位，所以只需要右移16位就可以停止了（當然也可以繼續右移32位，64位...
73 只不過那樣的話就沒有什么意義了，因為右移后的結果都是0，按位或的結果是不會發生變動的）
74 而int的最大值MAX_VALUE是2的31次方-1，換算成二進制就是有31個1
75 在之前的第25行代碼處已經將該值改為了2的30次方，1后面有30個0，即010000...000
76 所以傳進來該方法的最大值cap只能是這個數，經過-1再幾次右移操作后就變成了00111...111，即30個1
77 最后在第90行代碼處+1后又會重新修正為2的30次方，即MAXIMUM_CAPACITY
78 */
79 n |= n >>> 16;
80 /*
81 n如果小于0對應的是傳進來的cap本身就是0的情況。經過右移后，n變成了-1（其實右不右移根本不會改變結果，
82 因為-1的二進制數就是32個1，和任何數按位或都不會發生變動），這個時候就返回結果1（2的0次方）就行了
83
84 由此可以看到，最后的效果就是得出了一個原始數據從第一個最高位為1的這個位置開始，后面的所有位不管是0還是1都改成1
85 最后在第90行代碼處再加一后就變成了最高位是1而剩下位都是0的一個數，但是位數比原數據多一位，也就是原數據的最小2次冪了
86
87 現在可以考慮一下之前說過的如果傳進來的cap本身就是2的冪的情況。假如說沒有第47行代碼操作的話，那么經過不斷右移操作后，
88 得出來的是一個全是1的二進制數，也就是這個數*2-1的結果，最后再加1后就變成了原數據的2倍，這顯然是不對的
89 */
90 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
91} 1/**
2 * HashMap:
3 */
4public V put(K key, V value) {
5 return putVal(hash(key), key, value, false, true);
6}
7
8/**
9 * 計算key的hash值
10 * 注意這里是直接調用key的hashCode方法，并且會將其高16位和低16位進行異或來作為最終的hash（Java中的int值是32位）
11 * 那么為什么會這樣做呢？因為在后續的判斷插入桶bin的位置使用的方法是(table.length - 1) & hash
12 * 這里數組的長度必須為2的冪（如果不是則會轉換成大于該值的最小2次冪，詳見tableSizeFor方法），那么數組的長度減去1后的值
13 * 用二進制來表示就是11111...低位全都是1的一個數。這樣再去和本方法計算出來的hash值進行按位與的話，結果就是一個
14 * 保留了hash值所有這些低位上的數，說白了就是和hash % table.length這種是一樣的結果，就是對數組長度取余而已
15 * 但是直接用%做取余的話效率不高，而且這種按位與的方式只能適用于數組長度是2的冪的情況，不是這種情況的話是不能做等價交換的
16 *
17 * 從上面可以看到，按位與的方式只會用到hash值低位的信息，高位的信息不管是什么都無所謂，反正不會記錄到最后的hash計算中
18 * 這樣的話就覺得有些可惜、有些浪費。如果將高位信息也進行記錄的話那就更好了。所以在下面第26行代碼處，
19 * 將其高16位和低16位進行異或，就是為了將高16位的特征信息也融合進hash值中，盡量使哈希變得散列，減少hash沖突的發生
20 * 同時使用一個異或操作的話也很簡單高效，不會像有些hash函數一樣會進行很多的計算后才會生成一個hash值（比如說這塊
21 * 在Java 7中的實現就是會有很多次的右移操作）
22 * <<<在底層源碼中，在能完成需求的前提下，能實現得越簡單越高效，就是王道>>>
23 */
24static final int hash(Object key) {
25 int h;
26 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
27}
28
29/**
30 * 第5行代碼處：
31 */
32final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
33 boolean evict) {
34 Node<K, V>[] tab;
35 Node<K, V> p;
36 int n, i;
37 if ((tab = table) == null || (n = tab.length) == 0)
38 //如果當前數組還沒有初始化的話，就進行初始化的工作。由此可以看到，HashMap的初始化工作被延遲到了put方法中
39 n = (tab = resize()).length;
40 if ((p = tab[i = (n - 1) & hash]) == null)
41 /*
42 通過(n - 1) & hash的方式來找到這個數據插入的桶位置（至于為什么用這種方式詳見hash方法的注釋）
43 如果這個桶上還沒有數據存在的話，就直接創建一個新的Node節點插入進這個桶就可以了，也就是快速判斷
44 */
45 tab[i] = newNode(hash, key, value, null);
46 else {
47 /*
48 否則如果這個桶上有數據的話，就執行下面的邏輯
49
50 e是用來判斷新插入的這個節點是否能插入進去，如果不為null就意味著找到了這個新節點要插入的位置
51 */
52 Node<K, V> e;
53 K k;
54 if (p.hash == hash &&
55 ((k = p.key) == key || (key != null && key.equals(k))))
56 /*
57 如果桶上第一個節點的hash值和要插入的hash值相同，并且key也是相同的話，
58 就記錄一下這個位置e，后續會做值的覆蓋（快速判斷模式）
59 */
60 e = p;
61 //走到這里說明要插入的節點和當前桶中的第一個節點不是同一個節點，但是他們計算出來的hash值是一樣的
62 else if (p instanceof TreeNode)
63 //如果節點是紅黑樹的話，就執行紅黑樹的插入節點邏輯（紅黑樹的分析本文不做展開）
64 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
65 else {
66 //走到這里說明鏈表上有多個節點，遍歷鏈表上的節點（第一個節點不需要判斷了，因為在第54行代碼處已經判斷過了）
67 for (int binCount = 0; ; ++binCount) {
68 if ((e = p.next) == null) {
69 /*
70 如果當前鏈表的下一個位置為null，意味著已經循環到最后一個節點還沒有找到一樣的，
71 此時將要插入的新節點插到最后
72 */
73 p.next = newNode(hash, key, value, null);
74 //如果循環到此時，鏈表的數量已經達到了轉成紅黑樹的閾值的時候，就進行轉換
75 if (binCount >= TREEIFY_THRESHOLD - 1)
76 /*
77 之前分析過，是否真正會轉成紅黑樹，需要看當前數組的桶的個數
78 是否大于等于MIN_TREEIFY_CAPACITY，小于就只是擴容
79 */
80 treeifyBin(tab, hash);
81 break;
82 }
83 if (e.hash == hash &&
84 ((k = e.key) == key || (key != null && key.equals(k))))
85 //如果這個節點之前就在鏈表中存在，就可以退出循環了（e在第68行代碼處已經被賦值了）
86 break;
87 p = e;
88 }
89 }
90 if (e != null) {
91 /*
92 如果找到了要插入的位置的話，就做值的覆蓋
93
94 記錄舊值，并最終返回出去
95 */
96 V oldValue = e.value;
97 //如果onlyIfAbsent為false，或者本身舊值就為null，就新值覆蓋舊值
98 if (!onlyIfAbsent || oldValue == null)
99 e.value = value;
100 //鉤子方法，空實現
101 afterNodeAccess(e);
102 return oldValue;
103 }
104 }
105 /*
106 走到這里說明之前是走到了第45行代碼處，添加了一個新的節點。
107
108 修改次數+1，modCount是用來做快速失敗的。如果迭代器中做修改，modCount != expectedModCount，
109 表明此時HashMap被其他線程修改了，會拋出ConcurrentModificationException異常（我在分析ArrayList
110 的源碼文章中詳細解釋了這一過程，在HashMap中也是類似的）
111 */
112 ++modCount;
113 /*
114 既然是添加了一個新的節點，那么就需要判斷一下此時是否需要擴容
115 如果當前數組容量已經超過了設定好的threshold閾值的時候，就執行擴容操作
116 */
117 if (++size > threshold)
118 resize();
119 //鉤子方法，空實現
120 afterNodeInsertion(evict);
121 return null;
122}??在上面putVal方法中的第39行和118行代碼處，都是調用了resize方法來進行初始化或擴容的。而resize方法也是HashMap源碼中比較精髓、比較有亮點的一個方法。其具體實現大致可以分為兩部分：設置擴容標志位和具體的數據遷移過程。下面就首先來看一下resize方法的前半部分源碼：
1/**
2 * HashMap:
3 * 擴容操作（當前數組為空的話就變成了對數組初始化的操作）
4 */
5final Node<K, V>[] resize() {
6 Node<K, V>[] oldTab = table;
7 //記錄舊數組（當前數組）的容量，如果為null就是0
8 int oldCap = (oldTab == null) ? 0 : oldTab.length;
9 /*
10 1.在調用有參構造器的時候threshold存放的是大于等于當前數組容量的最小2次冪，將其賦值給oldThr
11 2.調用無參構造器的時候threshold=0
12 3.之前數組已經不為空，現在在做擴容的時候，threshold存放的是舊數組容量 * 負載因子
13 */
14 int oldThr = threshold;
15 //newCap指的是數組擴容后的數量，newThr指的是newCap * 負載因子后的結果（如果計算出來有小數就取整數部分）
16 int newCap, newThr = 0;
17 //下面就是對各種情況進行分析，然后將newCap和newThr標記位進行賦值的過程
18 if (oldCap > 0) {
19 if (oldCap >= MAXIMUM_CAPACITY) {
20 /*
21 如果當前數組容量已經超過了設定的最大值，就將threshold設置為int的最大值，然后返回當前數組容量
22 也就意味著在這種情況下不進行擴容操作
23 */
24 threshold = Integer.MAX_VALUE;
25 return oldTab;
26 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
27 oldCap >= DEFAULT_INITIAL_CAPACITY)
28 /*
29 如果當前數組容量*2后沒有超過設定的最大值，并且當前數組容量是大于等于初始容量16的話，
30 就將newCap設置為oldCap * 2，newThr設置為oldThr * 2
31 oldCap >= DEFAULT_INITIAL_CAPACITY這個條件出現的意義在后面會說明
32 */
33 newThr = oldThr << 1;
34 } else if (oldThr > 0)
35 /*
36 走到這里說明oldCap=0，也就是當前是初始化數組的時候。我們剛才看到如果是默認的無參構造器的話，
37 threshold是不會被賦值的，也就是為0。但是如果調用的是有參的構造器，threshold就會在構造器初始階段被賦值了，
38 而這個if條件就是對應于這種情況。這里設置為oldThr是因為在上面的第14行代碼處可以看到oldThr指向的是threshold，
39 也就是說oldThr的值是大于等于“當前數組容量”的最小2次冪（注意，“當前數組容量”我在這里是加上引號的，
40 也就是說并不是現在真正物理存在的數組容量（當前的物理容量是0），而是通過構造器傳進來設定的容量），
41 肯定是個大于0的數。既然這個oldThr現在就代表著我想要設定的新容量，那么直接就將newCap也賦值成這個數就可以了
42 */
43 newCap = oldThr;
44 else {
45 /*
46 如上所說，這里對應的是調用無參構造器，threshold=0的時候
47 將newCap賦值為16，newThr賦值為16 * 0.75 = 12，都是取默認的值
48 */
49 newCap = DEFAULT_INITIAL_CAPACITY;
50 newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
51 }
52 if (newThr == 0) {
53 /*
54 有兩種情況程序能走到這里：
55 第一種：在第43行代碼處的if條件中沒有對newThr進行賦值，此時計算出ft = 新數組容量 * 負載因子，
56 如果數組容量和ft都沒有超過設定的最大值的話，就將newThr賦值為ft，否則賦值給int的最大值
57
58 第二種：注意到上面第27行代碼處的條件，如果oldCap比16要小的話，newThr也是沒有賦值的。
59 出現這種情況的根源不在于這一次resize方法的調用，而是在于上一次初始化時候的調用。舉個例子就明白了：
60 一開始我是調用new HashMap<>(2)這個構造器，經過計算后threshold=2。接著調用put方法觸發初始化會跳進該方法里
61 此時oldCap=0，oldThr=2。接著會走進第34行代碼處的if條件中，newCap=2，然后會走進第52行代碼處，
62 也就是本if條件中：newThr=1，然后修改threshold=1。之后resize方法就會走具體的擴容操作了
63 但是之前這些設置的標志位都不會被更改，擴容后就退出該方法了。這是第一次調用過程。
64 然后我此時成功插入了這個節點后，又再次調用了put方法。此時還是會把該節點插入成功進去，
65 但是在上面putVal方法中的第117行代碼處判斷發現，我當前的size=2已經大于了threshold=1。于是又會調用resize該方法來進行擴容
66 而此時oldCap=2，oldThr=1。會走到第26行代碼處的if條件中，newCap=4，而此時的oldCap=2要小于16，
67 于是就跳出了該if條件，然后會走進第52行代碼處，也就是本if條件中：newThr=3，然后修改threshold=3
68 這是正確的情況，因為newThr本身就是newCap * 負載因子后的結果，即 4 * 0.75 = 3
69 那么假如說源碼里沒有第27行代碼處的判斷條件的話，就會跳進到第33行代碼處，此時的oldThr=1，所以newThr=2
70 可以看到此時newCap=4而newThr=2，發生了錯誤，4 * 0.75不等于2。所以說在第27行代碼處的
71 oldCap >= DEFAULT_INITIAL_CAPACITY這個條件的出現，將原本在第33行代碼處進行更新newThr的操作
72 改為了在第97行代碼處，以解決newThr更新不準確的問題
73
74 當然這里只是演示了可能出錯的一種情況，并沒有說到本質。其實我通過對比其他的一些數據來演示這個結果后發現：
75 如果桶的個數超過了16也會存在這種差異點。其實上述的出錯可以一般化：一個是原容量 * 負載因子后取整，然后*2，
76 另一個是原容量 * 2 * 負載因子后再取整。差異點就在于取整的時機。而出現差別也就是
77 原容量 * 負載因子后是一個帶小數的數（如果為整數是不會有差別的，而且也并不是所有帶小數的數都會有差異），
78 這個帶小數的數取整后再*2，差異點被放大了，從而導致最終的不同。還有一處線索是第27行代碼處的
79 oldCap >= DEFAULT_INITIAL_CAPACITY，注意這里是大于等于，而不是小于等于，也就是說
80 只有大于等于16的話才會走進這個if條件（快速計算threshold結果），小于16的話會走進本if條件
81 （精確計算threshold結果）。所以說如果桶的個數大于16，閾值多一個少一個的話可能就沒那么重要了，
82 比如說1024個桶，我是在819個桶滿了的時候去擴容還是在818個，似乎差別也不太大，在這種情況下
83 就因為我把閾值threshold多減去了1個，從而會導致哈希沖突變高？還是空間更浪費了？其實不見得
84 畢竟數據量在這里擺著，而且負載因子一般都是小于1的數，所以這個差別最多也就是1個。這個差異點也會隨著
85 數據的越來越大而顯得越來越不重要。但是如果像前面舉的例子，4個桶我是在2個桶滿了還是3個桶滿的時候去擴容，
86 這個差別就很大了，這兩種情況下hash沖突發生概率的對比肯定是比較大的。可能一個是20%，另一個是40%，
87 而桶的個數比較大的時候這個差異對比可能就是1.2%和1.3%（這個數是我隨便舉的）。這樣的話在數據量大
88 而且擴容方法頻繁調用的時候（比如我要存進一個特別大的容量但是沒有指定初始容量），我犧牲了計算閾值的準確性
89 （如果負載因子設置合理，這個差異就只有1個的區別），但換來了執行速度的高效（注意在第33行代碼處是左移操作，
90 而在第96行代碼處是乘法，乘法后又接著一個三目運算符，然后又取整）；但是數據量小的時候，明顯是計算準確更重要，
91 而且數據量小的情況下也談不上什么性能差異，畢竟這里設定的閾值是16。所以在上面第14行代碼處的注釋中，
92 threshold有第四種取值：舊數組容量 * 負載因子 - 1（具體減去幾要看負載因子設置的值以及數組容量），
93 但是這種完全可以算作是第三種的特殊情況。所以總結來說：第27行代碼處添加的意義就是為了在桶數量比較大、
94 擴容方法頻繁調用的時候，稍微犧牲一些準確性，但是能讓threshold閾值計算得更快一些，是一種優化手段
95 */
96 float ft = (float) newCap * loadFactor;
97 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
98 (int) ft : Integer.MAX_VALUE);
99 }
100 //做完上述操作后，將threshold的值也更新一下
101 threshold = newThr;
102
103 //...
104}??上面在把newCap、newThr和threshold標記位都設置好了后，下面就是具體的數據遷移的過程，也就是resize方法后半部分的實現：
1/**
2 * HashMap:
3 */
4final Node<K, V>[] resize() {
5 //...
6
7 //此時newCap和newThr標記位都已經設置好了，將根據newCap新的容量來創建一個新的Node數組，以此來替代舊數組
8 @SuppressWarnings({"rawtypes", "unchecked"})
9 Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
10 table = newTab;
11 //如果舊數組為null，也就是說現在是對數組做初始化的操作。那么直接就返回創建的新數組newTab就行了
12 if (oldTab != null) {
13 //遍歷舊數組上的每一個桶
14 for (int j = 0; j < oldCap; ++j) {
15 Node<K, V> e;
16 //如果舊數組的這個桶上沒有數據的話，就跳過它，不進行擴容
17 if ((e = oldTab[j]) != null) {
18 //舊數組上的這個節點賦值為null，便于快速GC
19 oldTab[j] = null;
20 if (e.next == null)
21 /*
22 第一個節點后面沒有后續節點，也就意味著這個桶上只有一個節點，
23 那么只需要通過計算找出新位置放進去就行了，這里也就是在做快速遷移
24 */
25 newTab[e.hash & (newCap - 1)] = e;
26 else if (e instanceof TreeNode)
27 //如果是紅黑樹，就執行紅黑樹的遷移邏輯（紅黑樹的分析本文不做展開）
28 ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
29 else {
30 /*
31 走到這里說明當前這個桶里面有不止一個的節點，此時就會做鏈表上多個節點的遷移工作
32 首先來說一下大前提：現在舊數組上桶的位置是j，而準備放進新數組的桶位置有兩個：一個是j，
33 也就是說新數組上也會放在j這個位置上；另一個是j+舊數組的容量。比方說當前桶的位置15，
34 而舊數組的容量是16，那么新數組上第二個將要插入的桶的位置就是15 + 16 = 31
35
36 說完了大前提，再來看下面的代碼。以下定義了四個指針位置，
37 分別就對應了上面說的兩個新插入桶位置的頭尾指針
38 */
39 Node<K, V> loHead = null, loTail = null;
40 Node<K, V> hiHead = null, hiTail = null;
41 Node<K, V> next;
42 do {
43 //next指向當前節點的下一個節點
44 next = e.next;
45 /*
46 那么現在的問題就是通過什么辦法來判斷到底是插入到j位置還是j+舊數組容量的位置呢？
47 其實也很簡單，就是通過節點的哈希值和舊數組的容量按位與的方式來判斷的。舊數組容量
48 經過上面的分析后可以知道，肯定是一個2的冪，也就是1000...000，最高位為1，而剩余位都是0的形式
49 這樣按位與的結果就是取出了節點hash上的那個與舊數組所對應的1的那個位置上的數。
50 比如說節點的hash值是1010110，舊數組容量是16（1000），那么按位與的結果就是
51 取出了hash值中從右往左第四位的值，即0。也就是說，存在新數組哪個位置上，取決于hash值
52 所對應舊數組容量為1的那個位置上到底是0還是1。從這里也可以看出，除了
53 (table.length - 1) & hash這種方式用來判斷插入桶的位置，是必須要求數組容量是2的冪之外，
54 在擴容做遷移的時候，也必須要求了這點
55
56 按位與的結果只有兩種，不是0就是1，所以如果為0的話最后就會插入到新數組的j位置，
57 為1就插入到j+舊數組容量的位置（后面會解釋如果換一下的話，到底行不行）
58 */
59 if ((e.hash & oldCap) == 0) {
60 if (loTail == null)
61 //如果當前是第一個插進來的節點，就將loHead頭指針指向它
62 loHead = e;
63 else
64 /*
65 不是第一個的話，就將loTail尾指針的下一個next指針指向它，也就是把鏈拉上
66 loTail在之前已經指向了最后一個節點處
67 */
68 loTail.next = e;
69 //更新一下loTail尾指針，重新指向此時的最后一個節點處
70 loTail = e;
71 } else {
72 //(e.hash & oldCap) == 1
73 if (hiTail == null)
74 //如果當前是第一個插進來的節點，就將hiHead頭指針指向它
75 hiHead = e;
76 else
77 /*
78 不是第一個的話，就將hiTail尾指針的下一個next指針指向它，也就是把鏈拉上
79 hiTail在之前已經指向了最后一個節點處
80 */
81 hiTail.next = e;
82 //更新一下hiTail尾指針，重新指向此時的最后一個節點處
83 hiTail = e;
84 }
85 //如果當前遍歷鏈表上的節點還沒有到達最后一個節點處，就繼續循環去判斷
86 } while ((e = next) != null);
87 /*
88 走到這里說明已經將原來的舊數組上的鏈表拆分完畢了，現在分成了兩個鏈表，low和high
89 接下來需要做的工作就很清楚了：將這兩個鏈表分別插入到j位置和j+舊數組容量的位置就可以了
90 */
91 if (loTail != null) {
92 /*
93 如果low鏈表有節點的話（沒節點說明之前的按位與的計算結果都是1），就重新更新一下low鏈表上
94 最后一個節點的next指針指向null。這步操作很重要，因為如果之前這個節點不是
95 舊數組桶上的最后一個節點的話，next是有值的。不改成null的話指針指向就亂了
96 */
97 loTail.next = null;
98 //將鏈表插入到j位置
99 newTab[j] = loHead;
100 }
101 if (hiTail != null) {
102 /*
103 如果high鏈表有節點的話（沒節點說明之前的按位與的計算結果都是0），就重新更新一下high鏈表上
104 最后一個節點的next指針指向null。這步操作很重要，因為如果之前這個節點不是
105 舊數組桶上的最后一個節點的話，next是有值的。不改成null的話指針指向就亂了
106 */
107 hiTail.next = null;
108 //將鏈表插入到j+舊數組容量的位置
109 newTab[j + oldCap] = hiHead;
110 }
111 }
112 }
113 }
114 }
115 return newTab;
116}??在Java 7的HashMap源碼中，transfer方法是用來做擴容時的遷移數據操作的。其實現就是通過遍歷鏈表中的每一個節點，重新rehash實現的。在這其中會涉及到指針的修改，在高并發的場景下，可能會使鏈表上的一個節點的下一個指針指向了其前一個節點，也就是形成了死循環，死鏈（具體形成過程不再展開）：
??這樣再去遍歷鏈表的時候就永遠不會停下來，出現了bug。而Java 8中通過形成兩個鏈表，節點hash值在數組容量二進制數為1的那個位置處去按位與判斷是0還是1，以此來選擇插入的方式很好地解決了這個問題，而且不用每一個節點rehash，提高了執行速度。
??既然說到了不用rehash，那么這里想要探究一下在數組擴容時，選擇新插入數組的位置是原位置和原位置+舊數組容量，為什么這里加上的是舊數組容量呢？加別的值不可以嗎？其實這里加舊數組容量是有原因的。我們都知道，數組容量必須是2的冪，即100…000，而新數組的容量是原數組的2倍，也就是把原來值中的“1”往左移了一位，而我們在判斷插入桶位置時用的方式是（數組容量 - 1）& hash值。把這些信息都整合一下，我們就知道在新數組中計算桶位置和在舊數組中計算桶位置的差異，其實就在于舊數組二進制為1上的這位上。如果該位是0，那就是和原來舊數組是同一個位置，如果是1，就是舊數組位置處+舊數組的容量。下面舉個例子：
??兩個節點此時計算出來桶的位置都是1010，即第10個桶。它們都會被放在第10個桶中的鏈表中。
??而現在數組擴容了，數組容量變為了32，我們再來看看結果會怎樣：
??這時候發現(n - 1) & hash的結果不一樣了，節點1是01010，節點2是11010。也就是說，我們在get方法執行的時候（get方法也是通過(n - 1) & hash的方式來找到桶的位置），找到節點1是在第10個桶，節點2是在第26個桶，這兩個節點之間相差16個桶，這不就是舊數組的容量嗎？現在是不是恍然大悟了，我們當初在擴容時，將節點的hash值和舊數組容量進行按位與，其實也就是在找上圖紅框框中的那個位置。如果為0，就將節點1放在新數組中第10個桶中（1010），也就是原位置處；如果為1，就將節點2放在新數組中第26個桶中（1010+10000），也就是原位置+舊數組容量處。這樣做的話，我在get方法執行的時候也能保證正確執行，能正確找到節點在新數組中桶的位置。同時也說明了，這個放入的策略是不能換的。也就是說，不能是如果為1的話最后就會插入到新數組的原位置，為0就插入到原位置+舊數組容量的位置。如果這么做的話，最后get方法在查找該節點的時候，就找不到了（而實際上還存在）。所以通過Java 8中的這種擴容方式，既能計算出正確的新桶位置，又能避免每一個節點的rehash，節省計算時間，實在是妙哉。
1/**
2 * HashMap:
3 */
4public V get(Object key) {
5 Node<K, V> e;
6 //如果獲取不到值，或者本身插入的value就是null的話，就返回null，否則返回具體的value
7 return (e = getNode(hash(key), key)) == null ? null : e.value;
8}
9
10final Node<K, V> getNode(int hash, Object key) {
11 Node<K, V>[] tab;
12 Node<K, V> first, e;
13 int n;
14 K k;
15 //如果數組沒有初始化，或者計算出來的桶的位置為null（說明找不到這個key），就直接返回null
16 if ((tab = table) != null && (n = tab.length) > 0 &&
17 (first = tab[(n - 1) & hash]) != null) {
18 if (first.hash == hash &&
19 ((k = first.key) == key || (key != null && key.equals(k))))
20 /*
21 如果桶上第一個節點的hash值和要查找的hash值相同，并且key也是相同的話，
22 就直接返回（快速判斷模式）
23 */
24 return first;
25 /*
26 如果下一個節點為null，也就是當前桶上只有一個節點的時候，
27 并且之前那個節點不是的話，那就直接返回null，也就是找不到
28 */
29 if ((e = first.next) != null) {
30 if (first instanceof TreeNode)
31 //如果節點是紅黑樹的話，就執行紅黑樹的查找節點邏輯（紅黑樹的分析本文不做展開）
32 return ((TreeNode<K, V>) first).getTreeNode(hash, key);
33 /*
34 走到這里說明鏈表上有多個節點，遍歷鏈表上的每一個節點進行查找（第一個節點不需要判斷了，
35 因為在第18行代碼處已經判斷過了）
36 */
37 do {
38 if (e.hash == hash &&
39 ((k = e.key) == key || (key != null && key.equals(k))))
40 return e;
41 } while ((e = e.next) != null);
42 }
43 }
44 return null;
45} 1/**
2 * HashMap:
3 */
4public V remove(Object key) {
5 Node<K, V> e;
6 //如果找不到要刪除的節點，就返回null，否則返回刪除的節點
7 return (e = removeNode(hash(key), key, null, false, true)) == null ?
8 null : e.value;
9}
10
11final Node<K, V> removeNode(int hash, Object key, Object value,
12 boolean matchValue, boolean movable) {
13 Node<K, V>[] tab;
14 Node<K, V> p;
15 int n, index;
16 //如果數組沒有初始化，或者計算出來的桶的位置為null（說明找不到這個key），就直接返回null
17 if ((tab = table) != null && (n = tab.length) > 0 &&
18 (p = tab[index = (n - 1) & hash]) != null) {
19 Node<K, V> node = null, e;
20 K k;
21 V v;
22 if (p.hash == hash &&
23 ((k = p.key) == key || (key != null && key.equals(k))))
24 //如果桶上第一個節點的hash值和要查找的hash值相同，并且key也是相同的話，就記錄一下該位置
25 node = p;
26 else if ((e = p.next) != null) {
27 //e是桶上第一個節點的下一個節點，如果沒有的話，也說明找不到要刪除的節點，就返回null
28 if (p instanceof TreeNode)
29 //如果節點是紅黑樹的話，就執行紅黑樹的查找節點邏輯（紅黑樹的分析本文不做展開）
30 node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
31 else {
32 /*
33 走到這里說明鏈表上有多個節點，遍歷鏈表上的每一個節點進行查找，找到了就記錄一下該位置
34 （第一個節點不需要判斷了，因為在第22行代碼處已經判斷過了）
35 */
36 do {
37 if (e.hash == hash &&
38 ((k = e.key) == key ||
39 (key != null && key.equals(k)))) {
40 node = e;
41 break;
42 }
43 //此時p記錄的是當前節點的上一個節點
44 p = e;
45 } while ((e = e.next) != null);
46 }
47 }
48 /*
49 如果找到了要刪除的節點，并且如果matchValue為true（matchValue為true代表僅在value相等的情況下才能刪除）
50 并且value相等的時候（如果matchValue為false，就只需要判斷第一個條件node是否不為null）
51 當然，如果不相等的話，就直接返回null，也就是不會刪除
52 */
53 if (node != null && (!matchValue || (v = node.value) == value ||
54 (value != null && value.equals(v)))) {
55 if (node instanceof TreeNode)
56 //如果節點是紅黑樹的話，就執行紅黑樹的刪除節點邏輯（紅黑樹的分析本文不做展開）
57 ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
58 else if (node == p)
59 /*
60 如果要刪除的節點是桶上的第一個節點，就直接將當前桶的第一個位置處賦值為下一個節點
61 （如果next為null就是賦值為null）
62 */
63 tab[index] = node.next;
64 else
65 //不是桶上第一個節點就將前一個節點的next指向下一個節點，也就是將node節點從鏈表中剔除掉，等待GC
66 p.next = node.next;
67 //修改次數+1（快速失敗機制）
68 ++modCount;
69 //因為是要刪除節點，所以如果找到了的話，size就-1
70 --size;
71 //鉤子方法，空實現
72 afterNodeRemoval(node);
73 return node;
74 }
75 }
76 return null;
77} 1/**
2 * HashMap:
3 */
4public void clear() {
5 Node<K, V>[] tab;
6 //修改次數+1（快速失敗機制）
7 modCount++;
8 if ((tab = table) != null && size > 0) {
9 //size記錄的是當前有數據的桶的個數，因為這里要清空數據，所以將size重置為0
10 size = 0;
11 //同時將table中的每個桶都置為null就行了
12 for (int i = 0; i < tab.length; ++i)
13 tab[i] = null;
14 }
15}在這行干的越久真是越覺得：萬丈高樓平地起，這絕B是句真理！在應用業務里待太久很多底層的東西往往容易忽略掉，今年的年初計劃是把常用的JDK源碼工具做一次總結，眼看年底將近，乘著最近有空，趕緊的給補上。
ArrayList你真懂？說說foreach與iterator時remove的區別
你是否想過互聯網公司一面為什么總愛問集合？聊聊經典數據結構HashMap
AQS源碼深入分析之獨占模式-ReentrantLock鎖特性詳解
AQS源碼深入分析之共享模式-為什么AQS中要有PROPAGATE這個狀態？
AQS源碼深入分析之條件隊列-Java中的阻塞隊列是如何實現的？
AQS源碼深入分析之應用工具CountDownLatch（規劃中）
AQS源碼深入分析之應用工具CyclicBarrier（規劃中）
ConcurrentHashMap源碼分析-ConcurrentHashMap在Java 8中的實現還有bug？而且還不止一處！這個坑還比較大，后面會重點總結一下！
ThreadPoolExecutor源碼分析-問爛了的Java線程池執行流程，其實如果問的細，很多人還是一臉懵逼？
ScheduledThreadPoolExecutor源碼分析-重點屢屢定時線程池是如何實現延遲執行和周期執行！
ThreadLocal源碼分析-重點總結，內存泄漏，軟引用弱引用虛引用，面試經常喜歡問，我也喜歡問別個
紅黑樹TreeMap、LinkedHashMap（不確定要不要寫，有時間寫，看項目情況）
有序并且線程的Map容器ConcurrentSkipListMap（跳表）深入理解
LinkedList（不確定要不要寫，有時間寫，看項目情況）
年底如果項目不趕，有空就在寫一篇常用的排序算法的文章
每一次總結都是對知識點掌握程度的審視，技術不易，每日精進一點，與大家共勉。
關于經典數據結構HashMap以及逐行分析每一個關鍵點就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
