HashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 單向鏈表 + 紅黑樹(shù)
HashMap底層數(shù)據(jù)結(jié)構(gòu).png
一、相關(guān)概念
1循集、Hash沖突：就是在一個(gè)數(shù)組的位置上出現(xiàn)了一個(gè)鏈表唇敞，這就是所謂的hash沖突。
2咒彤、解決hash沖突疆柔，就是讓鏈表的長(zhǎng)度變短，或者干脆就是不產(chǎn)生鏈表镶柱，一個(gè)好的hash算法應(yīng)該是讓數(shù)據(jù)很好的散列到數(shù)組的各個(gè)位置旷档，
即一個(gè)位置存一個(gè)數(shù)據(jù)就是最好的散列，下面說(shuō)的鏈地址法歇拆，說(shuō)的就是在hashmap里面沖突的時(shí)候故觅，一個(gè)節(jié)點(diǎn)可以存多個(gè)數(shù)據(jù)。
3躲查、桶(bucket)：數(shù)組中的每一個(gè)元素的位置就是一個(gè)桶。
4、HashMap的初始容量：16腌乡，并且 HashMap的底層數(shù)組長(zhǎng)度總是2的n次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
HashMap的最大容量：2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
5、 HashMap的加載因子是：0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
如果負(fù)載因子越大影所，對(duì)空間的利用更充分勺阐，然而后果是查找效率的降低；
如果負(fù)載因子太小愤估，那么散列表的數(shù)據(jù)將過(guò)于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)荔棉。系統(tǒng)默認(rèn)負(fù)載因子為0.75壹若，一般情況下我們是無(wú)需修改的店展。
6养篓、將鏈表轉(zhuǎn)為紅黑樹(shù)設(shè)置的鏈表長(zhǎng)度的閾值：8
static final int TREEIFY_THRESHOLD = 8;
7、 從源碼中可以看出赂蕴，每次新建一個(gè)HashMap時(shí)柳弄，都會(huì)初始化一個(gè)table數(shù)組。table數(shù)組的元素為Node節(jié)點(diǎn)概说。
Node為HashMap的內(nèi)部類(lèi)决左，它包含了鍵key懊缺、值value、下一個(gè)節(jié)點(diǎn)next，以及hash值幻锁，正是由于Node才構(gòu)成了table數(shù)組的項(xiàng)為鏈表蝙寨。
8辽幌、創(chuàng)建一個(gè)Node類(lèi)型的數(shù)組巡社，transient 意思是不能序列化
transient Node<K,V>[] table;
二、計(jì)算key在數(shù)組中的位置
1奋构、獲取key的hash值
(h = key.hashCode()) ^ (h >>> 16)
● 通過(guò)hashCode方法獲取到key的hash值骨田，然后把hash值的低16位與高16位進(jìn)行異或運(yùn)算得到的值即為該key的hash值
● 原因：
因?yàn)楹竺嬉褂?(n - 1) & hash，所以通過(guò)hashCode方法獲取的hash值不同也可能數(shù)組下標(biāo)相同声怔。為了降低運(yùn)算結(jié)果值的相同概率态贤，
使table數(shù)據(jù)分布均勻，減少碰撞
2醋火、計(jì)算key在數(shù)組中的位置 【n是數(shù)組的容量悠汽，即長(zhǎng)度】
①、對(duì)于HashMap的table數(shù)組而言芥驳，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素柿冲，這樣就可以直接找到），不能太緊也不能太松兆旬，
太緊會(huì)導(dǎo)致查詢速度慢假抄，太松則浪費(fèi)空間。
②、計(jì)算hash值后宿饱，怎么才能保證table數(shù)組中元素分布均與呢熏瞄？我們會(huì)想到取模，但是由于取模的消耗較大谬以，
HashMap是這樣處理的：采用按位與運(yùn)算强饮，即 (n - 1) & hash，效率高为黎，可以均勻分布table數(shù)據(jù)和充分利用空間邮丰。
③、原因：
● (n - 1) & hash 與 hash % n 是等值不等效 铭乾， (n - 1) & hash 的效率高于 hash % n 剪廉，這是HashMap在速度上的一個(gè)優(yōu)化。
● 按位取與炕檩，作用上相當(dāng)于取模mod或者取余%妈经。
★ 為什么 HashMap的底層數(shù)組長(zhǎng)度總是2的n次方？
● 數(shù)組的默認(rèn)長(zhǎng)度是16捧书，用二進(jìn)制表示為： 10000
(n - 1) 即 (16 - 1) , 用二進(jìn)制表示為：01111
因?yàn)閿?shù)組長(zhǎng)度總是2的n次方，所以如果擴(kuò)容一次之后骤星，數(shù)組的長(zhǎng)度為32经瓷，用二進(jìn)制表示為：100000
擴(kuò)容一次后，(n - 1) 即 (32 - 1)洞难，用二進(jìn)制表示為： 011111
然后使用(n - 1) 與 key的 hash 進(jìn)行 & 操作舆吮，結(jié)果是由key的hash值決定的(hash值是一個(gè)整型)
● 如果數(shù)組的長(zhǎng)度不是2的n次方，假如數(shù)組的長(zhǎng)度為15 队贱，則用二進(jìn)制表示為：011111
則 (n - 1) 即 (15 - 1) , 用二進(jìn)制表示為：011110
然后使用(n - 1) 與 key的 hash 進(jìn)行 & 操作色冀，因?yàn)閿?shù)組長(zhǎng)度不是2的n次冪，所以 (n - 1) 轉(zhuǎn)換為二進(jìn)制最后一位永遠(yuǎn)都是0 柱嫌，
& 的結(jié)果不能只由key的hash值決定的(hash值是一個(gè)整型)锋恬，所以空間減少，產(chǎn)生hash碰撞的概率就高
例如數(shù)組長(zhǎng)度為9编丘，hash值為3与学，計(jì)算其在數(shù)組上的位置為： 3 & (9 - 1) = 0 --> 0011 & 1000 = 0
數(shù)組長(zhǎng)度為9，hash值為2嘉抓，計(jì)算其在數(shù)組上的位置為：2 & (9 - 1) = 0 --> 0010 & 1000 = 0 在數(shù)組的相同位置上索守，發(fā)生碰撞；
例如數(shù)組長(zhǎng)度為8抑片，hash值為3卵佛，計(jì)算其在數(shù)組上的位置為：3 & (8 - 1) = 3 --> 0011 & 0111 = 0011
數(shù)組長(zhǎng)度為8，hash值為2，計(jì)算其在數(shù)組上的位置為：2 & (8 - 1) = 2 --> 0010 & 0111 = 0010 不同位置上截汪，不碰撞疾牲；
▲ 總結(jié)：數(shù)組的長(zhǎng)度必須是2的n次冪，當(dāng)length = 2^n時(shí)挫鸽，不同的hash值發(fā)生碰撞的概率比較小说敏，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻，
查詢速度也較快丢郊。
三盔沫、HashMap的put方法執(zhí)行過(guò)程可以通過(guò)下圖來(lái)理解：
HashMap的put方法.png
①、調(diào)用put方法枫匾，首先判斷數(shù)組table是否為null或數(shù)組的長(zhǎng)度是否為0架诞，如果是，就執(zhí)行resize()進(jìn)行擴(kuò)容干茉，轉(zhuǎn)向②谴忧，如果不是，轉(zhuǎn)向②角虫；
②.根據(jù)鍵key計(jì)算hash值得到插入的數(shù)組索引i沾谓，如果table[i]==null，直接新建節(jié)點(diǎn)添加戳鹅，轉(zhuǎn)向⑥均驶，如果table[i]不為空，轉(zhuǎn)向③枫虏；
③.判斷table[i]位置的key是否和要添加的key相同(通過(guò)hashCode以及equals進(jìn)行比較)妇穴，如果相同直接覆蓋舊的value，添加新value隶债，
并返回舊的value腾它，否則轉(zhuǎn)向⑥，死讹，如果不同瞒滴，轉(zhuǎn)向④；
④.判斷table[i] 是否 instanceof TreeNode赞警，即table[i] 是否是紅黑樹(shù)逛腿，如果是紅黑樹(shù)，則直接在樹(shù)中插入鍵值對(duì)仅颇，轉(zhuǎn)向⑥单默，否則轉(zhuǎn)向⑤；
⑤忘瓦、遍歷table[i]位置的鏈表搁廓，判斷鏈表長(zhǎng)度是否大于8引颈，大于8的話把鏈表轉(zhuǎn)換為紅黑樹(shù)，在紅黑樹(shù)中執(zhí)行插入操作境蜕，否則進(jìn)行鏈表的插入操作蝙场；
遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥.插入成功后粱年，數(shù)組長(zhǎng)度加1售滤，然后判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超過(guò)了臨界值threshold(數(shù)組容量 * 加載因子)，如果超過(guò)台诗，進(jìn)行擴(kuò)容完箩。
四、HashMap的resize方法執(zhí)行過(guò)程：
★ resize()方法的作用：
初始化數(shù)組Node拉队；
對(duì)數(shù)組進(jìn)行擴(kuò)容
①弊知、獲取原來(lái)數(shù)組的長(zhǎng)度oldCap(oldCapacity)，進(jìn)行判斷：
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
②粱快、如果數(shù)組長(zhǎng)度oldCap > 0秩彤，判斷數(shù)組長(zhǎng)度oldCap是否 > 數(shù)組長(zhǎng)度的最大值(2的30次方)，如果大于事哭，則不進(jìn)行擴(kuò)容漫雷，返回原來(lái)的數(shù)組oldTab；
否則判斷 oldCap << 1是否大于數(shù)組長(zhǎng)度的最大值(2的30次方) 并且 oldCap是否 > 數(shù)組長(zhǎng)度的最大值(2的30次方) 鳍咱，
如果不大于降盹，則進(jìn)行擴(kuò)容，即擴(kuò)容后的數(shù)組長(zhǎng)度為原來(lái)數(shù)組長(zhǎng)度的2倍流炕，臨界值threshold也要左移1位，擴(kuò)大到原來(lái)的2倍
③仅胞、如果數(shù)組長(zhǎng)度oldCap <= 0每辟，則對(duì)數(shù)組進(jìn)行初始化操作，數(shù)組默認(rèn)長(zhǎng)度為16干旧，臨界值threshold(數(shù)組容量 * 加載因子)為12(16*0.75)渠欺；
newCap = DEFAULT_INITIAL_CAPACITY
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
④、創(chuàng)建新數(shù)組newTab椎眯，數(shù)組容量為擴(kuò)容后的挠将，即舊數(shù)組容量的2倍
⑤、判斷舊數(shù)組是否使null编整，如果不是舔稀，則遍歷舊數(shù)組，如果oldTab[i] 掌测！= null内贮，則把oldTab[i] = null 【把舊數(shù)組oldTab[i] 置空】
● 判斷oldTab[i] 下面是不是null [即 e.next == null]，如果不存在，則重新計(jì)算oldTab[i] 在新數(shù)組中的位置
● 判斷oldTab[i] 下面是一個(gè)紅黑樹(shù)夜郁，則把該紅黑樹(shù)進(jìn)行split(分割)什燕，然后重新計(jì)算在新數(shù)組中的位置
● 判斷oldTab[i] 下面是一個(gè)鏈表(該鏈表的長(zhǎng)度不會(huì)超過(guò)8)，則進(jìn)行循環(huán)遍歷竞端，新數(shù)組中元素的位置只可能在兩個(gè)地方屎即，
一個(gè)是原下標(biāo)的位置，另一個(gè)是下標(biāo)為 [原下標(biāo) + 原容量] 的位置
● 如果 (e.hash & oldCap) == 0事富，則新數(shù)組中元素的位置在原下標(biāo)的位置
● 如果 (e.hash & oldCap) != 0技俐，則新數(shù)組中元素的位置在下標(biāo)為 [原下標(biāo) + 原容量] 的位置
⑥、返回新數(shù)組newTab
