經(jīng)典數(shù)據(jù)結(jié)構(gòu)HashMap以及逐行分析每一個(gè)關(guān)鍵點(diǎn)

這篇文章給大家介紹經(jīng)典數(shù)據(jù)結(jié)構(gòu)HashMap以及逐行分析每一個(gè)關(guān)鍵點(diǎn)，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

聊聊經(jīng)典數(shù)據(jù)結(jié)構(gòu)HashMap,逐行分析每一個(gè)關(guān)鍵點(diǎn)

基于JDK-8u261源碼分析

1 簡(jiǎn)介

??HashMap是一個(gè)使用非常頻繁的鍵值對(duì)形式的工具類(lèi)，其使用起來(lái)十分方便。但是需要注意的是，HashMap不是線(xiàn)程安全的，線(xiàn)程安全的是ConcurrentHashMap（Hashtable這種過(guò)時(shí)的工具類(lèi)就不要再提了），在Spring框架中也會(huì)用到HashMap和ConcurrentHashMap來(lái)做各種緩存。從Java 8開(kāi)始，HashMap的源碼做了一定的修改，以此來(lái)提升其性能。首先來(lái)看一下HashMap的數(shù)據(jù)結(jié)構(gòu)：

??整體上可以看作是數(shù)組+鏈表的形式。數(shù)組是為了進(jìn)行快速檢索，而如果hash函數(shù)沖突了的話(huà)，就會(huì)在同一個(gè)位置處后面進(jìn)行掛鏈表的操作。也就是說(shuō)，同一個(gè)鏈表上的節(jié)點(diǎn)，它們的hash值計(jì)算出來(lái)都是一樣的。但是如果hash沖突比較多的時(shí)候，生成的鏈表也會(huì)拉的比較長(zhǎng)，這個(gè)時(shí)候檢索起來(lái)就會(huì)退化成遍歷操作，性能就比較低了。在Java 8中為了改善這種情況，引入了紅黑樹(shù)。

??紅黑樹(shù)是一種高級(jí)的平衡二叉樹(shù)結(jié)構(gòu)，其能保證查找、插入、刪除的時(shí)間復(fù)雜度最壞為O(logn)。在大數(shù)據(jù)量的場(chǎng)景下，相比于AVL樹(shù)，紅黑樹(shù)的插入刪除性能要更高。當(dāng)鏈表中的節(jié)點(diǎn)數(shù)量大于等于8的時(shí)候，同時(shí)當(dāng)前數(shù)組中的長(zhǎng)度大于等于MIN_TREEIFY_CAPACITY時(shí)（注意這里是考點(diǎn)！所以以后不要再說(shuō)什么當(dāng)鏈表長(zhǎng)度大于8的時(shí)候就會(huì)轉(zhuǎn)成紅黑樹(shù)，這么說(shuō)只會(huì)讓別人覺(jué)得你沒(méi)有認(rèn)真看源碼），鏈表中的所有節(jié)點(diǎn)會(huì)被轉(zhuǎn)化成紅黑樹(shù)，而如果當(dāng)前鏈表節(jié)點(diǎn)的數(shù)量小于等于6的時(shí)候，紅黑樹(shù)又會(huì)被退化成鏈表。其中MIN_TREEIFY_CAPACITY的值為64，也就是說(shuō)當(dāng)前數(shù)組中的長(zhǎng)度（也就是桶bin的個(gè)數(shù)）必須大于等于64的時(shí)候，同時(shí)當(dāng)前這個(gè)鏈表的長(zhǎng)度大于等于8的時(shí)候，才能轉(zhuǎn)化。如果當(dāng)前數(shù)組中的長(zhǎng)度小于64，即使當(dāng)前鏈表的長(zhǎng)度已經(jīng)大于8了，也不會(huì)轉(zhuǎn)化。這點(diǎn)需要特別注意。以下的treeifyBin方法是用來(lái)將鏈表轉(zhuǎn)化成紅黑樹(shù)操作的：

 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行代碼處可以看出，如果當(dāng)前數(shù)組的長(zhǎng)度也就是桶的數(shù)量小于MIN_TREEIFY_CAPACITY的時(shí)候，會(huì)選擇resize擴(kuò)容操作，此時(shí)就不會(huì)走轉(zhuǎn)成紅黑樹(shù)的邏輯了。這里的意思就是說(shuō)如果當(dāng)前的hash沖突達(dá)到8的時(shí)候，根本的原因就是因?yàn)橥胺峙涞奶俨女a(chǎn)生那么多沖突的。那么此時(shí)我選擇擴(kuò)容操作，以此來(lái)降低hash沖突的產(chǎn)生。等到數(shù)組的長(zhǎng)度大于等于MIN_TREEIFY_CAPACITY的時(shí)候，如果當(dāng)前鏈表的長(zhǎng)度還是8的話(huà)，才會(huì)去轉(zhuǎn)化成紅黑樹(shù)。

??由此可以看出加入MIN_TREEIFY_CAPACITY這個(gè)參數(shù)的意義就是在于要保證hash沖突多的原因不是因?yàn)閿?shù)組容量少才導(dǎo)致的；還有一個(gè)意義在于，假如說(shuō)當(dāng)前數(shù)組的所有數(shù)據(jù)都放在了一個(gè)桶里面（或者類(lèi)似于這種情況，絕大部分的節(jié)點(diǎn)都掛在了一個(gè)桶里（hash函數(shù)散列效果不好，一般不太可能出現(xiàn)）），此時(shí)如果沒(méi)有MIN_TREEIFY_CAPACITY這個(gè)參數(shù)進(jìn)行限制的話(huà)，那我就會(huì)去開(kāi)開(kāi)心心去生成紅黑樹(shù)去了（紅黑樹(shù)的生成過(guò)程以及后續(xù)的維護(hù)還是比較復(fù)雜的，所以原則上是能不生成就不生成，后面會(huì)有說(shuō)明）。而有了MIN_TREEIFY_CAPACITY這個(gè)參數(shù)進(jìn)行限制的話(huà)，在上面的第8行代碼處就會(huì)觸發(fā)擴(kuò)容操作。這里的擴(kuò)容更多的意義在于把這個(gè)hash沖突盡量削減。比如把鏈表長(zhǎng)度為8的八個(gè)節(jié)點(diǎn)再平分到擴(kuò)容后新的兩倍數(shù)組的兩處新的桶里面，每個(gè)桶由原來(lái)的八個(gè)節(jié)點(diǎn)到現(xiàn)在的四個(gè)節(jié)點(diǎn)（也可能是一個(gè)桶5個(gè)另一個(gè)桶3個(gè)，極端情況下也可能一個(gè)桶8個(gè)另一個(gè)桶0個(gè)。但不管怎樣，從統(tǒng)計(jì)學(xué)上考量的話(huà)，原來(lái)桶中的節(jié)點(diǎn)數(shù)大概率會(huì)被削減），這樣就相當(dāng)于減少了鏈表的個(gè)數(shù)，也就是說(shuō)減少了在同一個(gè)位置上的hash沖突的發(fā)生。還有一點(diǎn)需要提一下，源碼注釋中說(shuō)明MIN_TREEIFY_CAPACITY的大小要至少為4倍的轉(zhuǎn)成紅黑樹(shù)閾值的數(shù)量，這么做的原因也是更多的希望能減少hash沖突的發(fā)生。

??**那么為什么不直接用紅黑樹(shù)來(lái)代替鏈表，而是采用鏈表和紅黑樹(shù)來(lái)搭配在一起使用呢？**原因就在于紅黑樹(shù)雖然性能更好，但是這也僅是在大數(shù)據(jù)量下才能看到差異。如果當(dāng)前數(shù)據(jù)量很小，就幾個(gè)節(jié)點(diǎn)的話(huà)，那么此時(shí)顯然用鏈表的方式會(huì)更劃算。因?yàn)橐兰t黑樹(shù)的插入和刪除操作會(huì)涉及到大量的自旋，以此來(lái)保證樹(shù)結(jié)構(gòu)的平衡。如果數(shù)據(jù)量小的話(huà)，插入刪除的性能高效根本抵消不了自旋操作所帶來(lái)的成本。

