自己在簡書上看了不少的別人總結(jié)，那么在借鑒前人（miaoLoveCode）基礎(chǔ)上自己再總結(jié)一番。
HashMap1.8實(shí)現(xiàn)分析
數(shù)據(jù)結(jié)構(gòu)
1.8的HashMap數(shù)據(jù)結(jié)構(gòu)是由數(shù)組+（鏈表或紅黑樹）實(shí)現(xiàn)。
構(gòu)造方法
幾個基本量：
- capacity：容量，bucket數(shù)組長度，默認(rèn)長度為16；
- loadFactor：裝載因子，默認(rèn)值為0.75，它決定了bucket填充程度；
- threshold：決定了HashMap能夠放進(jìn)去的數(shù)據(jù)量。
對于threshold的初始化會調(diào)用tableSizeFor方法計算出一個比initialCapacity大的第一個2的n次冪的值存入threshold。
bucket的初始化一般都是在第一次調(diào)用put方法時完成的。
Hash
JDK 8 中在進(jìn)行g(shù)et和put操作時，會先根據(jù)key的hashCode進(jìn)行再散列，再進(jìn)行bucket對應(yīng)節(jié)點(diǎn)位置計算，請看以下示例：
可以看出：h >>> 16，高16位補(bǔ)0，由于任意數(shù)跟0異或不變，所以hash的作用就是高16位不變，低16位和高16位做異或運(yùn)算，來達(dá)到減少碰撞的目的。
hash方法的實(shí)現(xiàn)：
為了提高碰撞下的性能，當(dāng)鏈表節(jié)點(diǎn)等于8時，JDK8用紅黑樹代替鏈表，將原有鏈表部分查詢的時間復(fù)雜度o(n)提升為o(logn)，繼續(xù)看JDK 8中的put方法的具體實(shí)現(xiàn)。
- put方法
- putVal
具體流程如下：
1.如果當(dāng)前bucket為空時，調(diào)用resize（）方法初始化；
2.根據(jù)key的hash值計算出所在的bucket節(jié)點(diǎn)的位置；
3.如果沒有沖突，也就是
p = tab[i = (n - 1) & hash]=null
調(diào)用newNode方法封裝key-value鍵值對，并將其掛到 bucket對應(yīng)位置下，否則，跳轉(zhuǎn)到步驟4；
4.如果發(fā)生沖突
- 遍歷鏈表，如果該key已經(jīng)存在，則更新原有的oldValue為新的value，并返回oldValue。直到鏈表末尾沒有相同的key的hash值和key（equals，==），則在末尾插入新節(jié)點(diǎn)；
- 如果key所在的節(jié)點(diǎn)為treeNode，調(diào)用rbtree（紅黑樹）的putTreeVal方法將改節(jié)點(diǎn)掛到rbtree上；
- 如果插入節(jié)點(diǎn)后，當(dāng)前bucket節(jié)點(diǎn)下鏈表長度超過8，需要將原有的數(shù)據(jù)結(jié)構(gòu)鏈表變?yōu)閞btree；
5.數(shù)據(jù)put完成之后，如果當(dāng)前數(shù)組長度 > threshold，調(diào)用resize方法擴(kuò)容。
resize（）
resize的前半部分主要完成了新的capacity和threshold的計算。從代碼實(shí)現(xiàn)可以看出，每一次擴(kuò)容，newCapacity和newThreshold均是擴(kuò)容前值的兩倍，如此設(shè)計師為什么？先看個例子來說明這樣子設(shè)計的原因：
從小例子可以看出，resize后，key所在bucket的節(jié)點(diǎn)位置保持不變。首先，table.length也就是capacity肯定是2的n次方，根據(jù)所在bucket節(jié)點(diǎn)下標(biāo)計算公式：index = hash & (table.length - 1)，其實(shí)在進(jìn)行&運(yùn)算的時候，只是多了一個最高位1，那么新位置要么保持原位置不變，要么在原位置 + oldCapacity，這個設(shè)計的巧妙就在于節(jié)省了一部分重新計算hash的時間，而且hash值高位出現(xiàn)0和1的概率均等，在resize的過程又將節(jié)點(diǎn)平均分配到兩個bucket節(jié)點(diǎn)。
resize的后半部分對數(shù)據(jù)做了transfer，具體實(shí)現(xiàn)如下：
總結(jié)
HashMap在JDk1.8比JDK1.7的優(yōu)化主要在：
1.引入rbtree，在bucket節(jié)點(diǎn)下鏈表長度 = 8時將鏈表變成rbtree；
2.優(yōu)化hash和resize，減少resize帶來的hash性能消耗。
