自己在簡(jiǎn)書上看了不少的別人總結(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)造方法
幾個(gè)基本量：
- capacity：容量，bucket數(shù)組長(zhǎng)度全陨，默認(rèn)長(zhǎng)度為16爆班；
- loadFactor：裝載因子，默認(rèn)值為0.75辱姨，它決定了bucket填充程度柿菩；
- threshold：決定了HashMap能夠放進(jìn)去的數(shù)據(jù)量。
對(duì)于threshold的初始化會(huì)調(diào)用tableSizeFor方法計(jì)算出一個(gè)比initialCapacity大的第一個(gè)2的n次冪的值存入threshold雨涛。
bucket的初始化一般都是在第一次調(diào)用put方法時(shí)完成的枢舶。
Hash
JDK 8 中在進(jìn)行g(shù)et和put操作時(shí)，會(huì)先根據(jù)key的hashCode進(jìn)行再散列替久，再進(jìn)行bucket對(duì)應(yīng)節(jié)點(diǎn)位置計(jì)算凉泄，請(qǐng)看以下示例：
可以看出：h >>> 16，高16位補(bǔ)0蚯根，由于任意數(shù)跟0異或不變后众，所以hash的作用就是高16位不變，低16位和高16位做異或運(yùn)算颅拦，來(lái)達(dá)到減少碰撞的目的蒂誉。
hash方法的實(shí)現(xiàn)：
為了提高碰撞下的性能，當(dāng)鏈表節(jié)點(diǎn)等于8時(shí)距帅，JDK8用紅黑樹代替鏈表右锨，將原有鏈表部分查詢的時(shí)間復(fù)雜度o(n)提升為o(logn)，繼續(xù)看JDK 8中的put方法的具體實(shí)現(xiàn)碌秸。
- put方法
- putVal
具體流程如下：
1.如果當(dāng)前bucket為空時(shí)绍移，調(diào)用resize（）方法初始化悄窃；
2.根據(jù)key的hash值計(jì)算出所在的bucket節(jié)點(diǎn)的位置；
3.如果沒(méi)有沖突蹂窖，也就是
p = tab[i = (n - 1) & hash]=null
調(diào)用newNode方法封裝key-value鍵值對(duì)轧抗，并將其掛到 bucket對(duì)應(yīng)位置下，否則恼策，跳轉(zhuǎn)到步驟4鸦致；
4.如果發(fā)生沖突
- 遍歷鏈表，如果該key已經(jīng)存在涣楷，則更新原有的oldValue為新的value分唾，并返回oldValue。直到鏈表末尾沒(méi)有相同的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)下鏈表長(zhǎng)度超過(guò)8秋柄，需要將原有的數(shù)據(jù)結(jié)構(gòu)鏈表變?yōu)閞btree益涧；
5.數(shù)據(jù)put完成之后锹杈，如果當(dāng)前數(shù)組長(zhǎng)度 > threshold，調(diào)用resize方法擴(kuò)容摔寨。
resize（）
resize的前半部分主要完成了新的capacity和threshold的計(jì)算去枷。從代碼實(shí)現(xiàn)可以看出，每一次擴(kuò)容是复，newCapacity和newThreshold均是擴(kuò)容前值的兩倍删顶，如此設(shè)計(jì)師為什么？先看個(gè)例子來(lái)說(shuō)明這樣子設(shè)計(jì)的原因：
從小例子可以看出淑廊，resize后逗余，key所在bucket的節(jié)點(diǎn)位置保持不變。首先季惩，table.length也就是capacity肯定是2的n次方录粱，根據(jù)所在bucket節(jié)點(diǎn)下標(biāo)計(jì)算公式：index = hash & (table.length - 1)，其實(shí)在進(jìn)行&運(yùn)算的時(shí)候蜀备，只是多了一個(gè)最高位1关摇，那么新位置要么保持原位置不變，要么在原位置 + oldCapacity碾阁，這個(gè)設(shè)計(jì)的巧妙就在于節(jié)省了一部分重新計(jì)算hash的時(shí)間，而且hash值高位出現(xiàn)0和1的概率均等些楣，在resize的過(guò)程又將節(jié)點(diǎn)平均分配到兩個(gè)bucket節(jié)點(diǎn)脂凶。
resize的后半部分對(duì)數(shù)據(jù)做了transfer宪睹，具體實(shí)現(xiàn)如下：
總結(jié)
HashMap在JDk1.8比JDK1.7的優(yōu)化主要在：
1.引入rbtree，在bucket節(jié)點(diǎn)下鏈表長(zhǎng)度 = 8時(shí)將鏈表變成rbtree蚕钦；
2.優(yōu)化hash和resize亭病，減少resize帶來(lái)的hash性能消耗。
