Java中HashMap底層實(shí)現(xiàn)原理(JDK1.8)源碼分析
這幾天學(xué)習(xí)了HashMap的底層實(shí)現(xiàn),但是發(fā)現(xiàn)好幾個(gè)版本的，代碼不一巍膘，而且看了Android包的HashMap和JDK中的HashMap的也不是一樣厂财，原來(lái)他們沒(méi)有指定JDK版本，很多文章都是舊版本JDK1.6.JDK1.7的∠啃福現(xiàn)在我來(lái)分析一哈最新的JDK1.8的HashMap及性能優(yōu)化璃饱。
在JDK1.6，JDK1.7中肪康，HashMap采用位桶+鏈表實(shí)現(xiàn)荚恶，即使用鏈表處理沖突，同一hash值的鏈表都存儲(chǔ)在一個(gè)鏈表里磷支。但是當(dāng)位于一個(gè)桶中的元素較多谒撼，即hash值相等的元素較多時(shí)，通過(guò)key值依次查找的效率較低雾狈。而JDK1.8中嗤栓，HashMap采用位桶+鏈表+紅黑樹實(shí)現(xiàn)，當(dāng)鏈表長(zhǎng)度超過(guò)閾值（8）時(shí)箍邮，將鏈表轉(zhuǎn)換為紅黑樹茉帅，這樣大大減少了查找時(shí)間。
簡(jiǎn)單說(shuō)下HashMap的實(shí)現(xiàn)原理：
首先有一個(gè)每個(gè)元素都是鏈表（可能表述不準(zhǔn)確）的數(shù)組锭弊，當(dāng)添加一個(gè)元素（key-value）時(shí)堪澎，就首先計(jì)算元素key的hash值，以此確定插入數(shù)組中的位置味滞，但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了樱蛤，這時(shí)就添加到同一hash值的元素的后面钮呀，他們?cè)跀?shù)組的同一位置，但是形成了鏈表昨凡，同一各鏈表上的Hash值是相同的爽醋，所以說(shuō)數(shù)組存放的是鏈表。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)時(shí)便脊，鏈表就轉(zhuǎn)換為紅黑樹蚂四，這樣大大提高了查找的效率。
當(dāng)鏈表數(shù)組的容量超過(guò)初始容量的0.75時(shí)哪痰，再散列將鏈表數(shù)組擴(kuò)大2倍遂赠，把原鏈表數(shù)組的搬移到新的數(shù)組中
即HashMap的原理圖是：
[圖片上傳失敗...(image-de36f7-1563526853522)]
一，JDK1.8中的涉及到的數(shù)據(jù)結(jié)構(gòu)
1晌杰，位桶數(shù)組
2跷睦，數(shù)組元素Node<K,V>實(shí)現(xiàn)了Entry接口
3，紅黑樹
二肋演，源碼中的數(shù)據(jù)域
加載因子（默認(rèn)0.75）：為什么需要使用加載因子抑诸，為什么需要擴(kuò)容呢？因?yàn)槿绻畛浔群艽蟮猓f(shuō)明利用的空間很多蜕乡，如果一直不進(jìn)行擴(kuò)容的話，鏈表就會(huì)越來(lái)越長(zhǎng)边灭，這樣查找的效率很低，因?yàn)殒湵淼拈L(zhǎng)度很大（當(dāng)然最新版本使用了紅黑樹后會(huì)改進(jìn)很多）健盒，擴(kuò)容之后绒瘦，將原來(lái)鏈表數(shù)組的每一個(gè)鏈表分成奇偶兩個(gè)子鏈表分別掛在新鏈表數(shù)組的散列位置，這樣就減少了每個(gè)鏈表的長(zhǎng)度扣癣，增加查找效率
HashMap本來(lái)是以空間換時(shí)間惰帽，所以填充比沒(méi)必要太大。但是填充比太小又會(huì)導(dǎo)致空間浪費(fèi)父虑。如果關(guān)注內(nèi)存该酗，填充比可以稍大，如果主要關(guān)注查找性能士嚎，填充比可以稍小呜魄。
三，HashMap的構(gòu)造函數(shù)
HashMap的構(gòu)造方法有4種莱衩，主要涉及到的參數(shù)有爵嗅，指定初始容量，指定填充比和用來(lái)初始化的Map
四笨蚁，HashMap的存取機(jī)制
1睹晒，HashMap如何getValue值趟庄，看源碼
get(key)方法時(shí)獲取key的hash值，計(jì)算hash&(n-1)得到在鏈表數(shù)組中的位置first=tab[hash&(n-1)],先判斷first的key是否與參數(shù)key相等伪很，不等就遍歷后面的鏈表找到相同的key值返回對(duì)應(yīng)的Value值即可
2戚啥，HashMap如何put(key，value);看源碼
下面簡(jiǎn)單說(shuō)下添加鍵值對(duì)put(key,value)的過(guò)程：
1锉试，判斷鍵值對(duì)數(shù)組tab[]是否為空或?yàn)閚ull猫十，否則以默認(rèn)大小resize()；
2键痛，根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i炫彩，如果tab[i]==null，直接新建節(jié)點(diǎn)添加絮短，否則轉(zhuǎn)入3
3江兢，判斷當(dāng)前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個(gè)節(jié)點(diǎn)類型即可),分別處理
五，HasMap的擴(kuò)容機(jī)制resize();
構(gòu)造hash表時(shí)丁频，如果不指明初始大小杉允，默認(rèn)大小為16（即Node數(shù)組大小16），如果Node[]數(shù)組中的元素達(dá)到（填充比Node.length）重新調(diào)整HashMap大小 變?yōu)樵瓉?lái)2倍大小,*擴(kuò)容很耗時(shí)
六席里，JDK1.8使用紅黑樹的改進(jìn)
在Java jdk8中對(duì)HashMap的源碼進(jìn)行了優(yōu)化叔磷，在jdk7中，HashMap處理“碰撞”的時(shí)候奖磁，都是采用鏈表來(lái)存儲(chǔ)改基，當(dāng)碰撞的結(jié)點(diǎn)很多時(shí)，查詢時(shí)間是O（n）咖为。
在jdk8中秕狰，HashMap處理“碰撞”增加了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)碰撞結(jié)點(diǎn)較少時(shí)躁染，采用鏈表存儲(chǔ)鸣哀，當(dāng)較大時(shí)（>8個(gè)），采用紅黑樹（特點(diǎn)是查詢時(shí)間是O（logn））存儲(chǔ)（有一個(gè)閥值控制吞彤，大于閥值(8個(gè))我衬，將鏈表存儲(chǔ)轉(zhuǎn)換成紅黑樹存儲(chǔ)）
[圖片上傳失敗...(image-11f4c6-1563526853522)]
問(wèn)題分析：
你可能還知道哈希碰撞會(huì)對(duì)hashMap的性能帶來(lái)災(zāi)難性的影響。如果多個(gè)hashCode()的值落到同一個(gè)桶內(nèi)的時(shí)候饰恕，這些值是存儲(chǔ)到一個(gè)鏈表中的挠羔。最壞的情況下，所有的key都映射到同一個(gè)桶中埋嵌，這樣hashmap就退化成了一個(gè)鏈表——查找時(shí)間從O(1)到O(n)褥赊。
隨著HashMap的大小的增長(zhǎng)，get()方法的開銷也越來(lái)越大莉恼。由于所有的記錄都在同一個(gè)桶里的超長(zhǎng)鏈表內(nèi)拌喉，平均查詢一條記錄就需要遍歷一半的列表速那。
JDK1.8HashMap的紅黑樹是這樣解決的：
**如果某個(gè)桶中的記錄過(guò)大的話（當(dāng)前是TREEIFY_THRESHOLD = 8），HashMap會(huì)動(dòng)態(tài)的使用一個(gè)專門的treemap實(shí)現(xiàn)來(lái)替換掉它尿背。這樣做的結(jié)果會(huì)更好端仰，是O(logn)，而不是糟糕的O(n)田藐。**
它是如何工作的荔烧？前面產(chǎn)生沖突的那些KEY對(duì)應(yīng)的記錄只是簡(jiǎn)單的追加到一個(gè)鏈表后面，這些記錄只能通過(guò)遍歷來(lái)進(jìn)行查找汽久。但是超過(guò)這個(gè)閾值后HashMap開始將列表升級(jí)成一個(gè)二叉樹鹤竭，**使用哈希值作為樹的分支變量，如果兩個(gè)哈希值不等景醇，但指向同一個(gè)桶的話臀稚，較大的那個(gè)會(huì)插入到右子樹里。如果哈希值相等三痰，HashMap希望key值最好是實(shí)現(xiàn)了Comparable接口的吧寺，這樣它可以按照順序來(lái)進(jìn)行插入**。這對(duì)HashMap的key來(lái)說(shuō)并不是必須的散劫，不過(guò)如果實(shí)現(xiàn)了當(dāng)然最好稚机。如果沒(méi)有實(shí)現(xiàn)這個(gè)接口，在出現(xiàn)嚴(yán)重的哈希碰撞的時(shí)候获搏，你就并別指望能獲得性能提升了赖条。
