HashMap是java面試中常被問到的一個(gè)數(shù)據(jù)類型蹂安，因?yàn)檫@個(gè)問題可以追問的很深，而且常用的HashSet底層也是HashMap實(shí)現(xiàn)的彰阴，所以作為java程序員有必要了解多一點(diǎn)瘾敢，而且有時(shí)候面試官和你聊到HashMap時(shí)，可能因?yàn)樽约簺]有系統(tǒng)的了解過尿这，有些觀點(diǎn)邏輯自己是對(duì)的簇抵，可能也會(huì)沒有太多的底氣堅(jiān)持自己的觀點(diǎn)，比如put操作的邏輯有些博客寫的不全射众，所以這邊推薦一篇比較專業(yè)的文章給大家碟摆，之前在ImportNew看過一篇介紹的文章有點(diǎn)細(xì)節(jié)有問題，所以建議好好看和理解美團(tuán)點(diǎn)評(píng)發(fā)布的這篇文章叨橱，介紹的比較全典蜕。
美團(tuán)的博客：Java 8系列之重新認(rèn)識(shí)HashMap
2021.7.27新補(bǔ)充一點(diǎn)：
1.對(duì)照源碼發(fā)現(xiàn)，美團(tuán)博客中第五步說明有誤罗洗，之前超鏈接已經(jīng)404了愉舔，已鏈接到新的地址
根據(jù)源碼我們發(fā)現(xiàn)正確的第五步：
遍歷table[i]，如果key存在伙菜，跳出循環(huán)后將該鏈表節(jié)點(diǎn)值覆蓋轩缤；如果key不存在，則直接添加新的鏈表節(jié)點(diǎn)并判斷之前鏈表長度是否大于等于8，如果是則將鏈表轉(zhuǎn)換為紅黑樹典奉；（圖片流程也需要注意對(duì)應(yīng)第五步的細(xì)節(jié)錯(cuò)誤）
else if (p instanceof TreeNode)
//步驟四
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//步驟五
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//5.2key不存在躺翻，插入鏈表節(jié)點(diǎn)丧叽，并判斷插入后鏈表size
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; //5.1key存在卫玖，遍歷的時(shí)候不操作，跳出循環(huán)覆蓋節(jié)點(diǎn)value即可
p = e;
}
}
簡單總結(jié)：
- Jdk7和Jdk8的區(qū)別：
1.Jdk8引入了紅黑樹的結(jié)構(gòu)（當(dāng)鏈表元素達(dá)到八個(gè)的時(shí)候踊淳，鏈表結(jié)構(gòu)轉(zhuǎn)紅黑樹結(jié)構(gòu)）
2.擴(kuò)容的時(shí)候也進(jìn)行了優(yōu)化 - 存儲(chǔ)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹（Jdk8引入）
- HashMap可以存儲(chǔ)null假瞬，根據(jù)源碼可知：key為null會(huì)放在數(shù)組的最前面，hash的結(jié)果為0迂尝。
-
put的流程：
流程圖
①.判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull脱茉，否則執(zhí)行resize()進(jìn)行擴(kuò)容；
②.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i垄开，如果table[i]==null琴许，直接新建節(jié)點(diǎn)添加，轉(zhuǎn)向⑥溉躲，如果table[i]不為空榜田，轉(zhuǎn)向③；
③.判斷table[i]的首個(gè)元素是否和key一樣锻梳，如果相同直接覆蓋value箭券，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals疑枯；
④.判斷table[i] 是否為treeNode辩块，即table[i] 是否是紅黑樹，如果是紅黑樹荆永，則直接在樹中插入鍵值對(duì)废亭，否則轉(zhuǎn)向⑤；
⑤.遍歷table[i]具钥，判斷鏈表長度是否大于8滔以，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作氓拼，否則進(jìn)行鏈表的插入操作你画；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥.插入成功后桃漾，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold坏匪，如果超過，進(jìn)行擴(kuò)容撬统。
