前言
文本已收錄至我的GitHub：https://github.com/ZhongFuCheng3y/3y，有300多篇原創文章，最近在連載面試系列！
我，三歪，最近開始寫面試系列，我給這個面試系列取了一個名字，叫做《求求大廠給個Offer》
所以這篇文章叫做《求求大廠給個Offer：Map面試題》
接下來就開始吧，
面試現場
三歪：“我叫三歪，這幾年寫了300+原創技術文章，近1000頁的原創電子書和多個知識點的思維導圖，我的愿景是：只要關注我并三連的同學都可以拿到大廠offer，我的....”
三歪：“Map在Java里邊是一個介面，常見的實作類有HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap”
三歪：“首先要明確的是：在Java里邊，哈希表的結構是陣列+鏈表的方式，HashMap底層資料機構是陣列+鏈表/紅黑樹、LinkedHashMap底層資料結構是陣列+鏈表+雙向鏈表、TreeMap底層資料結構是紅黑樹，而ConcurrentHashMap底層資料結構也是陣列+鏈表/紅黑樹”
面試官：“我們先以HashMap開始吧，你能講講當你new一個HashMap的時候，會發生什么嗎？”
三歪：“HashMap有幾個構造方法，但最主要的就是指定初始值大小和負載因子的大小，如果我們不指定，默認HashMap的大小為16，負載因子的大小為0.75”
三歪：“HashMap的大小只能是2次冪的，假設你傳一個10進去，實際上最終HashMap的大小是16，你傳一個7進去，HashMap最終的大小是8，具體的實作在tableSizeFor可以看到，我們把元素放進HashMap的時候，需要算出這個元素所在的位置（hash），在HashMap里用的是位運算來代替取模，能夠更加高效地算出該元素所在的位置，為什么HashMap的大小只能是2次冪，因為只有大小為2次冪時，才能合理用位運算替代取模，”
三歪：“而負載因子的大小決定著哈希表的擴容和哈希沖突，比如現在我默認的HashMap大小為16，負載因子為0.75，這意味著陣列最多只能放12個元素，一旦超過12個元素，則哈希表需要擴容，怎么算出是12呢？很簡單，就是16*0.75，每次put元素進去的時候，都會檢查HashMap的大小有沒有超過這個閾值，如果有，則需要擴容，”
三歪：“鑒于上面的說法（HashMap的大小只能是2次冪），所以擴容的時候時候默認是擴原來的2倍”
三歪：“顯然擴容這個操作肯定是耗時的，那我能不能把負載因子調高一點，比如我要調至為1，那我的HashMap就等到16個元素的時候才擴容呢，顯然是可以的，但是不推薦，負載因子調高了，這意味著哈希沖突的概率會增高，哈希沖突概率增高，同樣會耗時（因為查找的速度變慢了）”
三歪：“實作就在hash方法上，可以發現的是，它是先算出正常的哈希值，然后與高16位做異或運算，產生最終的哈希值，這樣做的好處可以增加了隨機性，減少了碰撞沖突的可能性，”
三歪：”在put的時候，首先對key做hash運算，計算出該key所在的index，如果沒碰撞，直接放到陣列中，如果碰撞了，需要判斷目前資料結構是鏈表還是紅黑樹，根據不同的情況來進行插入，假設key是相同的，則替換到原來的值，最后判斷哈希表是否滿了(當前哈希表大小*負載因子），如果滿了，則擴容“
三歪：”在get的時候，還是對key做hash運算，計算出該key所在的index，然后判斷是否有hash沖突，假設沒有直接回傳，假設有則判斷當前資料結構是鏈表還是紅黑樹，分別從不同的資料結構中取出，“
三歪：”首先會比較hash值，隨后會用==運算子和equals()來判斷該元素是否相同，說白了就是：如果只有hash值相同，那說明該元素哈希沖突了，如果hash值和equals() || == 都相同，那說明該元素是同一個，“
三歪：”當陣列的大小大于64且鏈表的大小大于8的時候才會將鏈表改為紅黑樹，當紅黑樹大小為6時，會退化為鏈表，這里轉紅黑樹退化為鏈表的操作主要出于查詢和插入時對性能的考量，鏈表查詢時間復雜度O(N)，插入時間復雜度O(1)，紅黑樹查詢和插入時間復雜度O(logN)“
三歪：“其實在日常開發中LinkedHashMap用得不多，在前面也提到了，LinkedHashMap底層結構是陣列+鏈表+雙向鏈表”，實際上它繼承了HashMap，在HashMap的基礎上維護了一個雙向鏈表，有了這個雙向鏈表，我們的插入可以是“有序”的，這里的有序不是指大小有序，而是插入有序，
三歪：“LinkedHashMap在遍歷的時候實際用的是雙向鏈表來遍歷的，所以LinkedHashMap的大小不會影響到遍歷的性能”
三歪：“TreeMap在現實開發中用得也不多，TreeMap的底層資料結構是紅黑樹，TreeMap的key不能為null（如果為null，那還怎么排序呢），TreeMap有序是通過Comparator來進行比較的，如果comparator為null，那么就使用自然順序”
三歪：“HashMap不是執行緒安全的，在多執行緒環境下，HashMap有可能會有資料丟失和獲取不了最新資料的問題，比如說：執行緒Aput進去了，執行緒Bget不出來，我們想要執行緒安全，可以使用ConcurrentHashMap”
三歪：“ConcurrentHashMap是執行緒安全的Map實作類，它在juc包下的，執行緒安全的Map實作類除了ConcurrentHashMap還有一個叫做Hashtable，當然了，也可以使用Collections來包裝出一個執行緒安全的Map，但無論是Hashtable還是Collections包裝出來的都比較低效（因為是直接在外層套synchronize），所以我們一般有執行緒安全問題考量的，都使用ConcurrentHashMap”
三歪：“ConcurrentHashMap的底層資料結構是陣列+鏈表/紅黑樹，它能支持高并發的訪問和更新，是執行緒安全的，ConcurrentHashMap通過在部分加鎖和利用CAS演算法來實作同步，在get的時候沒有加鎖，Node都用了volatile給修飾，在擴容時，會給每個執行緒分配對應的區間，并且為了防止putVal導致資料不一致，會給執行緒的所負責的區間加鎖”
三歪：“不能，我不會”
三歪：“我在學習的時候也看過JDK7的HashMap和ConcurrentHashMap，其實還是有很多不一樣的地方，比如JDK 7 的HashMap在擴容時是頭插法，在JDK8就變成了尾插法，在JDK7 的HashMap還沒有引入紅黑樹....ConcurrentHashMap 在JDK7 還是使用分段鎖的方式來實作，而JDK 8 就又不一樣了，但JDK 7細節我大多數都忘了，”
三歪：“我就沒用過JDK 7的API，我想著現在最低應該也是用JDK8了吧？所以我就沒去仔細看了，要不我給你講講多執行緒相關的知識唄？”
三歪：“哦”
題外話
針對這次的面試可能你想了解更多Map的細節，比如說Map基礎知識/HashMap/LinkedHashMap/TreeMap/ConcurrentHashMap的原始碼，可以在微信搜「Java3y」回復「Map」即可獲取我之前寫的原創文章，
涵蓋Java后端所有知識點的開源專案，已有10K+ star！內含1000+頁原創電子書！！！
- GitHub
- Gitee訪問更快
PDF檔案的內容均為手打，有任何的不懂都可以直接來問我
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/45100.html
標籤：Java
上一篇：MySQL資料和索引占用空間查詢