前幾天在一個網(wǎng)站上回答問題，雖然是平時經(jīng)常遇到的匀归，但有很多點(diǎn)都被人模糊掉或者用一些專業(yè)名詞蓋掉坑资。筆者覺得這個問題很不錯，是一種學(xué)習(xí)思路穆端，于是回答后并將自己的答案記錄下來袱贮，如下：
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)超過8個元素會轉(zhuǎn)成TreeNode對象，由TreeBin封裝柒莉，也就是鏈表轉(zhuǎn)換為樹形結(jié)構(gòu)便于存儲和查找闻坚。不是線程安全類，但是如果多線程操作會報(bào)出ConCurrentxxxException兢孝。
下面按行數(shù)來說：
1.? 如果當(dāng)前Node[] 為null 或者 Node數(shù)組元素個數(shù)為0 執(zhí)行下面一行代碼（省略大括號）
2.? resize() 方法返回一個擴(kuò)容后的Node[],擴(kuò)容的機(jī)制為所需容量的兩倍窿凤，是原有的1.5倍，這個計(jì)算是由負(fù)載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 來決定的（具體的可以看一下resize()方法跨蟹，如果有困難我們再討論一次）雳殊。 Node數(shù)組元素個數(shù)n 賦值為擴(kuò)容后的長度。
4.? 「 (n - 1) & hash] 」定位數(shù)組下標(biāo)位置的經(jīng)典算法窗轩，你可以自己寫一個main方法來做幾個實(shí)驗(yàn)夯秃。n=16的話，計(jì)算結(jié)果肯定在0～15之間痢艺。p為計(jì)算后取到的一個Node節(jié)點(diǎn) 判斷是否為null (if else 省略大括號)
5.? 如果上述判斷為true仓洼，那么當(dāng)前節(jié)點(diǎn)賦值為一個新建節(jié)點(diǎn) newNode(x,x,x,x); 這個不用說吧。也是一個經(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í)行下列代碼（到這步的意思是喳整，不會是覆蓋操作谆构，當(dāng)前節(jié)點(diǎn)也不是treeNode，只能是將當(dāng)前節(jié)點(diǎn)拼接在列表末端）框都。
13-23. 這是一個看似無限循環(huán)的算法搬素，這有幾個退出點(diǎn)，按順序來，第一個break熬尺，代表找到了列表末端摸屠，把當(dāng)前元素添加到末端即可。第二個break粱哼，是找到新舊值覆蓋的元素季二，進(jìn)行替換。
14行為常規(guī)列表遍歷皂吮。
15行為如果找到最后一個元素了戒傻，直接新建元素，將最后一個元素與新元素邏輯關(guān)聯(lián)蜂筹。
16行 判斷當(dāng)前個數(shù)需纳，是否大于或者等于7，如果是艺挪，則將列表轉(zhuǎn)化為TreeBin包裝類不翩，其實(shí)列表轉(zhuǎn)樹的界限是8，但是數(shù)組下標(biāo)是從0開始麻裳，所以是TREEIFY_THRESHOLD - 1口蝠。
17行就是轉(zhuǎn)化方法了。
補(bǔ)充 1：jdk8之后津坑，hashmap中妙蔗，數(shù)據(jù)結(jié)構(gòu)是Node[]+（鏈表|樹），Node[]肯定是不會改變的了疆瑰，那什么時候用鏈表眉反，什么時候是樹呢？他們有個臨界點(diǎn)穆役，8寸五，這個數(shù)字我在回答里也說過，你在源碼里也能找到耿币。知道這個8了梳杏，我們看下怎么轉(zhuǎn)化的，首先淹接，數(shù)組中的一個元素十性，他是從鏈表就夠開始構(gòu)造的，也就是說塑悼，你連續(xù)put相同的(lenght-1)&hash的值劲适，當(dāng)個數(shù)小于8的時候，用的都是鏈表拢肆，也是就是node.next=new Node()形式减响，當(dāng)個數(shù)大于等8的時候，將鏈表轉(zhuǎn)化為TreeNode形式（在內(nèi)部TreeNode托管給TreebBin郭怪，TreeNode是紅黑樹結(jié)構(gòu)支示。），p instenceof NodeTree 就是用來判斷鄙才，當(dāng)前數(shù)組元素結(jié)構(gòu)颂鸿，是鏈表還是樹，如果返回時true攒庵，那么嘴纺，當(dāng)前元素下的結(jié)構(gòu)已經(jīng)是樹，就用樹的方式將當(dāng)前操作的對象加入到樹中浓冒，反之還是鏈表栽渴，將當(dāng)前操作的對象，加入到鏈表末尾稳懒，加入完成之后闲擦，判斷是否需要轉(zhuǎn)化為樹結(jié)構(gòu)，判斷條件是什么呢场梆，就是那個8墅冷。
補(bǔ)充 2: jdk8之后，初始化HashMap之后或油，他的容量size并不是16寞忿，初始化后的對象 是{},當(dāng)有寫操作進(jìn)行時，才會inittable 給他一個初始化容量1<<4,具體的請看源碼顶岸，如果不懂腔彰，歡迎留言一起討論。
補(bǔ)充 3： 有人說到底是看jdk7好還是8好蜕琴，我個人意見萍桌，以8為主，7也要看凌简，看他為什么這么優(yōu)化上炎，這么優(yōu)化的好處是什么，優(yōu)化的作者是如何想的雏搂，我想我們能把這種思想轉(zhuǎn)化為我們自己的藕施，jdk這種教科書也算是成功的。
