小茵：今天來講講Map吧限番，你對Map了解多少姻乓？
小奧：Map在Java里邊是一個(gè)接口蕉拢，常見的實(shí)現(xiàn)類有HashMap、LinkedHashMap刻两、TreeMap和ConcurrentHashMap
小奧：在Java里邊增蹭，哈希表的結(jié)構(gòu)是數(shù)組+鏈表的方式。
小奧：HashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表/紅黑樹
小奧：LinkedHashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表/紅黑樹+雙向鏈表
小奧：TreeMap底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹
小奧：而ConcurrentHashMap底層數(shù)據(jù)結(jié)構(gòu)也是數(shù)組+鏈表/紅黑樹
小茵：我們先以HashMap開始吧磅摹，你能講講當(dāng)你new一個(gè)HashMap的時(shí)候沪铭，會(huì)發(fā)生什么嗎？
小奧：HashMap有幾個(gè)構(gòu)造方法偏瓤，但最主要的就是指定初始值大小和負(fù)載因子的大小杀怠。
小奧：如果我們不指定，默認(rèn)HashMap的大小為16厅克，負(fù)載因子的大小為0.75
小奧：HashMap的大小只能是2次冪的赔退，假設(shè)你傳一個(gè)10進(jìn)去，實(shí)際上最終HashMap的大小是16证舟，你傳一個(gè)7進(jìn)去硕旗，HashMap最終的大小是8，具體的實(shí)現(xiàn)在tableSizeFor可以看到女责。
小奧：我們把元素放進(jìn)HashMap的時(shí)候漆枚，需要算出這個(gè)元素所在的位置（hash）。
小奧：在HashMap里用的是位運(yùn)算來代替取模抵知，能夠更加高效地算出該元素所在的位置墙基。
小奧：為什么HashMap的大小只能是2次冪，因?yàn)橹挥写笮?次冪時(shí)刷喜，才能合理用位運(yùn)算替代取模残制。
小奧：而負(fù)載因子的大小決定著哈希表的擴(kuò)容和哈希沖突。
小奧：比如現(xiàn)在我默認(rèn)的HashMap大小為16掖疮，負(fù)載因子為0.75初茶，這意味著數(shù)組最多只能放12個(gè)元素，一旦超過12個(gè)元素浊闪，則哈希表需要擴(kuò)容恼布。
小奧：怎么算出是12呢？很簡單搁宾，就是16*0.75折汞。每次put元素進(jìn)去的時(shí)候，都會(huì)檢查HashMap的大小有沒有超過這個(gè)閾值猛铅，如果有字支，則需要擴(kuò)容。
小奧：鑒于上面的說法（HashMap的大小只能是2次冪），所以擴(kuò)容的時(shí)候時(shí)候默認(rèn)是擴(kuò)原來的2倍
小奧：擴(kuò)容這個(gè)操作肯定是耗時(shí)的堕伪，那能不能把負(fù)載因子調(diào)高一點(diǎn)揖庄，比如我要調(diào)至為1，那我的HashMap就等到16個(gè)元素的時(shí)候才擴(kuò)容呢欠雌。
小奧：是可以的蹄梢，但是不推薦。負(fù)載因子調(diào)高了富俄，這意味著哈希沖突的概率會(huì)增高禁炒，哈希沖突概率增高，同樣會(huì)耗時(shí)（因?yàn)椴檎业乃俣茸兟耍?/p>
小茵：那我想問下霍比，在put元素的時(shí)候幕袱，傳遞的Key是怎么算哈希值的？
小奧：實(shí)現(xiàn)就在hash方法上悠瞬，可以發(fā)現(xiàn)的是们豌，它是先算出正常的哈希值，然后與高16位做異或運(yùn)算浅妆，產(chǎn)生最終的哈希值望迎。
小奧：這樣做的好處可以增加了隨機(jī)性，減少了碰撞沖突的可能性凌外。
小茵：了解辩尊，你簡單再說下put和get方法的實(shí)現(xiàn)吧
小奧：在put的時(shí)候，首先對key做hash運(yùn)算康辑，計(jì)算出該key所在的index摄欲。
小奧：如果沒碰撞，直接放到數(shù)組中晾捏，如果碰撞了蒿涎，需要判斷目前數(shù)據(jù)結(jié)構(gòu)是鏈表還是紅黑樹哀托，根據(jù)不同的情況來進(jìn)行插入惦辛。
小奧：假設(shè)key是相同的，則替換到原來的值仓手。最后判斷哈希表是否滿了(當(dāng)前哈希表大小*負(fù)載因子）胖齐，如果滿了，則擴(kuò)容
小奧：在get的時(shí)候嗽冒，還是對key做hash運(yùn)算呀伙，計(jì)算出該key所在的index，然后判斷是否有hash沖突
小奧：假設(shè)沒有沖突直接返回添坊，假設(shè)有沖突則判斷當(dāng)前數(shù)據(jù)結(jié)構(gòu)是鏈表還是紅黑樹剿另，分別從不同的數(shù)據(jù)結(jié)構(gòu)中取出。
小茵：那在HashMap中是怎么判斷一個(gè)元素是否相同的呢？
小奧：首先會(huì)比較hash值雨女，隨后會(huì)用==運(yùn)算符和equals()來判斷該元素是否相同谚攒。
小奧：說白了就是：如果只有hash值相同，那說明該元素哈希沖突了氛堕，如果hash值和equals() || == 都相同馏臭，那說明該元素是同一個(gè)。
小茵：你說HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表/紅黑樹讼稚，那什么情況拿下才會(huì)用到紅黑樹呢括儒？
小奧：當(dāng)數(shù)組的大小大于64且鏈表的大小大于8的時(shí)候才會(huì)將鏈表改為紅黑樹，當(dāng)紅黑樹大小為6時(shí)锐想，會(huì)退化為鏈表帮寻。
小奧：這里轉(zhuǎn)紅黑樹退化為鏈表的操作主要出于查詢和插入時(shí)對性能的考量。
小奧：鏈表查詢時(shí)間復(fù)雜度O(N)赠摇，插入時(shí)間復(fù)雜度O(1)规婆，紅黑樹查詢和插入時(shí)間復(fù)雜度O(logN)
小茵：你在日常開始中LinkedHashMap用的多嗎？
小奧：其實(shí)在日常開發(fā)中LinkedHashMap用得不多蝉稳。
小奧：在前面也提到了抒蚜，LinkedHashMap底層結(jié)構(gòu)是數(shù)組+鏈表+雙向鏈表，實(shí)際上它繼承了HashMap耘戚，在HashMap的基礎(chǔ)上維護(hù)了一個(gè)雙向鏈表嗡髓。
小奧：有了這個(gè)雙向鏈表，我們的插入可以是有序的收津，這里的有序不是指大小有序饿这，而是插入有序。
小奧：LinkedHashMap在遍歷的時(shí)候?qū)嶋H用的是雙向鏈表來遍歷的撞秋，所以LinkedHashMap的大小不會(huì)影響到遍歷的性能
小茵：那TreeMap呢长捧？
小奧：TreeMap在現(xiàn)實(shí)開發(fā)中用得也不多，TreeMap的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹
小奧：TreeMap的key不能為null（如果為null吻贿，那還怎么排序呢）串结，TreeMap有序是通過Comparator來進(jìn)行比較的，如果comparator為null舅列，那么就使用自然順序
小茵：再來講講線程安全的Map吧肌割？HashMap是線程安全的嗎？
小奧：HashMap不是線程安全的帐要，在多線程環(huán)境下把敞，HashMap有可能會(huì)有數(shù)據(jù)丟失和獲取不了最新數(shù)據(jù)的問題，比如說：線程Aput進(jìn)去了榨惠，線程Bget不出來奋早。
小奧：我們想要線程安全盛霎，可以使用ConcurrentHashMap
小奧：ConcurrentHashMap是線程安全的Map實(shí)現(xiàn)類，它在juc包下的耽装。
小奧：線程安全的Map實(shí)現(xiàn)類除了ConcurrentHashMap還有一個(gè)叫做Hashtable摩渺。
小奧：當(dāng)然了，也可以使用Collections來包裝出一個(gè)線程安全的Map剂邮。
小奧：但無論是Hashtable還是Collections包裝出來的都比較低效（因?yàn)槭侵苯釉谕鈱犹譻ynchronize）摇幻，所以我們一般有線程安全問題考量的，都使用ConcurrentHashMap
小奧：ConcurrentHashMap的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表/紅黑樹挥萌，它能支持高并發(fā)的訪問和更新绰姻，是線程安全的。
小奧：ConcurrentHashMap通過在部分加鎖和利用CAS算法來實(shí)現(xiàn)同步引瀑，在get的時(shí)候沒有加鎖狂芋，Node都用了volatile給修飾。
小奧：在擴(kuò)容時(shí)憨栽，會(huì)給每個(gè)線程分配對應(yīng)的區(qū)間帜矾，并且為了防止putVal導(dǎo)致數(shù)據(jù)不一致，會(huì)給線程的所負(fù)責(zé)的區(qū)間加鎖
小茵：你能給我講講JDK 7 和JDK8中HashMap和ConcurrentHashMap的區(qū)別嗎屑柔？
小奧：不能屡萤，我不會(huì)
小奧：我在學(xué)習(xí)的時(shí)候也看過JDK7的HashMap和ConcurrentHashMap，其實(shí)還是有很多不一樣的地方
候選者 比如JDK 7 的HashMap在擴(kuò)容時(shí)是頭插法掸宛，在JDK8就變成了尾插法死陆，在JDK7 的HashMap還沒有引入紅黑樹….
小奧：ConcurrentHashMap 在JDK7 還是使用分段鎖的方式來實(shí)現(xiàn)，而JDK 8 就又不一樣了唧瘾。但JDK 7細(xì)節(jié)我大多數(shù)都忘了棕硫。
小奧：我就沒用過JDK 7的API岸裙，我想著現(xiàn)在最低應(yīng)該也是用JDK8了吧枉层？所以我就沒去仔細(xì)看了贰拿。
小茵：嗯...