??**還有一點(diǎn)需要留意的是鏈表轉(zhuǎn)為紅黑樹(shù)的閾值是8，而紅黑樹(shù)退化成鏈表的閾值是6。**為什么這兩個(gè)值會(huì)不一樣呢？可以試想一下，如果這兩個(gè)值都為8的話(huà)，而當(dāng)前鏈表的節(jié)點(diǎn)數(shù)量為7，此時(shí)一個(gè)新的節(jié)點(diǎn)進(jìn)來(lái)了，計(jì)算出hash值和這七個(gè)節(jié)點(diǎn)的hash值相同，即發(fā)生了hash沖突。于是就會(huì)把這個(gè)節(jié)點(diǎn)掛在第七個(gè)節(jié)點(diǎn)的后面，但是此時(shí)已經(jīng)達(dá)到了變成紅黑樹(shù)的閾值了（MIN_TREEIFY_CAPACITY條件假定也滿(mǎn)足），于是就轉(zhuǎn)成紅黑樹(shù)。但是此時(shí)調(diào)用了一次remove操作需要?jiǎng)h掉這個(gè)新加的節(jié)點(diǎn)，刪掉之后當(dāng)前紅黑樹(shù)的節(jié)點(diǎn)數(shù)量就又變成了7，于是就退化成了鏈表。然后此時(shí)又新加了一個(gè)節(jié)點(diǎn)，正好又要掛在第七個(gè)節(jié)點(diǎn)的后面，于是就又變成紅黑樹(shù)，然后又要remove，又退化成鏈表…可以看到在這種場(chǎng)景下，會(huì)不斷地出現(xiàn)鏈表和紅黑樹(shù)之間的相互轉(zhuǎn)換，這個(gè)性能是很低的，因?yàn)榇蟛糠值膱?zhí)行時(shí)間都花費(fèi)在了轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)上面，而我僅僅是做了幾次連續(xù)的增刪操作而已。所以為了避免這種情況的發(fā)生，將兩個(gè)閾值錯(cuò)開(kāi)一些，以此來(lái)盡量避免在閾值點(diǎn)附近可能存在的、頻繁地做轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)操作而導(dǎo)致性能變低的情況出現(xiàn)。

??這里之所以閾值會(huì)選擇為8是通過(guò)數(shù)學(xué)統(tǒng)計(jì)上的結(jié)論得出的，在源碼中也有相關(guān)注釋?zhuān)?/p>

其中中間的數(shù)字表示當(dāng)前這個(gè)位置預(yù)計(jì)發(fā)生指定次數(shù)哈希沖突的概率是多少?？梢钥吹疆?dāng)沖突概率為8的時(shí)候，概率已經(jīng)降低到了0.000006%，幾乎是不可能發(fā)生的概率。從這里也可以看出，HashMap作者選擇這個(gè)數(shù)作為閾值是不希望生成紅黑樹(shù)的（紅黑樹(shù)的維護(hù)成本高昂）。而同樣負(fù)載因子默認(rèn)選擇為0.75也是基于統(tǒng)計(jì)分析出來(lái)的，以下是源碼中對(duì)負(fù)載因子的解釋?zhuān)?/p>

??負(fù)載因子衡量的是數(shù)組在擴(kuò)容前的填充程度，也就是說(shuō)一個(gè)數(shù)組真正能存進(jìn)去的實(shí)際容量 = 數(shù)組的長(zhǎng)度 * 負(fù)載因子（比如當(dāng)前數(shù)組的長(zhǎng)度為16（桶的個(gè)數(shù)），負(fù)載因子為0.75，那么當(dāng)數(shù)組存進(jìn)了16 * 0.75 = 12個(gè)桶的時(shí)候，就會(huì)進(jìn)行擴(kuò)容操作，而不是等到數(shù)組空間滿(mǎn)了的時(shí)候）。如果為0.5表示的就是數(shù)組填充一半后就進(jìn)行擴(kuò)容；為1就表示的是數(shù)組全部填滿(mǎn)后再進(jìn)行擴(kuò)容。之所以默認(rèn)值選擇為0.75是在時(shí)間和空間成本上做的一個(gè)折中方案，一般不建議自己更改。這個(gè)值越高，就意味著數(shù)組中能存更多的值，減少空間開(kāi)銷(xiāo)，但是會(huì)增加hash沖突的概率，增加查找的成本；這個(gè)值越低，就會(huì)減少hash沖突的概率，但是會(huì)比較費(fèi)空間。

??而數(shù)組的默認(rèn)容量為16也是統(tǒng)計(jì)上的結(jié)果。值得一說(shuō)的是，如果事先知道了HashMap所要存儲(chǔ)的數(shù)量的時(shí)候，就可以將數(shù)組容量傳進(jìn)構(gòu)造器中，以此來(lái)避免頻繁地?cái)U(kuò)容操作。比如我現(xiàn)在要往HashMap中大約放進(jìn)200個(gè)數(shù)據(jù)，如果不設(shè)置初始值的話(huà)，默認(rèn)容量就是16，當(dāng)存進(jìn)16 * 0.75 = 12個(gè)數(shù)據(jù)的時(shí)候就會(huì)擴(kuò)容一次，擴(kuò)容到兩倍容量32，然后等再存進(jìn)32 * 0.75 = 24個(gè)數(shù)據(jù)的時(shí)候再繼續(xù)擴(kuò)容…直到擴(kuò)容到能存進(jìn)200個(gè)數(shù)據(jù)為止。所以說(shuō)，如果能提前先設(shè)置好初始容量的話(huà)，就不需要再擴(kuò)容這么多次了。

2 構(gòu)造器

 1/**
 2 * HashMap:
 3 * 無(wú)參構(gòu)造器
 4 */
 5public HashMap() {
 6    //負(fù)載因子設(shè)置為默認(rèn)值0.75，其他的屬性值也都是走默認(rèn)的
 7    this.loadFactor = DEFAULT_LOAD_FACTOR;
 8}
 9
