面試現(xiàn)場
程序員：我以前在哪里哪里當(dāng)?shù)漠a(chǎn)品經(jīng)理， 項(xiàng)目經(jīng)理? ?
程序員：“Map在Java里邊是一個接口，常見的實(shí)現(xiàn)類有HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap”
程序員：“首先要明確的是：在Java里邊，哈希表的結(jié)構(gòu)是數(shù)組+鏈表的方式。HashMap底層數(shù)據(jù)機(jī)構(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一個HashMap的時候，會發(fā)生什么嗎？”
程序員：“HashMap有幾個構(gòu)造方法，但最主要的就是指定初始值大小和負(fù)載因子的大小。如果我們不指定，默認(rèn)HashMap的大小為16，負(fù)載因子的大小為0.75”
程序員：“HashMap的大小只能是2次冪的，假設(shè)你傳一個10進(jìn)去，實(shí)際上最終HashMap的大小是16，你傳一個7進(jìn)去，HashMap最終的大小是8，具體的實(shí)現(xiàn)在tableSizeFor可以看到。我們把元素放進(jìn)HashMap的時候，需要算出這個元素所在的位置（hash）。在HashMap里用的是位運(yùn)算來代替取模，能夠更加高效地算出該元素所在的位置。為什么HashMap的大小只能是2次冪，因?yàn)橹挥写笮?次冪時，才能合理用位運(yùn)算替代取模。”
程序員：“而負(fù)載因子的大小決定著哈希表的擴(kuò)容和哈希沖突。比如現(xiàn)在我默認(rèn)的HashMap大小為16，負(fù)載因子為0.75，這意味著數(shù)組最多只能放12個元素，一旦超過12個元素，則哈希表需要擴(kuò)容。怎么算出是12呢？很簡單，就是16*0.75。每次put元素進(jìn)去的時候，都會檢查HashMap的大小有沒有超過這個閾值，如果有，則需要擴(kuò)容?！?/p>
程序員：“鑒于上面的說法（HashMap的大小只能是2次冪），所以擴(kuò)容的時候時候默認(rèn)是擴(kuò)原來的2倍”
程序員：“顯然擴(kuò)容這個操作肯定是耗時的，那我能不能把負(fù)載因子調(diào)高一點(diǎn)，比如我要調(diào)至為1，那我的HashMap就等到16個元素的時候才擴(kuò)容呢。顯然是可以的，但是不推薦。負(fù)載因子調(diào)高了，這意味著哈希沖突的概率會增高，哈希沖突概率增高，同樣會耗時（因?yàn)椴檎业乃俣茸兟耍?/p>
程序員：“實(shí)現(xiàn)就在hash方法上，可以發(fā)現(xiàn)的是，它是先算出正常的哈希值，然后與高16位做異或運(yùn)算，產(chǎn)生最終的哈希值。這樣做的好處可以增加了隨機(jī)性，減少了碰撞沖突的可能性?！?/p>
程序員：”在put的時候，首先對key做hash運(yùn)算，計(jì)算出該key所在的index。如果沒碰撞，直接放到數(shù)組中，如果碰撞了，需要判斷目前數(shù)據(jù)結(jié)構(gòu)是鏈表還是紅黑樹，根據(jù)不同的情況來進(jìn)行插入。假設(shè)key是相同的，則替換到原來的值。最后判斷哈希表是否滿了(當(dāng)前哈希表大小*負(fù)載因子），如果滿了，則擴(kuò)容“
程序員：”在get的時候，還是對key做hash運(yùn)算，計(jì)算出該key所在的index，然后判斷是否有hash沖突，假設(shè)沒有直接返回，假設(shè)有則判斷當(dāng)前數(shù)據(jù)結(jié)構(gòu)是鏈表還是紅黑樹，分別從不同的數(shù)據(jù)結(jié)構(gòu)中取出?！?/p>
程序員：”首先會比較hash值，隨后會用==運(yùn)算符和equals()來判斷該元素是否相同。說白了就是：如果只有hash值相同，那說明該元素哈希沖突了，如果hash值和equals() || ==?都相同，那說明該元素是同一個?！?/p>
程序員：”當(dāng)數(shù)組的大小大于64且鏈表的大小大于8的時候才會將鏈表改為紅黑樹，當(dāng)紅黑樹大小為6時，會退化為鏈表。這里轉(zhuǎn)紅黑樹退化為鏈表的操作主要出于查詢和插入時對性能的考量。鏈表查詢時間復(fù)雜度O(N)，插入時間復(fù)雜度O(1)，紅黑樹查詢和插入時間復(fù)雜度O(logN)“
程序員：“其實(shí)在日常開發(fā)中LinkedHashMap用得不多。在前面也提到了，LinkedHashMap底層結(jié)構(gòu)是數(shù)組+鏈表+雙向鏈表”，實(shí)際上它繼承了HashMap，在HashMap的基礎(chǔ)上維護(hù)了一個雙向鏈表。有了這個雙向鏈表，我們的插入可以是“有序”的，這里的有序不是指大小有序，而是插入有序。
程序員：“LinkedHashMap在遍歷的時候?qū)嶋H用的是雙向鏈表來遍歷的，所以LinkedHashMap的大小不會影響到遍歷的性能”
程序員：“TreeMap在現(xiàn)實(shí)開發(fā)中用得也不多，TreeMap的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹，TreeMap的key不能為null（如果為null，那還怎么排序呢），TreeMap有序是通過Comparator來進(jìn)行比較的，如果comparator為null，那么就使用自然順序”
程序員：“HashMap不是線程安全的，在多線程環(huán)境下，HashMap有可能會有數(shù)據(jù)丟失和獲取不了最新數(shù)據(jù)的問題，比如說：線程Aput進(jìn)去了，線程Bget不出來。我們想要線程安全，可以使用ConcurrentHashMap”
程序員：“ConcurrentHashMap是線程安全的Map實(shí)現(xiàn)類，它在juc包下的。線程安全的Map實(shí)現(xiàn)類除了ConcurrentHashMap還有一個叫做Hashtable。當(dāng)然了，也可以使用Collections來包裝出一個線程安全的Map。但無論是Hashtable還是Collections包裝出來的都比較低效（因?yàn)槭侵苯釉谕鈱犹譻ynchronize），所以我們一般有線程安全問題考量的，都使用ConcurrentHashMap”
程序員：“ConcurrentHashMap的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表/紅黑樹，它能支持高并發(fā)的訪問和更新，是線程安全的。ConcurrentHashMap通過在部分加鎖和利用CAS算法來實(shí)現(xiàn)同步，在get的時候沒有加鎖，Node都用了volatile給修飾。在擴(kuò)容時，會給每個線程分配對應(yīng)的區(qū)間，并且為了防止putVal導(dǎo)致數(shù)據(jù)不一致，會給線程的所負(fù)責(zé)的區(qū)間加鎖”
程序員：“不能，我不會”
程序員：“我在學(xué)習(xí)的時候也看過JDK7的HashMap和ConcurrentHashMap，其實(shí)還是有很多不一樣的地方，比如JDK 7 的HashMap在擴(kuò)容時是頭插法，在JDK8就變成了尾插法，在JDK7 的HashMap還沒有引入紅黑樹....ConcurrentHashMap 在JDK7 還是使用分段鎖的方式來實(shí)現(xiàn)，而JDK 8 就又不一樣了。但JDK 7細(xì)節(jié)我大多數(shù)都忘了?！?/p>
程序員：“我就沒用過JDK 7的API，我想著現(xiàn)在最低應(yīng)該也是用JDK8了吧？所以我就沒去仔細(xì)看了。要不我給你講講多線程相關(guān)的知識唄？”
程序員：“哦”
