引言
? ? ? ?基于Java集合框架圖，本文針對(duì)Map集合的主要實(shí)現(xiàn)類(lèi)從實(shí)現(xiàn)原理梢什、特點(diǎn)奠蹬、核心功能實(shí)現(xiàn)細(xì)節(jié)角度進(jìn)行分析總結(jié)，目的是深入的了解其性能特點(diǎn)和適應(yīng)場(chǎng)景嗡午，合理的優(yōu)化使用囤躁；學(xué)習(xí)它們的架構(gòu)設(shè)計(jì)思想和算法思想，編寫(xiě)更高效的代碼荔睹。
HashMap的結(jié)構(gòu)特點(diǎn)狸演？
? ? ? ?JDK中HashMap是一種將元素以Key-Value形式存儲(chǔ)的非線(xiàn)程安全、自動(dòng)擴(kuò)容的集合僻他。其特點(diǎn)是利用java對(duì)象的hashCode唯一性作為元素的key宵距，基于數(shù)組結(jié)構(gòu)，使用哈希函數(shù)（除留取余法吨拗，hash(key)%n满哪，n為數(shù)組長(zhǎng)度），將非固定長(zhǎng)度的key劝篷，映射為數(shù)組下標(biāo)哨鸭。進(jìn)而通過(guò)下標(biāo)位置存儲(chǔ)key對(duì)應(yīng)的哈希值value。
? ? ? ?可以說(shuō)沒(méi)有數(shù)組就沒(méi)有哈希表娇妓。HashMap中的HashTable存儲(chǔ)的元素是單鏈表爬范，利用單鏈表解決哈希沖突悉盆，HashMap的HashTable是一個(gè)單鏈表數(shù)組結(jié)構(gòu)簿盅。
HashMap的哈希存儲(chǔ)及查找原理皂吮？
? ? ? ?首先來(lái)看下HashMap的key的hash計(jì)算方法
? ? ? ?如圖，h>>>16將32位int值保留高16位，使用java對(duì)象hashCode異或操作，目的是使key值更隨機(jī)。
? ? ? ?然后锌云，看下put()方法的具體實(shí)現(xiàn)，在此之前先了解下吁脱，Node結(jié)點(diǎn)實(shí)現(xiàn)：HashMap內(nèi)部使用單鏈表來(lái)存儲(chǔ)元素宾抓，其中hash/key/value均為鏈表結(jié)點(diǎn)的數(shù)據(jù)屬性。而HashTable就是存儲(chǔ)單鏈表的數(shù)組豫喧。
其中627-628是在進(jìn)行擴(kuò)容判斷石洗，629判斷當(dāng)前結(jié)點(diǎn)不在hash表中，則創(chuàng)建結(jié)點(diǎn)放入HashTable中紧显。（其中 ??(n -1) &hash 等價(jià)于 hash%n 讲衫，n為HashTable長(zhǎng)度，利用二進(jìn)制按位&操作代替取余操作來(lái)提高在HashTable中定位元素的查找效率）孵班。如果當(dāng)前結(jié)點(diǎn)在HashTable中存在涉兽，則通過(guò)key原值比較，進(jìn)而判斷HashTable中存在的結(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)是否相同篙程，如果不是相同結(jié)點(diǎn)枷畏，此時(shí)發(fā)生哈希沖突，則將當(dāng)前結(jié)點(diǎn)也放入鏈表尾部即可虱饿。當(dāng)鏈表長(zhǎng)度大于規(guī)定閥值8時(shí)拥诡，JDK1.8將單鏈表轉(zhuǎn)換為紅黑樹(shù)存儲(chǔ)元素，從而避免極端情況下散列到HashTable一個(gè)桶內(nèi)氮发，造成單鏈表過(guò)長(zhǎng)性能退化渴肉。
HashMap的初始化及其擴(kuò)容機(jī)制？為什么每次擴(kuò)容為舊容量的2倍爽冕，而不是1.5倍或其他倍數(shù)呢仇祭？
? ? ? ?HashMap初始默認(rèn)容量為16，初始擴(kuò)容因子為0.75颈畸，初始化容量閥值=容量*擴(kuò)容因子乌奇，即16*0.75=12。
? ? ? ?擴(kuò)容邏輯是：插入元素后眯娱，容量是否超過(guò)當(dāng)前容量閥值礁苗。每次擴(kuò)容為原容量的2倍，并重新分配內(nèi)存困乒，對(duì)舊hash表中的數(shù)據(jù)寂屏，重新計(jì)算hash值贰谣，并遷移到新的hash表中娜搂。也就是說(shuō)當(dāng)HashMap采用默認(rèn)初始化后迁霎，新增元素超過(guò)12時(shí)，會(huì)進(jìn)行第一次擴(kuò)容百宇，擴(kuò)容后的容量為16*2考廉。之后每次都擴(kuò)容為原容量的2倍，也就是說(shuō)HashMap的容量始終是2的N次冪携御。
? ? ? ?HashMap定位和存儲(chǔ)元素在hash表中的位置都是通過(guò)hash(key)%n實(shí)現(xiàn)的（除留取余法）這種方式如果除數(shù)不是2的N次冪昌粤，則無(wú)法利用位&操作，散列函數(shù)性能會(huì)大打折扣啄刹。這正是HashMap每次擴(kuò)容為舊容量的2倍的原因涮坐。
? ? ? ?由于HashMap擴(kuò)容條件，會(huì)導(dǎo)致浪費(fèi)其自身%25的存儲(chǔ)空間誓军，以犧牲空間的代價(jià)來(lái)降低哈希沖突的概率袱讹，以此達(dá)到空間換性能的做法。如果一個(gè)容器存儲(chǔ)1萬(wàn)個(gè)元素昵时，則需要擴(kuò)容7次捷雕。那么如何降低擴(kuò)容的性能損耗呢？如果事先能夠預(yù)見(jiàn)數(shù)據(jù)量大小壹甥，可以指定容量的方式初始化固定容量的集合救巷，以此降低不必要的被動(dòng)擴(kuò)容性能損耗。
? ? ? ?下面對(duì)HashMap存儲(chǔ)1萬(wàn)個(gè)元素句柠，分別使用默認(rèn)構(gòu)造方法和指定容量（Capacity=10390浦译，不擴(kuò)容）方式構(gòu)造，進(jìn)行JMH吞吐量測(cè)試溯职。從下圖測(cè)試結(jié)果反饋管怠，第一條指定容量比第二條未指定容量，ops高出不少缸榄〔吵冢可見(jiàn)頻繁被動(dòng)擴(kuò)容性能消耗不小，指定容量減少擴(kuò)容可以提升性能甚带。
小結(jié)：
? ? ? ?HashMap基于數(shù)組支持按下標(biāo)隨機(jī)訪(fǎng)問(wèn)的特性她肯，利用除留取余的哈希算法，將key映射到數(shù)組下標(biāo)鹰贵，并將key對(duì)應(yīng)的value值存儲(chǔ)到下標(biāo)位置晴氨。HashMap采用鏈表法解決哈希沖突，同時(shí)引入紅黑樹(shù)優(yōu)化鏈表過(guò)長(zhǎng)導(dǎo)致的哈希碰撞攻擊碉输。通常情況下認(rèn)為HashMap的查詢(xún)籽前、插入和刪除操作的時(shí)間復(fù)雜度均為O(1)，適合快速精確無(wú)序查找的場(chǎng)景。
LinkedHashMap特點(diǎn)枝哄？為什么散列表經(jīng)常和鏈表一起使用肄梨？
? ? ? ?LinkedHashMap是通過(guò)雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的。LinkedList中的“Linked”實(shí)際上不僅僅指它是通過(guò)鏈表法來(lái)解決哈希沖突的挠锥，它還指雙向鏈表實(shí)現(xiàn)的緩沖LRU策略众羡，使HashMap支持按插入順序或操作順序遍歷的含義。
? ? ? ? 雖然散列表作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)其插入蓖租、刪除粱侣、查找操作的性能較高，但散列表中的數(shù)據(jù)都是通過(guò)散列函數(shù)之后蓖宦，無(wú)序存儲(chǔ)的齐婴。也就是說(shuō)它不支持按某種順序查找元素，為了使其有序遍歷稠茂。每次遍歷都要先排序的話(huà)尔店，那效率勢(shì)必會(huì)很低。為了解決這個(gè)問(wèn)題主慰，通常將散列表和鏈表（或者跳表）一起使用嚣州。