10/**
11 * 有參構(gòu)造器
12 */
13public HashMap(int initialCapacity) {
14    //初始容量是自己指定的，而負(fù)載因子是默認(rèn)的0.75
15    this(initialCapacity, DEFAULT_LOAD_FACTOR);
16}
17
18public HashMap(int initialCapacity, float loadFactor) {
19    //initialCapacity非負(fù)校驗(yàn)
20    if (initialCapacity < 0)
21        throw new IllegalArgumentException("Illegal initial capacity: " +
22                initialCapacity);
23    //initialCapacity如果超過(guò)了設(shè)定的最大值（2的30次方），就重置為2的30次方
24    if (initialCapacity > MAXIMUM_CAPACITY)
25        initialCapacity = MAXIMUM_CAPACITY;
26    //負(fù)載因子非負(fù)校驗(yàn)和非法數(shù)字校驗(yàn)（當(dāng)被除數(shù)是0或0.0，而除數(shù)是0.0的時(shí)候，得出來(lái)的結(jié)果就是NaN）
27    if (loadFactor <= 0 || Float.isNaN(loadFactor))
28        throw new IllegalArgumentException("Illegal load factor: " +
29                loadFactor);
30    this.loadFactor = loadFactor;
31    /*
32    將threshold設(shè)置為大于等于當(dāng)前設(shè)置的數(shù)組容量的最小2次冪
33    threshold會(huì)在resize擴(kuò)容方法中被重新更新為新數(shù)組容量 * 負(fù)載因子，也就是下一次的擴(kuò)容點(diǎn)
34     */
35    this.threshold = tableSizeFor(initialCapacity);
36}
37
38/**
39 * 這個(gè)方法是用來(lái)計(jì)算出大于等于cap的最小2次冪的，但是實(shí)現(xiàn)的方式很精巧，充分利用了二進(jìn)制的特性
40 */
41static final int tableSizeFor(int cap) {
42    /*
43    這里的-1操作是為了防止cap現(xiàn)在就已經(jīng)是2的冪的情況，后面會(huì)進(jìn)行說(shuō)明。為了便于理解，這里舉個(gè)例子：
44    假設(shè)此時(shí)cap為34（100010），n就是33（100001）。我們其實(shí)只要關(guān)注第一個(gè)最高位是1的這個(gè)位置，即從左
45    到右第一個(gè)為1的位置。通用的解釋是01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx（x代表不確定，不用關(guān)心這個(gè)位置上是0還是1）
46     */
47    int n = cap - 1;
48    /*
49    經(jīng)過(guò)一次右移操作并按位或之后，n變成了110001（100001 | 010000）
50    通用解釋?zhuān)捍藭r(shí)變成了011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
51     */
52    n |= n >>> 1;
53    /*
54    此時(shí)經(jīng)過(guò)兩次右移操作并按位或之后，n變成了111101（110001 | 001100）
55    通用解釋?zhuān)捍藭r(shí)變成了01111xxxxxxxxxxxxxxxxxxxxxxxxxxx
56     */
57    n |= n >>> 2;
58    /*
59    此時(shí)經(jīng)過(guò)四次右移操作并按位或之后，n變成了111111（111101 | 000011）
60    通用解釋?zhuān)捍藭r(shí)變成了011111111xxxxxxxxxxxxxxxxxxxxxxx
61     */
62    n |= n >>> 4;
63    /*
64    此時(shí)經(jīng)過(guò)八次右移操作并按位或，對(duì)于上面的示例數(shù)據(jù)來(lái)說(shuō)，此時(shí)已經(jīng)變成了所有位都是1的情況，
65    那么下面的兩次右移操作做了和沒(méi)做已經(jīng)沒(méi)區(qū)別了（因?yàn)橛乙坪蟮慕Y(jié)果肯定是0，和原來(lái)的數(shù)按位或之后是沒(méi)有變的）
66    其實(shí)經(jīng)過(guò)這么多次的右移并按位或，就是為了最后能得出一個(gè)全是1的數(shù)
67    通用解釋?zhuān)捍藭r(shí)變成了01111111111111111xxxxxxxxxxxxxxx
68     */
69    n |= n >>> 8;
70    /*
71    此時(shí)經(jīng)過(guò)十六次右移操作并按位或，通用解釋?zhuān)捍藭r(shí)變成了01111111111111111111111111111111
72    需要說(shuō)明一下的是int的位數(shù)是32位，所以只需要右移16位就可以停止了（當(dāng)然也可以繼續(xù)右移32位，64位...
73    只不過(guò)那樣的話(huà)就沒(méi)有什么意義了，因?yàn)橛乙坪蟮慕Y(jié)果都是0，按位或的結(jié)果是不會(huì)發(fā)生變動(dòng)的）
74    而int的最大值MAX_VALUE是2的31次方-1，換算成二進(jìn)制就是有31個(gè)1
75    在之前的第25行代碼處已經(jīng)將該值改為了2的30次方，1后面有30個(gè)0，即010000...000
76    所以傳進(jìn)來(lái)該方法的最大值cap只能是這個(gè)數(shù)，經(jīng)過(guò)-1再幾次右移操作后就變成了00111...111，即30個(gè)1
77    最后在第90行代碼處+1后又會(huì)重新修正為2的30次方，即MAXIMUM_CAPACITY
78     */
79    n |= n >>> 16;
80    /*
81    n如果小于0對(duì)應(yīng)的是傳進(jìn)來(lái)的cap本身就是0的情況。經(jīng)過(guò)右移后，n變成了-1（其實(shí)右不右移根本不會(huì)改變結(jié)果，
82    因?yàn)?1的二進(jìn)制數(shù)就是32個(gè)1，和任何數(shù)按位或都不會(huì)發(fā)生變動(dòng)），這個(gè)時(shí)候就返回結(jié)果1（2的0次方）就行了
83
84    由此可以看到，最后的效果就是得出了一個(gè)原始數(shù)據(jù)從第一個(gè)最高位為1的這個(gè)位置開(kāi)始，后面的所有位不管是0還是1都改成1
85    最后在第90行代碼處再加一后就變成了最高位是1而剩下位都是0的一個(gè)數(shù)，但是位數(shù)比原數(shù)據(jù)多一位，也就是原數(shù)據(jù)的最小2次冪了
86
87    現(xiàn)在可以考慮一下之前說(shuō)過(guò)的如果傳進(jìn)來(lái)的cap本身就是2的冪的情況。假如說(shuō)沒(méi)有第47行代碼操作的話(huà)，那么經(jīng)過(guò)不斷右移操作后，
88    得出來(lái)的是一個(gè)全是1的二進(jìn)制數(shù)，也就是這個(gè)數(shù)*2-1的結(jié)果，最后再加1后就變成了原數(shù)據(jù)的2倍，這顯然是不對(duì)的
89     */
90    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
91}

