前幾天在一個(gè)網(wǎng)站上回答問(wèn)題，雖然是平時(shí)經(jīng)常遇到的，但有很多點(diǎn)都被人模糊掉或者用一些專業(yè)名詞蓋掉。筆者覺(jué)得這個(gè)問(wèn)題很不錯(cuò)，是一種學(xué)習(xí)思路，于是回答后并將自己的答案記錄下來(lái)，如下：
1. if ((tab = table) == null || (n = tab.length) == 0)
2.? ? ? ? ? n = (tab = resize()).length;
3.? ? ? if ((p = tab[i = (n - 1) & hash]) == null)
4.? ? ? ? ? tab[i] = newNode(hash, key, value, null);
5.? ? ? else {
6.? ? ? ? ? Node e; K k;
7.? ? ? ? ? if (p.hash == hash &&
8.? ? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))
9.? ? ? ? ? ? ? e = p;
10.? ? ? ? ? else if (p instanceof TreeNode)
11.? ? ? ? ? ? ? e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
12.? ? ? ? else {
13.? ? ? ? ? ? for (int binCount = 0; ; ++binCount) {
14.? ? ? ? ? ? ? ? ? if ((e = p.next) == null) {
15.? ? ? ? ? ? ? ? ? ? p.next = newNode(hash, key, value, null);
16.? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
? 17.? ? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
? 18.? ? ? ? ? ? ? ? ? ? break;
? 19.? ? ? ? ? ? ? ? }
? 20.? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? 21.? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? 22.? ? ? ? ? ? ? ? ? ? ? break;
? 23.? ? ? ? ? ? ? ? ? p = e;
? 24.? ? ? ? ? ? ? }
? 25.? ? ? ? }
解讀這一段源碼：
0. java1.8中，map的結(jié)構(gòu)是由Node[] + 鏈表組成的，和之前的主要區(qū)別是，鏈表部分，當(dāng)超過(guò)8個(gè)元素會(huì)轉(zhuǎn)成TreeNode對(duì)象，由TreeBin封裝，也就是鏈表轉(zhuǎn)換為樹(shù)形結(jié)構(gòu)便于存儲(chǔ)和查找。不是線程安全類，但是如果多線程操作會(huì)報(bào)出ConCurrentxxxException。
下面按行數(shù)來(lái)說(shuō)：
1.? 如果當(dāng)前Node[] 為null 或者 Node數(shù)組元素個(gè)數(shù)為0 執(zhí)行下面一行代碼（省略大括號(hào)）
2.? resize() 方法返回一個(gè)擴(kuò)容后的Node[],擴(kuò)容的機(jī)制為所需容量的兩倍，是原有的1.5倍，這個(gè)計(jì)算是由負(fù)載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 來(lái)決定的（具體的可以看一下resize()方法，如果有困難我們?cè)儆懻撘淮危?Node數(shù)組元素個(gè)數(shù)n 賦值為擴(kuò)容后的長(zhǎng)度。
4.? 「 (n - 1) & hash] 」定位數(shù)組下標(biāo)位置的經(jīng)典算法，你可以自己寫一個(gè)main方法來(lái)做幾個(gè)實(shí)驗(yàn)。n=16的話，計(jì)算結(jié)果肯定在0～15之間。p為計(jì)算后取到的一個(gè)Node節(jié)點(diǎn) 判斷是否為null (if else 省略大括號(hào))
5.? 如果上述判斷為true，那么當(dāng)前節(jié)點(diǎn)賦值為一個(gè)新建節(jié)點(diǎn) newNode(x,x,x,x); 這個(gè)不用說(shuō)吧。也是一個(gè)經(jīng)典數(shù)據(jù)結(jié)構(gòu)。
6.? 如果4 中判斷結(jié)果為false，證明當(dāng)前下標(biāo)為i的位置存在節(jié)點(diǎn)，那么進(jìn)行下列操作。
7、8、9.? 如果當(dāng)前node節(jié)點(diǎn)的hash 和 節(jié)點(diǎn)中key屬性值 雙等或值等（也就是進(jìn)行新舊值替換），則將當(dāng)前節(jié)點(diǎn)賦值給e。
10、11.? 如果當(dāng)前節(jié)點(diǎn)為TreeNode節(jié)點(diǎn)，則將當(dāng)前操作元素添加到TreeNode[]中（圖中，單獨(dú)的hash，key，value都是當(dāng)前操作元素的值）。
12.? 如果上述都不成立，直接執(zhí)行下列代碼（到這步的意思是，不會(huì)是覆蓋操作，當(dāng)前節(jié)點(diǎn)也不是treeNode，只能是將當(dāng)前節(jié)點(diǎn)拼接在列表末端）。
13-23. 這是一個(gè)看似無(wú)限循環(huán)的算法，這有幾個(gè)退出點(diǎn)，按順序來(lái)，第一個(gè)break，代表找到了列表末端，把當(dāng)前元素添加到末端即可。第二個(gè)break，是找到新舊值覆蓋的元素，進(jìn)行替換。
14行為常規(guī)列表遍歷。
15行為如果找到最后一個(gè)元素了，直接新建元素，將最后一個(gè)元素與新元素邏輯關(guān)聯(lián)。
16行 判斷當(dāng)前個(gè)數(shù)，是否大于或者等于7，如果是，則將列表轉(zhuǎn)化為TreeBin包裝類，其實(shí)列表轉(zhuǎn)樹(shù)的界限是8，但是數(shù)組下標(biāo)是從0開(kāi)始，所以是TREEIFY_THRESHOLD - 1。
17行就是轉(zhuǎn)化方法了。
補(bǔ)充 1：jdk8之后，hashmap中，數(shù)據(jù)結(jié)構(gòu)是Node[]+（鏈表|樹(shù)），Node[]肯定是不會(huì)改變的了，那什么時(shí)候用鏈表，什么時(shí)候是樹(shù)呢？他們有個(gè)臨界點(diǎn)，8，這個(gè)數(shù)字我在回答里也說(shuō)過(guò)，你在源碼里也能找到。知道這個(gè)8了，我們看下怎么轉(zhuǎn)化的，首先，數(shù)組中的一個(gè)元素，他是從鏈表就夠開(kāi)始構(gòu)造的，也就是說(shuō)，你連續(xù)put相同的(lenght-1)&hash的值，當(dāng)個(gè)數(shù)小于8的時(shí)候，用的都是鏈表，也是就是node.next=new Node()形式，當(dāng)個(gè)數(shù)大于等8的時(shí)候，將鏈表轉(zhuǎn)化為TreeNode形式（在內(nèi)部TreeNode托管給TreebBin，TreeNode是紅黑樹(shù)結(jié)構(gòu)。），p instenceof NodeTree 就是用來(lái)判斷，當(dāng)前數(shù)組元素結(jié)構(gòu)，是鏈表還是樹(shù)，如果返回時(shí)true，那么，當(dāng)前元素下的結(jié)構(gòu)已經(jīng)是樹(shù)，就用樹(shù)的方式將當(dāng)前操作的對(duì)象加入到樹(shù)中，反之還是鏈表，將當(dāng)前操作的對(duì)象，加入到鏈表末尾，加入完成之后，判斷是否需要轉(zhuǎn)化為樹(shù)結(jié)構(gòu)，判斷條件是什么呢，就是那個(gè)8。
補(bǔ)充 2: jdk8之后，初始化HashMap之后，他的容量size并不是16，初始化后的對(duì)象 是{},當(dāng)有寫操作進(jìn)行時(shí)，才會(huì)inittable 給他一個(gè)初始化容量1<<4,具體的請(qǐng)看源碼，如果不懂，歡迎留言一起討論。
補(bǔ)充 3： 有人說(shuō)到底是看jdk7好還是8好，我個(gè)人意見(jiàn)，以8為主，7也要看，看他為什么這么優(yōu)化，這么優(yōu)化的好處是什么，優(yōu)化的作者是如何想的，我想我們能把這種思想轉(zhuǎn)化為我們自己的，jdk這種教科書(shū)也算是成功的。