3 put方法

 1/**
 2 * HashMap:
 3 */
 4public V put(K key, V value) {
 5    return putVal(hash(key), key, value, false, true);
 6}
 7
 8/**
 9 * 計(jì)算key的hash值
 10 * 注意這里是直接調(diào)用key的hashCode方法，并且會(huì)將其高16位和低16位進(jìn)行異或來(lái)作為最終的hash（Java中的int值是32位）
 11 * 那么為什么會(huì)這樣做呢？因?yàn)樵诤罄m(xù)的判斷插入桶bin的位置使用的方法是(table.length - 1) & hash
 12 * 這里數(shù)組的長(zhǎng)度必須為2的冪（如果不是則會(huì)轉(zhuǎn)換成大于該值的最小2次冪，詳見(jiàn)tableSizeFor方法），那么數(shù)組的長(zhǎng)度減去1后的值
 13 * 用二進(jìn)制來(lái)表示就是11111...低位全都是1的一個(gè)數(shù)。這樣再去和本方法計(jì)算出來(lái)的hash值進(jìn)行按位與的話(huà)，結(jié)果就是一個(gè)
 14 * 保留了hash值所有這些低位上的數(shù)，說(shuō)白了就是和hash % table.length這種是一樣的結(jié)果，就是對(duì)數(shù)組長(zhǎng)度取余而已
 15 * 但是直接用%做取余的話(huà)效率不高，而且這種按位與的方式只能適用于數(shù)組長(zhǎng)度是2的冪的情況，不是這種情況的話(huà)是不能做等價(jià)交換的
 16 * 
 17 * 從上面可以看到，按位與的方式只會(huì)用到hash值低位的信息，高位的信息不管是什么都無(wú)所謂，反正不會(huì)記錄到最后的hash計(jì)算中
 18 * 這樣的話(huà)就覺(jué)得有些可惜、有些浪費(fèi)。如果將高位信息也進(jìn)行記錄的話(huà)那就更好了。所以在下面第26行代碼處，
 19 * 將其高16位和低16位進(jìn)行異或，就是為了將高16位的特征信息也融合進(jìn)hash值中，盡量使哈希變得散列，減少hash沖突的發(fā)生
 20 * 同時(shí)使用一個(gè)異或操作的話(huà)也很簡(jiǎn)單高效，不會(huì)像有些hash函數(shù)一樣會(huì)進(jìn)行很多的計(jì)算后才會(huì)生成一個(gè)hash值（比如說(shuō)這塊
 21 * 在Java 7中的實(shí)現(xiàn)就是會(huì)有很多次的右移操作）
 22 * <<<在底層源碼中，在能完成需求的前提下，能實(shí)現(xiàn)得越簡(jiǎn)單越高效，就是王道>>>
 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        //如果當(dāng)前數(shù)組還沒(méi)有初始化的話(huà)，就進(jìn)行初始化的工作。由此可以看到，HashMap的初始化工作被延遲到了put方法中
 39        n = (tab = resize()).length;
 40    if ((p = tab[i = (n - 1) & hash]) == null)
 41        /*
 42        通過(guò)(n - 1) & hash的方式來(lái)找到這個(gè)數(shù)據(jù)插入的桶位置（至于為什么用這種方式詳見(jiàn)hash方法的注釋?zhuān)?
 43        如果這個(gè)桶上還沒(méi)有數(shù)據(jù)存在的話(huà)，就直接創(chuàng)建一個(gè)新的Node節(jié)點(diǎn)插入進(jìn)這個(gè)桶就可以了，也就是快速判斷
 44         */
 45        tab[i] = newNode(hash, key, value, null);
 46    else {
 47        /*
 48        否則如果這個(gè)桶上有數(shù)據(jù)的話(huà)，就執(zhí)行下面的邏輯
 49
 50        e是用來(lái)判斷新插入的這個(gè)節(jié)點(diǎn)是否能插入進(jìn)去，如果不為null就意味著找到了這個(gè)新節(jié)點(diǎn)要插入的位置
 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            如果桶上第一個(gè)節(jié)點(diǎn)的hash值和要插入的hash值相同，并且key也是相同的話(huà)，
 58            就記錄一下這個(gè)位置e，后續(xù)會(huì)做值的覆蓋（快速判斷模式）
 59             */
 60            e = p;
 61        //走到這里說(shuō)明要插入的節(jié)點(diǎn)和當(dāng)前桶中的第一個(gè)節(jié)點(diǎn)不是同一個(gè)節(jié)點(diǎn)，但是他們計(jì)算出來(lái)的hash值是一樣的
 62        else if (p instanceof TreeNode)
 63            //如果節(jié)點(diǎn)是紅黑樹(shù)的話(huà)，就執(zhí)行紅黑樹(shù)的插入節(jié)點(diǎn)邏輯（紅黑樹(shù)的分析本文不做展開(kāi)）
 64            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
 65        else {
 66            //走到這里說(shuō)明鏈表上有多個(gè)節(jié)點(diǎn)，遍歷鏈表上的節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)不需要判斷了，因?yàn)樵诘?4行代碼處已經(jīng)判斷過(guò)了）
 67            for (int binCount = 0; ; ++binCount) {
 68                if ((e = p.next) == null) {
 69                    /*
 70                    如果當(dāng)前鏈表的下一個(gè)位置為null，意味著已經(jīng)循環(huán)到最后一個(gè)節(jié)點(diǎn)還沒(méi)有找到一樣的，
 71                    此時(shí)將要插入的新節(jié)點(diǎn)插到最后
 72                     */
 73                    p.next = newNode(hash, key, value, null);
 74                    //如果循環(huán)到此時(shí)，鏈表的數(shù)量已經(jīng)達(dá)到了轉(zhuǎn)成紅黑樹(shù)的閾值的時(shí)候，就進(jìn)行轉(zhuǎn)換
 75                    if (binCount >= TREEIFY_THRESHOLD - 1)
 76                        /*
 77                        之前分析過(guò)，是否真正會(huì)轉(zhuǎn)成紅黑樹(shù)，需要看當(dāng)前數(shù)組的桶的個(gè)數(shù)
 78                        是否大于等于MIN_TREEIFY_CAPACITY，小于就只是擴(kuò)容
 79                         */
 80                        treeifyBin(tab, hash);
 81                    break;
 82                }
 83                if (e.hash == hash &&
 84                        ((k = e.key) == key || (key != null && key.equals(k))))
 85                    //如果這個(gè)節(jié)點(diǎn)之前就在鏈表中存在，就可以退出循環(huán)了（e在第68行代碼處已經(jīng)被賦值了）
 86                    break;
 87                p = e;
 88            }
 89        }
 90        if (e != null) {
 91            /*
 92            如果找到了要插入的位置的話(huà)，就做值的覆蓋
 93
 94            記錄舊值，并最終返回出去
 95             */
 96            V oldValue = e.value;
 97            //如果onlyIfAbsent為false，或者本身舊值就為null，就新值覆蓋舊值
 98            if (!onlyIfAbsent || oldValue == null)
 99                e.value = value;
100            //鉤子方法，空實(shí)現(xiàn)
101            afterNodeAccess(e);
102            return oldValue;
103        }
104    }
105    /*
106    走到這里說(shuō)明之前是走到了第45行代碼處，添加了一個(gè)新的節(jié)點(diǎn)。
107
108    修改次數(shù)+1，modCount是用來(lái)做快速失敗的。如果迭代器中做修改，modCount != expectedModCount，
109    表明此時(shí)HashMap被其他線(xiàn)程修改了，會(huì)拋出ConcurrentModificationException異常（我在分析ArrayList
110    的源碼文章中詳細(xì)解釋了這一過(guò)程，在HashMap中也是類(lèi)似的）
111     */
112    ++modCount;
113    /*
114    既然是添加了一個(gè)新的節(jié)點(diǎn)，那么就需要判斷一下此時(shí)是否需要擴(kuò)容
115    如果當(dāng)前數(shù)組容量已經(jīng)超過(guò)了設(shè)定好的threshold閾值的時(shí)候，就執(zhí)行擴(kuò)容操作
116     */
117    if (++size > threshold)
118        resize();
119    //鉤子方法，空實(shí)現(xiàn)
120    afterNodeInsertion(evict);
121    return null;
122}

4 resize方法

??在上面putVal方法中的第39行和118行代碼處，都是調(diào)用了resize方法來(lái)進(jìn)行初始化或擴(kuò)容的。而resize方法也是HashMap源碼中比較精髓、比較有亮點(diǎn)的一個(gè)方法。其具體實(shí)現(xiàn)大致可以分為兩部分：設(shè)置擴(kuò)容標(biāo)志位和具體的數(shù)據(jù)遷移過(guò)程。下面就首先來(lái)看一下resize方法的前半部分源碼：

 1/**
 2 * HashMap:
 3 * 擴(kuò)容操作（當(dāng)前數(shù)組為空的話(huà)就變成了對(duì)數(shù)組初始化的操作）
 4 */
 5final Node<K, V>[] resize() {
 6    Node<K, V>[] oldTab = table;
 7    //記錄舊數(shù)組（當(dāng)前數(shù)組）的容量，如果為null就是0
 8    int oldCap = (oldTab == null) ? 0 : oldTab.length;
 9    /*
 10    1.在調(diào)用有參構(gòu)造器的時(shí)候threshold存放的是大于等于當(dāng)前數(shù)組容量的最小2次冪，將其賦值給oldThr
 11    2.調(diào)用無(wú)參構(gòu)造器的時(shí)候threshold=0
 12    3.之前數(shù)組已經(jīng)不為空，現(xiàn)在在做擴(kuò)容的時(shí)候，threshold存放的是舊數(shù)組容量 * 負(fù)載因子
 13     */
 14    int oldThr = threshold;
 15    //newCap指的是數(shù)組擴(kuò)容后的數(shù)量，newThr指的是newCap * 負(fù)載因子后的結(jié)果（如果計(jì)算出來(lái)有小數(shù)就取整數(shù)部分）
 16    int newCap, newThr = 0;
 17    //下面就是對(duì)各種情況進(jìn)行分析，然后將newCap和newThr標(biāo)記位進(jìn)行賦值的過(guò)程
 18    if (oldCap > 0) {
 19        if (oldCap >= MAXIMUM_CAPACITY) {
 20            /*
 21            如果當(dāng)前數(shù)組容量已經(jīng)超過(guò)了設(shè)定的最大值，就將threshold設(shè)置為int的最大值，然后返回當(dāng)前數(shù)組容量
 22            也就意味著在這種情況下不進(jìn)行擴(kuò)容操作
 23             */
 24            threshold = Integer.MAX_VALUE;
 25            return oldTab;
 26        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 27                oldCap >= DEFAULT_INITIAL_CAPACITY)
 28            /*
 29            如果當(dāng)前數(shù)組容量*2后沒(méi)有超過(guò)設(shè)定的最大值，并且當(dāng)前數(shù)組容量是大于等于初始容量16的話(huà)，
 30            就將newCap設(shè)置為oldCap * 2，newThr設(shè)置為oldThr * 2
 31            oldCap >= DEFAULT_INITIAL_CAPACITY這個(gè)條件出現(xiàn)的意義在后面會(huì)說(shuō)明
 32             */
 33            newThr = oldThr << 1;
 34    } else if (oldThr > 0)
 35        /*
 36        走到這里說(shuō)明oldCap=0，也就是當(dāng)前是初始化數(shù)組的時(shí)候。我們剛才看到如果是默認(rèn)的無(wú)參構(gòu)造器的話(huà)，
 37        threshold是不會(huì)被賦值的，也就是為0。但是如果調(diào)用的是有參的構(gòu)造器，threshold就會(huì)在構(gòu)造器初始階段被賦值了，
 38        而這個(gè)if條件就是對(duì)應(yīng)于這種情況。這里設(shè)置為oldThr是因?yàn)樵谏厦娴牡?4行代碼處可以看到oldThr指向的是threshold，
 39        也就是說(shuō)oldThr的值是大于等于“當(dāng)前數(shù)組容量”的最小2次冪（注意，“當(dāng)前數(shù)組容量”我在這里是加上引號(hào)的，
 40        也就是說(shuō)并不是現(xiàn)在真正物理存在的數(shù)組容量（當(dāng)前的物理容量是0），而是通過(guò)構(gòu)造器傳進(jìn)來(lái)設(shè)定的容量），
 41        肯定是個(gè)大于0的數(shù)。既然這個(gè)oldThr現(xiàn)在就代表著我想要設(shè)定的新容量，那么直接就將newCap也賦值成這個(gè)數(shù)就可以了
 42         */
 43        newCap = oldThr;
 44    else {
 45        /*
 46        如上所說(shuō)，這里對(duì)應(yīng)的是調(diào)用無(wú)參構(gòu)造器，threshold=0的時(shí)候
 47        將newCap賦值為16，newThr賦值為16 * 0.75 = 12，都是取默認(rèn)的值
 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條件中沒(méi)有對(duì)newThr進(jìn)行賦值，此時(shí)計(jì)算出ft = 新數(shù)組容量 * 負(fù)載因子，
 56        如果數(shù)組容量和ft都沒(méi)有超過(guò)設(shè)定的最大值的話(huà)，就將newThr賦值為ft，否則賦值給int的最大值
 57
 58        第二種：注意到上面第27行代碼處的條件，如果oldCap比16要小的話(huà)，newThr也是沒(méi)有賦值的。
 59        出現(xiàn)這種情況的根源不在于這一次resize方法的調(diào)用，而是在于上一次初始化時(shí)候的調(diào)用。舉個(gè)例子就明白了：
 60        一開(kāi)始我是調(diào)用new HashMap<>(2)這個(gè)構(gòu)造器，經(jīng)過(guò)計(jì)算后threshold=2。接著調(diào)用put方法觸發(fā)初始化會(huì)跳進(jìn)該方法里
 61        此時(shí)oldCap=0，oldThr=2。接著會(huì)走進(jìn)第34行代碼處的if條件中，newCap=2，然后會(huì)走進(jìn)第52行代碼處，
 62        也就是本if條件中：newThr=1，然后修改threshold=1。之后resize方法就會(huì)走具體的擴(kuò)容操作了
 63        但是之前這些設(shè)置的標(biāo)志位都不會(huì)被更改，擴(kuò)容后就退出該方法了。這是第一次調(diào)用過(guò)程。
 64        然后我此時(shí)成功插入了這個(gè)節(jié)點(diǎn)后，又再次調(diào)用了put方法。此時(shí)還是會(huì)把該節(jié)點(diǎn)插入成功進(jìn)去，
 65        但是在上面putVal方法中的第117行代碼處判斷發(fā)現(xiàn)，我當(dāng)前的size=2已經(jīng)大于了threshold=1。于是又會(huì)調(diào)用resize該方法來(lái)進(jìn)行擴(kuò)容
 66        而此時(shí)oldCap=2，oldThr=1。會(huì)走到第26行代碼處的if條件中，newCap=4，而此時(shí)的oldCap=2要小于16，
 67        于是就跳出了該if條件，然后會(huì)走進(jìn)第52行代碼處，也就是本if條件中：newThr=3，然后修改threshold=3
 68        這是正確的情況，因?yàn)閚ewThr本身就是newCap * 負(fù)載因子后的結(jié)果，即 4 * 0.75 = 3
 69        那么假如說(shuō)源碼里沒(méi)有第27行代碼處的判斷條件的話(huà)，就會(huì)跳進(jìn)到第33行代碼處，此時(shí)的oldThr=1，所以newThr=2
 70        可以看到此時(shí)newCap=4而newThr=2，發(fā)生了錯(cuò)誤，4 * 0.75不等于2。所以說(shuō)在第27行代碼處的
 71        oldCap >= DEFAULT_INITIAL_CAPACITY這個(gè)條件的出現(xiàn)，將原本在第33行代碼處進(jìn)行更新newThr的操作
 72        改為了在第97行代碼處，以解決newThr更新不準(zhǔn)確的問(wèn)題
 73
 74        當(dāng)然這里只是演示了可能出錯(cuò)的一種情況，并沒(méi)有說(shuō)到本質(zhì)。其實(shí)我通過(guò)對(duì)比其他的一些數(shù)據(jù)來(lái)演示這個(gè)結(jié)果后發(fā)現(xiàn)：
 75        如果桶的個(gè)數(shù)超過(guò)了16也會(huì)存在這種差異點(diǎn)。其實(shí)上述的出錯(cuò)可以一般化：一個(gè)是原容量 * 負(fù)載因子后取整，然后*2，
 76        另一個(gè)是原容量 * 2 * 負(fù)載因子后再取整。差異點(diǎn)就在于取整的時(shí)機(jī)。而出現(xiàn)差別也就是
 77        原容量 * 負(fù)載因子后是一個(gè)帶小數(shù)的數(shù)（如果為整數(shù)是不會(huì)有差別的，而且也并不是所有帶小數(shù)的數(shù)都會(huì)有差異），
 78        這個(gè)帶小數(shù)的數(shù)取整后再*2，差異點(diǎn)被放大了，從而導(dǎo)致最終的不同。還有一處線(xiàn)索是第27行代碼處的
 79        oldCap >= DEFAULT_INITIAL_CAPACITY，注意這里是大于等于，而不是小于等于，也就是說(shuō)
 80        只有大于等于16的話(huà)才會(huì)走進(jìn)這個(gè)if條件（快速計(jì)算threshold結(jié)果），小于16的話(huà)會(huì)走進(jìn)本if條件
 81        （精確計(jì)算threshold結(jié)果）。所以說(shuō)如果桶的個(gè)數(shù)大于16，閾值多一個(gè)少一個(gè)的話(huà)可能就沒(méi)那么重要了，
 82        比如說(shuō)1024個(gè)桶，我是在819個(gè)桶滿(mǎn)了的時(shí)候去擴(kuò)容還是在818個(gè)，似乎差別也不太大，在這種情況下
 83        就因?yàn)槲野验撝祎hreshold多減去了1個(gè)，從而會(huì)導(dǎo)致哈希沖突變高？還是空間更浪費(fèi)了？其實(shí)不見(jiàn)得
 84        畢竟數(shù)據(jù)量在這里擺著，而且負(fù)載因子一般都是小于1的數(shù)，所以這個(gè)差別最多也就是1個(gè)。這個(gè)差異點(diǎn)也會(huì)隨著
 85        數(shù)據(jù)的越來(lái)越大而顯得越來(lái)越不重要。但是如果像前面舉的例子，4個(gè)桶我是在2個(gè)桶滿(mǎn)了還是3個(gè)桶滿(mǎn)的時(shí)候去擴(kuò)容，
 86        這個(gè)差別就很大了，這兩種情況下hash沖突發(fā)生概率的對(duì)比肯定是比較大的?？赡芤粋€(gè)是20%，另一個(gè)是40%，
 87        而桶的個(gè)數(shù)比較大的時(shí)候這個(gè)差異對(duì)比可能就是1.2%和1.3%（這個(gè)數(shù)是我隨便舉的）。這樣的話(huà)在數(shù)據(jù)量大
 88        而且擴(kuò)容方法頻繁調(diào)用的時(shí)候（比如我要存進(jìn)一個(gè)特別大的容量但是沒(méi)有指定初始容量），我犧牲了計(jì)算閾值的準(zhǔn)確性
 89        （如果負(fù)載因子設(shè)置合理，這個(gè)差異就只有1個(gè)的區(qū)別），但換來(lái)了執(zhí)行速度的高效（注意在第33行代碼處是左移操作，
 90        而在第96行代碼處是乘法，乘法后又接著一個(gè)三目運(yùn)算符，然后又取整）；但是數(shù)據(jù)量小的時(shí)候，明顯是計(jì)算準(zhǔn)確更重要，
 91        而且數(shù)據(jù)量小的情況下也談不上什么性能差異，畢竟這里設(shè)定的閾值是16。所以在上面第14行代碼處的注釋中，
 92        threshold有第四種取值：舊數(shù)組容量 * 負(fù)載因子 - 1（具體減去幾要看負(fù)載因子設(shè)置的值以及數(shù)組容量），
 93        但是這種完全可以算作是第三種的特殊情況。所以總結(jié)來(lái)說(shuō)：第27行代碼處添加的意義就是為了在桶數(shù)量比較大、
 94        擴(kuò)容方法頻繁調(diào)用的時(shí)候，稍微犧牲一些準(zhǔn)確性，但是能讓threshold閾值計(jì)算得更快一些，是一種優(yōu)化手段
 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標(biāo)記位都設(shè)置好了后，下面就是具體的數(shù)據(jù)遷移的過(guò)程，也就是resize方法后半部分的實(shí)現(xiàn)：

 1/**
 2 * HashMap:
 3 */
 4final Node<K, V>[] resize() {
 5    //...
 6
 7    //此時(shí)newCap和newThr標(biāo)記位都已經(jīng)設(shè)置好了，將根據(jù)newCap新的容量來(lái)創(chuàng)建一個(gè)新的Node數(shù)組，以此來(lái)替代舊數(shù)組
 8    @SuppressWarnings({"rawtypes", "unchecked"})
 9    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
 10    table = newTab;
 11    //如果舊數(shù)組為null，也就是說(shuō)現(xiàn)在是對(duì)數(shù)組做初始化的操作。那么直接就返回創(chuàng)建的新數(shù)組newTab就行了
 12    if (oldTab != null) {
 13        //遍歷舊數(shù)組上的每一個(gè)桶
 14        for (int j = 0; j < oldCap; ++j) {
 15            Node<K, V> e;
 16            //如果舊數(shù)組的這個(gè)桶上沒(méi)有數(shù)據(jù)的話(huà)，就跳過(guò)它，不進(jìn)行擴(kuò)容
 17            if ((e = oldTab[j]) != null) {
 18                //舊數(shù)組上的這個(gè)節(jié)點(diǎn)賦值為null，便于快速GC
 19                oldTab[j] = null;
 20                if (e.next == null)
 21                    /*
 22                    第一個(gè)節(jié)點(diǎn)后面沒(méi)有后續(xù)節(jié)點(diǎn)，也就意味著這個(gè)桶上只有一個(gè)節(jié)點(diǎn)，
 23                    那么只需要通過(guò)計(jì)算找出新位置放進(jìn)去就行了，這里也就是在做快速遷移
 24                     */
 25                    newTab[e.hash & (newCap - 1)] = e;
 26                else if (e instanceof TreeNode)
 27                    //如果是紅黑樹(shù)，就執(zhí)行紅黑樹(shù)的遷移邏輯（紅黑樹(shù)的分析本文不做展開(kāi)）
 28                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
 29                else {
 30                    /*
 31                    走到這里說(shuō)明當(dāng)前這個(gè)桶里面有不止一個(gè)的節(jié)點(diǎn)，此時(shí)就會(huì)做鏈表上多個(gè)節(jié)點(diǎn)的遷移工作
 32                    首先來(lái)說(shuō)一下大前提：現(xiàn)在舊數(shù)組上桶的位置是j，而準(zhǔn)備放進(jìn)新數(shù)組的桶位置有兩個(gè)：一個(gè)是j，
 33                    也就是說(shuō)新數(shù)組上也會(huì)放在j這個(gè)位置上；另一個(gè)是j+舊數(shù)組的容量。比方說(shuō)當(dāng)前桶的位置15，
 34                    而舊數(shù)組的容量是16，那么新數(shù)組上第二個(gè)將要插入的桶的位置就是15 + 16 = 31
 35
 36                    說(shuō)完了大前提，再來(lái)看下面的代碼。以下定義了四個(gè)指針位置，
 37                    分別就對(duì)應(yīng)了上面說(shuō)的兩個(gè)新插入桶位置的頭尾指針
 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指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
 44                        next = e.next;
 45                        /*
 46                        那么現(xiàn)在的問(wèn)題就是通過(guò)什么辦法來(lái)判斷到底是插入到j(luò)位置還是j+舊數(shù)組容量的位置呢？
 47                        其實(shí)也很簡(jiǎn)單，就是通過(guò)節(jié)點(diǎn)的哈希值和舊數(shù)組的容量按位與的方式來(lái)判斷的。舊數(shù)組容量
 48                        經(jīng)過(guò)上面的分析后可以知道，肯定是一個(gè)2的冪，也就是1000...000，最高位為1，而剩余位都是0的形式
 49                        這樣按位與的結(jié)果就是取出了節(jié)點(diǎn)hash上的那個(gè)與舊數(shù)組所對(duì)應(yīng)的1的那個(gè)位置上的數(shù)。
 50                        比如說(shuō)節(jié)點(diǎn)的hash值是1010110，舊數(shù)組容量是16（1000），那么按位與的結(jié)果就是
 51                        取出了hash值中從右往左第四位的值，即0。也就是說(shuō)，存在新數(shù)組哪個(gè)位置上，取決于hash值
 52                        所對(duì)應(yīng)舊數(shù)組容量為1的那個(gè)位置上到底是0還是1。從這里也可以看出，除了
 53                        (table.length - 1) & hash這種方式用來(lái)判斷插入桶的位置，是必須要求數(shù)組容量是2的冪之外，
 54                        在擴(kuò)容做遷移的時(shí)候，也必須要求了這點(diǎn)
 55
 56                        按位與的結(jié)果只有兩種，不是0就是1，所以如果為0的話(huà)最后就會(huì)插入到新數(shù)組的j位置，
 57                        為1就插入到j(luò)+舊數(shù)組容量的位置（后面會(huì)解釋如果換一下的話(huà)，到底行不行）
 58                         */
 59                        if ((e.hash & oldCap) == 0) {
 60                            if (loTail == null)
 61                                //如果當(dāng)前是第一個(gè)插進(jìn)來(lái)的節(jié)點(diǎn)，就將loHead頭指針指向它
 62                                loHead = e;
 63                            else
 64                                /*
 65                                不是第一個(gè)的話(huà)，就將loTail尾指針的下一個(gè)next指針指向它，也就是把鏈拉上
 66                                loTail在之前已經(jīng)指向了最后一個(gè)節(jié)點(diǎn)處
 67                                 */
 68                                loTail.next = e;
 69                            //更新一下loTail尾指針，重新指向此時(shí)的最后一個(gè)節(jié)點(diǎn)處
 70                            loTail = e;
 71                        } else {
 72                            //(e.hash & oldCap) == 1
 73                            if (hiTail == null)
 74                                //如果當(dāng)前是第一個(gè)插進(jìn)來(lái)的節(jié)點(diǎn)，就將hiHead頭指針指向它
 75                                hiHead = e;
 76                            else
 77                                /*
 78                                不是第一個(gè)的話(huà)，就將hiTail尾指針的下一個(gè)next指針指向它，也就是把鏈拉上
 79                                hiTail在之前已經(jīng)指向了最后一個(gè)節(jié)點(diǎn)處
 80                                 */
 81                                hiTail.next = e;
 82                            //更新一下hiTail尾指針，重新指向此時(shí)的最后一個(gè)節(jié)點(diǎn)處
 83                            hiTail = e;
 84                        }
 85                    //如果當(dāng)前遍歷鏈表上的節(jié)點(diǎn)還沒(méi)有到達(dá)最后一個(gè)節(jié)點(diǎn)處，就繼續(xù)循環(huán)去判斷
 86                    } while ((e = next) != null);
 87                    /*
 88                    走到這里說(shuō)明已經(jīng)將原來(lái)的舊數(shù)組上的鏈表拆分完畢了，現(xiàn)在分成了兩個(gè)鏈表，low和high
 89                    接下來(lái)需要做的工作就很清楚了：將這兩個(gè)鏈表分別插入到j(luò)位置和j+舊數(shù)組容量的位置就可以了
 90                     */
 91                    if (loTail != null) {
 92                        /*
 93                        如果low鏈表有節(jié)點(diǎn)的話(huà)（沒(méi)節(jié)點(diǎn)說(shuō)明之前的按位與的計(jì)算結(jié)果都是1），就重新更新一下low鏈表上
 94                        最后一個(gè)節(jié)點(diǎn)的next指針指向null。這步操作很重要，因?yàn)槿绻斑@個(gè)節(jié)點(diǎn)不是
 95                        舊數(shù)組桶上的最后一個(gè)節(jié)點(diǎn)的話(huà)，next是有值的。不改成null的話(huà)指針指向就亂了
 96                         */
 97                        loTail.next = null;
 98                        //將鏈表插入到j(luò)位置
 99                        newTab[j] = loHead;
100                    }
101                    if (hiTail != null) {
102                        /*
103                        如果high鏈表有節(jié)點(diǎn)的話(huà)（沒(méi)節(jié)點(diǎn)說(shuō)明之前的按位與的計(jì)算結(jié)果都是0），就重新更新一下high鏈表上
104                        最后一個(gè)節(jié)點(diǎn)的next指針指向null。這步操作很重要，因?yàn)槿绻斑@個(gè)節(jié)點(diǎn)不是
105                        舊數(shù)組桶上的最后一個(gè)節(jié)點(diǎn)的話(huà)，next是有值的。不改成null的話(huà)指針指向就亂了
106                         */
107                        hiTail.next = null;
108                        //將鏈表插入到j(luò)+舊數(shù)組容量的位置
109                        newTab[j + oldCap] = hiHead;
110                    }
111                }
112            }
113        }
114    }
115    return newTab;
116}

??在Java 7的HashMap源碼中，transfer方法是用來(lái)做擴(kuò)容時(shí)的遷移數(shù)據(jù)操作的。其實(shí)現(xiàn)就是通過(guò)遍歷鏈表中的每一個(gè)節(jié)點(diǎn)，重新rehash實(shí)現(xiàn)的。在這其中會(huì)涉及到指針的修改，在高并發(fā)的場(chǎng)景下，可能會(huì)使鏈表上的一個(gè)節(jié)點(diǎn)的下一個(gè)指針指向了其前一個(gè)節(jié)點(diǎn)，也就是形成了死循環(huán)，死鏈（具體形成過(guò)程不再展開(kāi)）：

??這樣再去遍歷鏈表的時(shí)候就永遠(yuǎn)不會(huì)停下來(lái)，出現(xiàn)了bug。而Java 8中通過(guò)形成兩個(gè)鏈表，節(jié)點(diǎn)hash值在數(shù)組容量二進(jìn)制數(shù)為1的那個(gè)位置處去按位與判斷是0還是1，以此來(lái)選擇插入的方式很好地解決了這個(gè)問(wèn)題，而且不用每一個(gè)節(jié)點(diǎn)rehash，提高了執(zhí)行速度。

??既然說(shuō)到了不用rehash，那么這里想要探究一下在數(shù)組擴(kuò)容時(shí)，選擇新插入數(shù)組的位置是原位置和原位置+舊數(shù)組容量，為什么這里加上的是舊數(shù)組容量呢？加別的值不可以嗎？其實(shí)這里加舊數(shù)組容量是有原因的。我們都知道，數(shù)組容量必須是2的冪，即100…000，而新數(shù)組的容量是原數(shù)組的2倍，也就是把原來(lái)值中的“1”往左移了一位，而我們?cè)谂袛嗖迦胪拔恢脮r(shí)用的方式是（數(shù)組容量 - 1）& hash值。把這些信息都整合一下，我們就知道在新數(shù)組中計(jì)算桶位置和在舊數(shù)組中計(jì)算桶位置的差異，其實(shí)就在于舊數(shù)組二進(jìn)制為1上的這位上。如果該位是0，那就是和原來(lái)舊數(shù)組是同一個(gè)位置，如果是1，就是舊數(shù)組位置處+舊數(shù)組的容量。下面舉個(gè)例子：

??兩個(gè)節(jié)點(diǎn)此時(shí)計(jì)算出來(lái)桶的位置都是1010，即第10個(gè)桶。它們都會(huì)被放在第10個(gè)桶中的鏈表中。

??而現(xiàn)在數(shù)組擴(kuò)容了，數(shù)組容量變?yōu)榱?2，我們?cè)賮?lái)看看結(jié)果會(huì)怎樣：

??這時(shí)候發(fā)現(xiàn)(n - 1) & hash的結(jié)果不一樣了，節(jié)點(diǎn)1是01010，節(jié)點(diǎn)2是11010。也就是說(shuō)，我們?cè)趃et方法執(zhí)行的時(shí)候（get方法也是通過(guò)(n - 1) & hash的方式來(lái)找到桶的位置），找到節(jié)點(diǎn)1是在第10個(gè)桶，節(jié)點(diǎn)2是在第26個(gè)桶，這兩個(gè)節(jié)點(diǎn)之間相差16個(gè)桶，這不就是舊數(shù)組的容量嗎？現(xiàn)在是不是恍然大悟了，我們當(dāng)初在擴(kuò)容時(shí)，將節(jié)點(diǎn)的hash值和舊數(shù)組容量進(jìn)行按位與，其實(shí)也就是在找上圖紅框框中的那個(gè)位置。如果為0，就將節(jié)點(diǎn)1放在新數(shù)組中第10個(gè)桶中（1010），也就是原位置處；如果為1，就將節(jié)點(diǎn)2放在新數(shù)組中第26個(gè)桶中（1010+10000），也就是原位置+舊數(shù)組容量處。這樣做的話(huà)，我在get方法執(zhí)行的時(shí)候也能保證正確執(zhí)行，能正確找到節(jié)點(diǎn)在新數(shù)組中桶的位置。同時(shí)也說(shuō)明了，這個(gè)放入的策略是不能換的。也就是說(shuō)，不能是如果為1的話(huà)最后就會(huì)插入到新數(shù)組的原位置，為0就插入到原位置+舊數(shù)組容量的位置。如果這么做的話(huà)，最后get方法在查找該節(jié)點(diǎn)的時(shí)候，就找不到了（而實(shí)際上還存在）。所以通過(guò)Java 8中的這種擴(kuò)容方式，既能計(jì)算出正確的新桶位置，又能避免每一個(gè)節(jié)點(diǎn)的rehash，節(jié)省計(jì)算時(shí)間，實(shí)在是妙哉。

5 get方法

 1/**
 2 * HashMap:
 3 */
 4public V get(Object key) {
 5    Node<K, V> e;
 6    //如果獲取不到值，或者本身插入的value就是null的話(huà)，就返回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    //如果數(shù)組沒(méi)有初始化，或者計(jì)算出來(lái)的桶的位置為null（說(shuō)明找不到這個(gè)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            如果桶上第一個(gè)節(jié)點(diǎn)的hash值和要查找的hash值相同，并且key也是相同的話(huà)，
22            就直接返回（快速判斷模式）
23             */
24            return first;
25        /*
26        如果下一個(gè)節(jié)點(diǎn)為null，也就是當(dāng)前桶上只有一個(gè)節(jié)點(diǎn)的時(shí)候，
27        并且之前那個(gè)節(jié)點(diǎn)不是的話(huà)，那就直接返回null，也就是找不到
28         */
29        if ((e = first.next) != null) {
30            if (first instanceof TreeNode)
31                //如果節(jié)點(diǎn)是紅黑樹(shù)的話(huà)，就執(zhí)行紅黑樹(shù)的查找節(jié)點(diǎn)邏輯（紅黑樹(shù)的分析本文不做展開(kāi)）
32                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
33            /*
34            走到這里說(shuō)明鏈表上有多個(gè)節(jié)點(diǎn)，遍歷鏈表上的每一個(gè)節(jié)點(diǎn)進(jìn)行查找（第一個(gè)節(jié)點(diǎn)不需要判斷了，
35            因?yàn)樵诘?8行代碼處已經(jīng)判斷過(guò)了）
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}

6 remove方法

 1/**
 2 * HashMap:
 3 */
 4public V remove(Object key) {
 5    Node<K, V> e;
 6    //如果找不到要?jiǎng)h除的節(jié)點(diǎn)，就返回null，否則返回刪除的節(jié)點(diǎn)
 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    //如果數(shù)組沒(méi)有初始化，或者計(jì)算出來(lái)的桶的位置為null（說(shuō)明找不到這個(gè)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            //如果桶上第一個(gè)節(jié)點(diǎn)的hash值和要查找的hash值相同，并且key也是相同的話(huà)，就記錄一下該位置
25            node = p;
26        else if ((e = p.next) != null) {
27            //e是桶上第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，如果沒(méi)有的話(huà)，也說(shuō)明找不到要?jiǎng)h除的節(jié)點(diǎn)，就返回null
28            if (p instanceof TreeNode)
29                //如果節(jié)點(diǎn)是紅黑樹(shù)的話(huà)，就執(zhí)行紅黑樹(shù)的查找節(jié)點(diǎn)邏輯（紅黑樹(shù)的分析本文不做展開(kāi)）
30                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
31            else {
32                /*
33                走到這里說(shuō)明鏈表上有多個(gè)節(jié)點(diǎn)，遍歷鏈表上的每一個(gè)節(jié)點(diǎn)進(jìn)行查找，找到了就記錄一下該位置
34                （第一個(gè)節(jié)點(diǎn)不需要判斷了，因?yàn)樵诘?2行代碼處已經(jīng)判斷過(guò)了）
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                    //此時(shí)p記錄的是當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
44                    p = e;
45                } while ((e = e.next) != null);
46            }
47        }
48        /*
49        如果找到了要?jiǎng)h除的節(jié)點(diǎn)，并且如果matchValue為true（matchValue為true代表僅在value相等的情況下才能刪除）
50        并且value相等的時(shí)候（如果matchValue為false，就只需要判斷第一個(gè)條件node是否不為null）
51        當(dāng)然，如果不相等的話(huà)，就直接返回null，也就是不會(huì)刪除
52         */
53        if (node != null && (!matchValue || (v = node.value) == value ||
54                (value != null && value.equals(v)))) {
55            if (node instanceof TreeNode)
56                //如果節(jié)點(diǎn)是紅黑樹(shù)的話(huà)，就執(zhí)行紅黑樹(shù)的刪除節(jié)點(diǎn)邏輯（紅黑樹(shù)的分析本文不做展開(kāi)）
57                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
58            else if (node == p)
59                /*
60                如果要?jiǎng)h除的節(jié)點(diǎn)是桶上的第一個(gè)節(jié)點(diǎn)，就直接將當(dāng)前桶的第一個(gè)位置處賦值為下一個(gè)節(jié)點(diǎn)
61                （如果next為null就是賦值為null）
62                 */
63                tab[index] = node.next;
64            else
65                //不是桶上第一個(gè)節(jié)點(diǎn)就將前一個(gè)節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)，也就是將node節(jié)點(diǎn)從鏈表中剔除掉，等待GC
66                p.next = node.next;
67            //修改次數(shù)+1（快速失敗機(jī)制）
68            ++modCount;
69            //因?yàn)槭且獎(jiǎng)h除節(jié)點(diǎn)，所以如果找到了的話(huà)，size就-1
70            --size;
71            //鉤子方法，空實(shí)現(xiàn)
72            afterNodeRemoval(node);
73            return node;
74        }
75    }
76    return null;
77}

7 clear方法

 1/**
 2 * HashMap:
 3 */
 4public void clear() {
 5    Node<K, V>[] tab;
 6    //修改次數(shù)+1（快速失敗機(jī)制）
 7    modCount++;
 8    if ((tab = table) != null && size > 0) {
 9        //size記錄的是當(dāng)前有數(shù)據(jù)的桶的個(gè)數(shù)，因?yàn)檫@里要清空數(shù)據(jù)，所以將size重置為0
10        size = 0;
11        //同時(shí)將table中的每個(gè)桶都置為null就行了
12        for (int i = 0; i < tab.length; ++i)
13            tab[i] = null;
14    }
15}

在這行干的越久真是越覺(jué)得：萬(wàn)丈高樓平地起，這絕B是句真理！在應(yīng)用業(yè)務(wù)里待太久很多底層的東西往往容易忽略掉，今年的年初計(jì)劃是把常用的JDK源碼工具做一次總結(jié)，眼看年底將近，乘著最近有空，趕緊的給補(bǔ)上。

1. ArrayList你真懂？說(shuō)說(shuō)foreach與iterator時(shí)remove的區(qū)別

2. 你是否想過(guò)互聯(lián)網(wǎng)公司一面為什么總愛(ài)問(wèn)集合？聊聊經(jīng)典數(shù)據(jù)結(jié)構(gòu)HashMap

3. AQS源碼深入分析之獨(dú)占模式-ReentrantLock鎖特性詳解

4. AQS源碼深入分析之共享模式-為什么AQS中要有PROPAGATE這個(gè)狀態(tài)？

5. AQS源碼深入分析之條件隊(duì)列-Java中的阻塞隊(duì)列是如何實(shí)現(xiàn)的？

6. AQS源碼深入分析之應(yīng)用工具CountDownLatch（規(guī)劃中）

7. AQS源碼深入分析之應(yīng)用工具CyclicBarrier（規(guī)劃中）

8. ConcurrentHashMap源碼分析-ConcurrentHashMap在Java 8中的實(shí)現(xiàn)還有bug？而且還不止一處！這個(gè)坑還比較大，后面會(huì)重點(diǎn)總結(jié)一下！

9. ThreadPoolExecutor源碼分析-問(wèn)爛了的Java線(xiàn)程池執(zhí)行流程，其實(shí)如果問(wèn)的細(xì)，很多人還是一臉懵逼？

10. ScheduledThreadPoolExecutor源碼分析-重點(diǎn)屢屢定時(shí)線(xiàn)程池是如何實(shí)現(xiàn)延遲執(zhí)行和周期執(zhí)行！

11. ThreadLocal源碼分析-重點(diǎn)總結(jié)，內(nèi)存泄漏，軟引用弱引用虛引用，面試經(jīng)常喜歡問(wèn)，我也喜歡問(wèn)別個(gè)

12. 紅黑樹(shù)TreeMap、LinkedHashMap（不確定要不要寫(xiě)，有時(shí)間寫(xiě)，看項(xiàng)目情況）

13. 有序并且線(xiàn)程的Map容器ConcurrentSkipListMap（跳表）深入理解

14. LinkedList（不確定要不要寫(xiě)，有時(shí)間寫(xiě)，看項(xiàng)目情況）

15. 年底如果項(xiàng)目不趕，有空就在寫(xiě)一篇常用的排序算法的文章

每一次總結(jié)都是對(duì)知識(shí)點(diǎn)掌握程度的審視，技術(shù)不易，每日精進(jìn)一點(diǎn)，與大家共勉。

關(guān)于經(jīng)典數(shù)據(jù)結(jié)構(gòu)HashMap以及逐行分析每一個(gè)關(guān)鍵點(diǎn)就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。