1. 集合框架整體梳理與記憶主線1.1 集合框架的分層結(jié)構(gòu)與核心接口很多同學(xué)準(zhǔn)備Java面試的時候一提到集合就開始背源碼、背結(jié)論比如HashMap初始容量16負(fù)載因子0.75鏈表轉(zhuǎn)紅黑樹閾值8背得滾瓜爛熟結(jié)果面試官問一句為什么是8而不是9就卡住了。你如果能把集合框架當(dāng)成一棵樹來理解理清接口、實現(xiàn)類、數(shù)據(jù)結(jié)構(gòu)之間的遞進(jìn)關(guān)系這些問題其實是可以推導(dǎo)出來的而不是靠死記硬背。Java集合框架最頂層的兩個體系一個是Collection接口體系存放單元素一個是Map接口體系存放鍵值對。Collection下面又分三大分支List、Set、Queue。List是允許重復(fù)、有序的集合Set是不允許重復(fù)的集合Queue是隊列語義的集合。Map體系獨立于Collection但Map的實現(xiàn)類又和Set有千絲萬縷的聯(lián)系比如HashSet底層就是HashMapTreeSet底層就是TreeMap。我在實際面試中發(fā)現(xiàn)面試官很少直接問List和Set的區(qū)別而是喜歡把一個大的知識網(wǎng)絡(luò)拆成連環(huán)追問。比如你先回答了HashSet基于HashMap實現(xiàn)那下一步就問為什么HashSet的value是同一個Object再下一步就問如果兩個對象的hashCode相同會怎樣。所以你準(zhǔn)備集合面試的時候不要按著章節(jié)一節(jié)一節(jié)背一定要建立一張完整的知識拓?fù)涿恳粋€結(jié)論都要能向上推導(dǎo)到接口設(shè)計、向下追溯到源碼實現(xiàn)。1.2 為什么面試官愛考集合以及怎么高效準(zhǔn)備集合框架為什么是Java面試的絕對重點因為它同時考察了幾個層面的能力第一你對JDK基礎(chǔ)類庫的熟悉程度這是Java開發(fā)者的基本功第二你對數(shù)據(jù)結(jié)構(gòu)與算法的理解比如數(shù)組、鏈表、紅黑樹、哈希表都是筆試和面試手撕代碼的高頻考點第三你在實際業(yè)務(wù)中做技術(shù)選型的能力比如什么時候用ArrayList什么時候用LinkedList高并發(fā)場景下用HashMap會不會出事這直接反映出你有沒有線上實戰(zhàn)經(jīng)驗。企業(yè)招聘Java開發(fā)最怕招到那種只會寫CRUD、遇到性能問題就懵的候選人。集合恰恰是把業(yè)務(wù)代碼和底層原理連接得最緊密的一塊知識。你寫任何業(yè)務(wù)代碼幾乎都離不開集合接口數(shù)據(jù)要轉(zhuǎn)List、賬務(wù)明細(xì)要放進(jìn)Map做聚合、去重用Set、隊列用Queue。面試官通過集合這一個點就能判斷出你的基礎(chǔ)是否扎實、有沒有深入研究過JDK源碼、能不能應(yīng)對線上OOM或死循環(huán)這樣的突發(fā)問題。我在帶新人時經(jīng)常說一句話不要單獨背集合面試題要把集合框架和JVM內(nèi)存、并發(fā)編程、設(shè)計模式聯(lián)系起來學(xué)。比如ArrayList擴(kuò)容涉及數(shù)組拷貝和內(nèi)存分配HashMap的并發(fā)問題涉及線程安全Collections工具類里的各種包裝方法涉及裝飾器模式。這樣橫向串聯(lián)起來你面試時候的回答深度會明顯不一樣因為你能從多個維度去解釋一個技術(shù)決策而不是只說出一個標(biāo)準(zhǔn)答案。2. List核心考點底層實現(xiàn)與擴(kuò)容機(jī)制2.1 ArrayList動態(tài)擴(kuò)容背后的設(shè)計思想ArrayList是Java面試中最親民的集合類因為大家平時寫代碼用得太多了但面試考起來一點不簡單。ArrayList本質(zhì)上是一個動態(tài)數(shù)組它默認(rèn)的初始容量是10每次擴(kuò)容的時候會創(chuàng)建新數(shù)組然后把舊數(shù)組里的元素用System.arraycopy拷貝過去。關(guān)鍵考點在于擴(kuò)容的倍率——JDK 8里面是oldCapacity (oldCapacity 1)也就是原來的1.5倍。你有沒有想過為什么擴(kuò)容是1.5倍而不是2倍或者1.2倍這涉及到擴(kuò)容策略的時間復(fù)雜度和空間利用率的權(quán)衡。如果擴(kuò)容倍數(shù)太大比如2倍那擴(kuò)容一次能撐很久但空間浪費很嚴(yán)重可能出現(xiàn)明明只放了幾百個元素卻占了上千個容量的情況如果擴(kuò)容倍數(shù)太小比如1.1倍那擴(kuò)容頻率會非常高頻繁的數(shù)組拷貝會導(dǎo)致性能下降明顯。1.5倍是經(jīng)過權(quán)衡之后一個比較折中的方案——每次擴(kuò)容新容量是舊容量的1.5倍均攤下來添加元素的平均時間復(fù)雜度是O(1)空間上也不會浪費太夸張。面試官還特別愛問一個細(xì)節(jié)ArrayList的size()和capacity有什么區(qū)別。size是當(dāng)前元素個數(shù)capacity是數(shù)組的最大容量。很多新手以為list.size()返回的就是數(shù)組長度其實不然。當(dāng)你new ArrayList()的時候底層是一個空數(shù)組只有當(dāng)?shù)谝淮蝍dd元素的時候才會用DEFAULT_CAPACITY(10)去初始化容量。這個設(shè)計叫做懶加載目的是避免創(chuàng)建對象時就分配多余內(nèi)存。提示如果你能預(yù)估元素數(shù)量一定要用new ArrayList(expectedSize)這樣能避免多次擴(kuò)容帶來的數(shù)組拷貝損耗。這個習(xí)慣在數(shù)據(jù)量大時性能差異非常明顯。ArrayList還有一個容易被問倒的點——subList陷阱。list.subList(0, 5)返回的不是一個新的ArrayList而是原列表的一個視圖底層用的是SubList內(nèi)部類。如果你對subList返回的結(jié)果執(zhí)行add或者remove操作會觸發(fā)原列表的modCount變化導(dǎo)致原列表在迭代時拋出ConcurrentModificationException。這個坑我在實際項目中見過不止一次很多人把subList的結(jié)果當(dāng)獨立列表用結(jié)果線上報錯查了半天。2.2 LinkedList雙向鏈表的功能邊界LinkedList在面試中和ArrayList是打包出現(xiàn)的對比考點。LinkedList底層是雙向鏈表JDK 8里的實現(xiàn)每個節(jié)點有三個屬性item數(shù)據(jù)、prev前驅(qū)節(jié)點、next后繼節(jié)點。因為每個節(jié)點還額外保存了兩個指針?biāo)訪inkedList比ArrayList更占內(nèi)存——一個元素除了數(shù)據(jù)本身還要存儲兩個引用在64位JVM上開啟了壓縮指針的情況下每個節(jié)點額外開銷約16字節(jié)。LinkedList的優(yōu)勢在于頭尾操作addFirst、addLast、removeFirst、removeLast這些操作的復(fù)雜度都是O(1)因為它不需要移動其他元素。但是注意一點LinkedList的get(int index)和add(int index, E element)并不是O(1)——雖然它內(nèi)部有一個優(yōu)化會根據(jù)index和size/2的比較決定從頭遍歷還是從尾遍歷但整體依然是O(n)。很多人背結(jié)論說LinkedList查找慢、插入快這個說法不夠嚴(yán)謹(jǐn)插入快指的是在已知節(jié)點位置的情況下插入如果你需要先查到某個位置再插入那這個查找的O(n)成本也要算進(jìn)去。我面過一些候選人一聽到LinkedList是鏈表實現(xiàn)的就趕緊說那它插入快。面試官馬上追問那我現(xiàn)在要在第1000個位置插入一個元素鏈表做了什么操作這時候就能看出是真懂還是背結(jié)論了。還有一個隱藏考點LinkedList實現(xiàn)了Deque接口所以它可以直接當(dāng)作?；蛘哧犃衼碛?。當(dāng)你寫LinkedList的時候官方是建議使用ArrayDeque來實現(xiàn)棧和隊列因為ArrayDeque基于循環(huán)數(shù)組平均性能更高內(nèi)存更緊湊。不過話說回來LinkedList的pop、push、offer、poll這些方法在日常刷題時用起來確實方便而且作為一面手撕算法的工具它完全夠用。2.3 面試必問的ArrayList vs LinkedList對比面試官非常喜歡讓候選人用表格或口頭陳述來對比ArrayList和LinkedList我建議你在準(zhǔn)備時記住以下核心差異而不是背一個數(shù)組一個鏈表這種空話對比維度ArrayListLinkedList底層結(jié)構(gòu)動態(tài)數(shù)組雙向鏈表隨機(jī)訪問O(1)按索引直接定位O(n)需要遍歷尾部插入均攤O(1)可能觸發(fā)擴(kuò)容O(1)指定位置插入O(n)涉及元素移位O(n)需要先定位定位后插入O(1)內(nèi)存占用相對緊湊有預(yù)分配冗余每個元素額外存儲兩個指針應(yīng)用場景讀多寫少、隨機(jī)訪問頻繁頭尾操作頻繁、無需隨機(jī)訪問我在實際開發(fā)中總結(jié)出來一個很樸素的經(jīng)驗大部分業(yè)務(wù)場景下選ArrayList就行LinkedList的優(yōu)勢場景其實非常少。原因很簡單現(xiàn)代CPU對連續(xù)內(nèi)存的訪問是有緩存友好的特性——ArrayList底層是連續(xù)數(shù)組遍歷時CPU緩存命中率很高而LinkedList每個節(jié)點在內(nèi)存中散落分布每次訪問都可能發(fā)生緩存缺失實際性能要打折扣。再加上LinkedList的節(jié)點對象更多、GC壓力更大所以很多人說LinkedList在某些情況下比ArrayList慢得多并不是錯覺。另外還有一個容易被忽略的點LinkedList沒有實現(xiàn)RandomAccess接口而ArrayList實現(xiàn)了。這個接口是一個標(biāo)記接口它影響到Collections.binarySearch等工具類對集合遍歷方式的選擇——實現(xiàn)了RandomAccess的集合二分查找會走索引遍歷邏輯沒實現(xiàn)的則走迭代器遍歷邏輯。這也側(cè)面說明有時候判斷一個集合能不能高效隨機(jī)訪問不能只看類名還要看它是否實現(xiàn)了這個標(biāo)記接口。3. HashMap全解數(shù)組鏈表紅黑樹的組合藝術(shù)3.1 HashMap底層數(shù)據(jù)結(jié)構(gòu)與put流程HashMap是整個Java集合面試的核彈級考點可以說如果HashMap答不好這場面試基本就涼了一半。Java 8版本的HashMap底層結(jié)構(gòu)是數(shù)組 鏈表 紅黑樹。數(shù)組的每個位置叫桶(bucket)當(dāng)多個鍵哈希沖突時元素在同一個桶里以鏈表形式串聯(lián)當(dāng)某個桶的鏈表長度太長時鏈表會轉(zhuǎn)化為紅黑樹以提升查詢效率。先記住一個足夠深度的put流程這個流程我建議你能手寫出來而不是靠感覺。當(dāng)你調(diào)用map.put(key, value)時對key.hashCode()做一次擾動計算讓高位也參與低位運算降低哈希沖突概率。根據(jù)哈希值按位與(n - 1)得到桶下標(biāo)n是當(dāng)前數(shù)組長度。如果數(shù)組為null或者長度為0先觸發(fā)resize()初始化。如果目標(biāo)桶位置為null直接new Node放入。如果桶位置不為null說明發(fā)生了哈希沖突此時需要判斷如果鏈表頭節(jié)點是key相同的舊節(jié)點直接覆蓋value否則遍歷鏈表找到相同key則替換value沒有相同key就在鏈表尾部插入一個新節(jié)點Java 8是尾插法。插入完成后判斷該桶鏈表的節(jié)點數(shù)是否達(dá)到樹化閾值8并且數(shù)組長度達(dá)到64滿足則轉(zhuǎn)換為紅黑樹。最后判斷當(dāng)前的size是否超過了擴(kuò)容閾值容量乘以負(fù)載因子超過就resize擴(kuò)容。視頻課程和面經(jīng)里都會提到這個流程但你有沒有想過為什么計算桶下標(biāo)要用(n - 1) hash而不是hash % n這一標(biāo)準(zhǔn)取模運算原因有兩點第一當(dāng)n是2的冪次方時n-1的二進(jìn)制低位全是1按位與運算可以完美替代取模而按位與比取模運算快得多第二這樣分布更均勻因為取模運算在n不是2的冪的時候高位會丟失沖突概率更大。3.2 擴(kuò)容機(jī)制、負(fù)載因子與尋址算法的深層邏輯HashMap的默認(rèn)容量是16負(fù)載因子是0.75。擴(kuò)容閾值threshold等于capacity乘以loadFactor也就是說當(dāng)元素個數(shù)超過16乘以0.75等于12的時候HashMap會擴(kuò)容為原來的2倍。這個0.75負(fù)載因子是怎么來的官方注釋里提到這是時間復(fù)雜度和空間復(fù)雜度的一個折中。如果負(fù)載因子調(diào)大比如調(diào)成1.0那么空間利用率會提高但哈希沖突概率更高鏈表更長查詢效率下降如果調(diào)小比如0.5那么沖突少了但空間浪費太多頻繁擴(kuò)容也帶來性能損耗。0.75這個值是JDK源碼作者根據(jù)大量實驗數(shù)據(jù)算出來的近似地讓鏈表長度服從泊松分布在大多數(shù)情況下保證沖突概率極低。擴(kuò)容的時候有一個非常體現(xiàn)設(shè)計功底的細(xì)節(jié)擴(kuò)容為原來的2倍后元素在新數(shù)組中的位置要么在原來的下標(biāo)要么在原下標(biāo) 舊容量這兩個位置之一。為什么因為數(shù)組長度從16變成32n-1的掩碼相當(dāng)于多了一位1某個元素在新掩碼下多出的那一位正好等于它舊hash值中對應(yīng)那一位的值那一位是0就呆在原位是1就移動到原下標(biāo)舊容量。Java 8就是根據(jù)e.hash oldCap是否等于0來判斷元素應(yīng)該留在原位還是移動到高位這樣就不需要重新計算每個元素的hash值了。這個無需rehash的設(shè)計不僅高效而且在并發(fā)環(huán)境下還避免了Java 7頭插法擴(kuò)容導(dǎo)致的死循環(huán)問題。Java 7擴(kuò)容時用頭插法轉(zhuǎn)移元素在多線程環(huán)境下容易出現(xiàn)環(huán)形鏈表而Java 8改成尾插法后理論上不再有這個死循環(huán)問題——但HashMap依然不是線程安全的并發(fā)put還是會導(dǎo)致數(shù)據(jù)覆蓋等問題。3.3 樹化條件與紅黑樹相關(guān)考點鏈表轉(zhuǎn)紅黑樹的條件有兩個兩者必須同時滿足第一某個桶的鏈表長度大于等于8第二整個數(shù)組長度不小于64。如果鏈表長度到了8但數(shù)組長度還不到64這時候不會立即樹化而是先進(jìn)行一次resize擴(kuò)容讓元素分散到更多桶里。這個設(shè)計思路很清晰小數(shù)組下樹化意義不大因為容量太小導(dǎo)致哈希沖突嚴(yán)重與其用紅黑樹解決沖突不如把數(shù)組做大。那為什么樹化閾值是8源碼注釋里給了一個統(tǒng)計學(xué)解釋在負(fù)載因子0.75的情況下鏈表長度達(dá)到8的概率大約是千萬分之一也就是說在正常情況下幾乎不會出現(xiàn)這么長的鏈表。如果真出現(xiàn)了說明元素分布的hash函數(shù)已經(jīng)惡化了此時引入紅黑樹來兜底把最壞情況下的查詢復(fù)雜度從O(n)降到O(log n)。面試中還常問另一個數(shù)字——為什么退化閾值是6而不是7或8這是為了留緩沖避免鏈表和紅黑樹頻繁地互相轉(zhuǎn)換。如果閾值都是8某個桶的長度在7到8之間反復(fù)橫跳就會導(dǎo)致頻繁的樹化、退化性能開銷很大。6和8之間隔了2個差值相當(dāng)于加了一個滯回區(qū)間防止抖動。注意紅黑樹是面試高級崗位時的加分項。你至少要能說清楚紅黑樹的五個性質(zhì)——節(jié)點非紅即黑、根黑、葉子黑、紅節(jié)點不能連續(xù)、任意節(jié)點到其葉子節(jié)點的路徑包含相同數(shù)量的黑節(jié)點——以及為什么插入和刪除后需要旋轉(zhuǎn)和變色來恢復(fù)平衡。3.4 為什么HashMap是線程不安全的這是我勸誡過很多次的一個高頻考點。HashMap在多線程環(huán)境下至少有三個問題一是多線程同時put時可能發(fā)生數(shù)據(jù)覆蓋比如兩個線程同時判斷某個桶為null然后同時new Node放入后寫的覆蓋了先寫的一個元素就丟了二是擴(kuò)容時多個線程同時對shared數(shù)組做rehash可能在Java 8之前版本導(dǎo)致鏈表循環(huán)引用三是size的值是普通int多線程下并發(fā)增減并不安全。如果你在面試中說Java 8的HashMap擴(kuò)容采用了尾插法所以沒有死循環(huán)問題了面試官大概率會接著問那它線程安全了嗎千萬不要踩這個坑——沒有死循環(huán)不等于線程安全數(shù)據(jù)覆蓋問題在Java 8依然存在。嚴(yán)謹(jǐn)?shù)恼f法是Java 8修復(fù)了擴(kuò)容時死循環(huán)的問題但HashMap仍然不是線程安全的并發(fā)場景應(yīng)該使用ConcurrentHashMap。我在實際工作中也見過有人用HashMap做緩存然后上線后偶發(fā)出現(xiàn)數(shù)據(jù)消失的問題排查到最后都是并發(fā)put覆蓋導(dǎo)致。新手容易誤以為我用HashMap并且加個synchronized修飾方法就安全了但其實不加同步的并發(fā)讀寫HashMap臟讀、覆蓋、無限循環(huán)都可能發(fā)生風(fēng)險極大。4. 并發(fā)場景下的集合選型線程安全與讀寫策略4.1 ConcurrentHashMap的演進(jìn)與實現(xiàn)對比并發(fā)場景下首選ConcurrentHashMap。Java 7版本它的實現(xiàn)是分段鎖結(jié)構(gòu)內(nèi)部維護(hù)了一個Segment數(shù)組每個Segment繼承自ReentrantLock多個線程可以同時操作不同的Segment從而把鎖競爭分散到16個段上。Java 8拋棄了Segment這種設(shè)計改成更細(xì)粒度的CAS synchronized——直接用Node數(shù)組鎖的粒度從段細(xì)化為單個桶節(jié)點。Java 8的ConcurrentHashMap在put時如果目標(biāo)桶位為空使用CAS直接寫入不需要加鎖如果桶位不為空用synchronized鎖住該桶的頭節(jié)點再進(jìn)行鏈表或紅黑樹的插入。這樣并發(fā)度大大提升——兩個線程只要鎖的不是同一個桶節(jié)點就能真正的并行寫入。而且synchronized在JDK 8之后經(jīng)過鎖升級優(yōu)化偏向鎖、輕量級鎖、重量級鎖性能并不比ReentrantLock差代碼也簡潔了不少。需要提醒的是ConcurrentHashMap的size()在并發(fā)寫場景下不是精確值它返回的是一個估測值JDK 8用了一個CounterCell數(shù)組來分散計數(shù)最終通過累加來統(tǒng)計。面試中被問到怎么計算size的時候不要說直接讀size字段而要說出baseCount加累加CounterCell這套機(jī)制才能體現(xiàn)出你真的讀過源碼。4.2 Collections工具類包裝方法與Hashtable的取舍除了ConcurrentHashMap還有一個老牌線程安全Map叫Hashtable。Hashtable是JDK 1.0就有的類內(nèi)部直接用synchronized鎖住整個表所以讀和寫都會被同一個鎖阻塞并發(fā)性能非常差。還有Collections.synchronizedMap(new HashMap())這種方式返回的是一個同步包裝類本質(zhì)上也是給每個方法加synchronized鎖。既然有了ConcurrentHashMap這兩者在高并發(fā)場景下都不推薦。低并發(fā)場景或僅需要線程安全的簡單封裝時Collections.synchronizedMap也有它的價值——代碼簡單、改動小、不會引入額外的復(fù)雜度。而ConcurrentHashMap在讀多寫少的場景下幾乎是無鎖的因為它的get操作不加鎖依靠volatile CAS保證可見性。如果數(shù)據(jù)量不大、并發(fā)壓力不高用synchronizedMap完全沒問題如果寫多讀多、要求高吞吐還是用ConcurrentHashMap更合適。面試官如果問Hashtable為什么慢你要能答出兩點鎖的粒度太大整表加鎖和鎖本身是重量級的。對比之下ConcurrentHashMap鎖的粒度是單個桶讀操作又不加鎖性能自然好很多。4.3 CopyOnWriteArrayList與其他并發(fā)集合并發(fā)場景下的List很多人不知道用哪個。常用的有兩種CopyOnWriteArrayList和Collections.synchronizedList(new ArrayList())。CopyOnWriteArrayList的名字說明了它的寫策略每次寫操作add、remove等都會復(fù)制一份底層數(shù)組在副本上修改然后通過volatile數(shù)組引用替換舊數(shù)組讀操作直接讀舊數(shù)組不加鎖。這個方案讓讀多寫少的場景非常高效——比如配置文件刷新、白名單列表、緩存鍵集合之類的場景。面試喜歡問CopyOnWriteArrayList的缺點你要能主動說出來寫操作代價高昂每次add都要復(fù)制整個數(shù)組如果列表很大或者寫頻繁內(nèi)存和GC壓力會很大另外讀操作雖然能讀到舊數(shù)據(jù)但不保證實時看到最新寫入存在弱一致性問題。如果你的業(yè)務(wù)是寫多讀少CopyOnWriteArrayList反而會成為性能瓶頸不如用synchronizedList。CopyOnWriteArrayList還有一個巧妙之處它的迭代器不支持add/remove操作遍歷時不會拋ConcurrentModificationException因為迭代器是在創(chuàng)建時基于當(dāng)前數(shù)組快照的。這個快照迭代器的特性有些面試官會問到你可以順便提一嘴與HashMap的fail-fast機(jī)制做對比。5. Set與排序規(guī)則去重邏輯和比較器體系5.1 HashSet與TreeSet的實現(xiàn)原理HashSet看似獨立其實底層完全復(fù)用HashMap。當(dāng)你new HashSet()的時候底層創(chuàng)建的是new HashMap()而每次add的元素作為HashMap的keyvalue統(tǒng)一用一個靜態(tài)的PRESENT占位對象。所以HashSet的元素天然不會重復(fù)——是否重復(fù)完全由HashMap的key判斷邏輯決定。而HashMap判斷key是否相同的規(guī)則是先比較hashCode是否相等再比較equals方法是否返回true。所以Set去重的前提是正確重寫equals和hashCode。TreeSet則基于TreeMap實現(xiàn)底層是一個紅黑樹它要求元素要么實現(xiàn)Comparable接口要么在構(gòu)造TreeSet時傳入Comparator。TreeSet的元素天然是有序的遍歷時按自然順序或自定義順序輸出——但代價是插入、刪除的時間復(fù)雜度是O(log n)比HashSet的O(1)慢。我在面試中經(jīng)常問候選人一個問題如果一個對象作為HashSet的元素它的hashCode變了會發(fā)生什么很多人答不上來。實際場景是如果你把對象放進(jìn)HashSet后又修改了對象參與hashCode計算的字段那么這個對象的hashCode就變了但它在HashSet底層的桶下標(biāo)依然是舊的。這時候你再把這個對象取出來判斷是否存在會發(fā)現(xiàn)在另一個桶里找不到它集合里就產(chǎn)生了一個內(nèi)存泄漏——對象永遠(yuǎn)留在Set里無法通過正常方法刪除。這個坑在寫緩存、寫去重邏輯時特別容易踩。5.2 Comparable與Comparator對比Comparable和Comparator是Java排序體系的兩塊基石。Comparable是自然排序定義在元素類內(nèi)部實現(xiàn)compareTo方法意思是我天生可以和自己比較Comparator是臨時比較器定義在類外部適合做多種不同的排序規(guī)則。說人話Comparable是元素自己的默認(rèn)排序規(guī)則Comparator是外部的靈活替身。舉個例子你有一個Person類默認(rèn)按age排序就實現(xiàn)Comparable但你在某個業(yè)務(wù)場景下想按name排序另一個場景想按salary排序這時候就不建議修改Person類的compareTo而是分別寫不同的Comparator匿名類或Lambda表達(dá)式。面試官特別喜歡考如果一個對象實現(xiàn)了Comparable同時又傳入了Comparator以哪個為準(zhǔn)——答案是Comparator優(yōu)先因為TreeSet或Collections.sort接收比較器時會用比較器而非自然順序。5.3 equals和hashCode的正確姿勢這是一個老生常談卻又特別容易在實戰(zhàn)中出錯的知識點。equals和hashCode的約定是如果兩個對象equals為true那么它們的hashCode必須相等反過來不成立hashCode相等但equals不相等是允許的。如果你重寫了equals卻沒有重寫hashCode那么兩個邏輯上相等的對象會在HashMap/HashSet中因為hashCode不同而被當(dāng)成不同元素。我見過一個真實的線上bug項目里定義了一個訂單對象只重寫了equals方法用于業(yè)務(wù)比較但沒有重寫hashCode結(jié)果用這個對象做Set去重時同樣的訂單被存了兩份最后導(dǎo)致統(tǒng)計結(jié)果翻倍。重寫hashCode的時候必須在構(gòu)造hashCode的字段上使用相同的字段而且這些字段最好是不可變的——如果參與hashCode計算的字段能變那集合的去重邏輯就會出問題。注意在實現(xiàn)hashCode時不要用乘以固定質(zhì)數(shù)的玄學(xué)恐懼實際上只要能保證分布均勻、性能可接受就行。我習(xí)慣用31這個數(shù)因為31 * i在JVM里可以被優(yōu)化成(i 5) - i位運算比乘法快。6. 高頻面試題實戰(zhàn)與回答思路6.1 經(jīng)典速查表為了讓你在面試前快速過一遍我把最常考的集合面試題整理成了一張速查表你可以把每一行當(dāng)成一個自測題遮住回答列看自己能不能在兩分鐘內(nèi)說清楚。面試題回答要點ArrayList擴(kuò)容多少倍1.5倍oldCapacity (oldCapacity 1)均攤時間復(fù)雜度O(1)HashMap為什么容量是2的冪保證(n - 1) hash與hash % n等價位運算更快同時讓擴(kuò)容后位置計算更簡單負(fù)載因子為什么是0.75時間與空間的折中沖突概率和空間利用率的平衡HashMap鏈表轉(zhuǎn)紅黑樹的閾值鏈表長度到達(dá)8且數(shù)組長度不小于64才能樹化紅黑樹轉(zhuǎn)鏈表的閾值6留滯回區(qū)間避免頻繁轉(zhuǎn)換Java 8 HashMap插入方式尾插法相比Java 7頭插法避免擴(kuò)容死循環(huán)ConcurrentHashMap JDK 8實現(xiàn)CAS synchronized鎖粒度是單個桶節(jié)點CopyOnWriteArrayList寫操作代價每次寫復(fù)制整個數(shù)組寫多讀少場景不適用HashSet如何實現(xiàn)去重底層是HashMap元素作為keyvalue統(tǒng)一PRESENT占位TreeSet要求元素滿足什么實現(xiàn)Comparable或傳入Comparator6.2 場景設(shè)計題與連環(huán)追問集合部分的面試中高級崗位非常喜歡出場景設(shè)計題。最常見的一個是給你500萬個字符串統(tǒng)計每個字符串出現(xiàn)的次數(shù)不能用現(xiàn)成的統(tǒng)計框架你怎么設(shè)計這個問題其實直接指向HashMap的用法遍歷字符串列表判斷map.containsKey(s)存在則計數(shù)加一不存在則put初始值1。如果你能用Java 8的merge方法配合Integer::sum一行代碼就能搞定既簡潔又說明你熟悉JDK新特性。如果面試官進(jìn)一步問字符串特別多、內(nèi)存不夠怎么辦你可以回答使用外部排序、分片文件、Redis HyperLogLog非精確或者布隆過濾器做預(yù)過濾這些方案思路是加分項。另一個經(jīng)典設(shè)計題是如何基于LinkedList實現(xiàn)LRU緩存。這個題目考察的是你知道LRU需要訪問到元素就把它移到頭部這種操作而LinkedList的remove和addFirst配合正好可以實現(xiàn)。如果你有經(jīng)驗?zāi)銜栏咝У慕夥ㄊ荋ashMap 自定義雙向鏈表讓get操作的時間復(fù)雜度從O(n)降到O(1)。這兩種方案都能說清楚的話說明你對數(shù)據(jù)結(jié)構(gòu)的組合使用有感覺。還有一個要留意的是手寫一個簡單的HashMap put邏輯。這道題看起來簡單其實考察了你是否理解數(shù)組索引計算、沖突解決、擴(kuò)容這三大模塊。我建議你平時就寫一個只支持put和get的精簡版比如用Node數(shù)組存元素用(n - 1) hash計算索引沖突時用頭插法或尾插法形成鏈表。寫一遍之后再去看JDK源碼很多疑問會迎刃而解。7. 備考經(jīng)驗與實戰(zhàn)避坑筆記7.1 我親測有效的記憶方法備考集合面試我最推薦的思路是從下往上的歷史演進(jìn)法。先理解集合框架是為了解決什么問題而設(shè)計的——比如從數(shù)組的固定長度無法自動擴(kuò)容衍生出ArrayList從鏈表查找效率低衍生出哈希表和HashMap從HashMap線程不安全衍生出ConcurrentHashMap。當(dāng)你把每個集合類都當(dāng)成某個問題的解決方案去記憶它的數(shù)據(jù)結(jié)構(gòu)、核心參數(shù)、適用場景就都變成邏輯推導(dǎo)的必然結(jié)果而不是需要死記的數(shù)字。我見過很多候選人準(zhǔn)備面試時被源碼細(xì)節(jié)淹沒把每個數(shù)字背得滾瓜爛熟但一說到為什么就支支吾吾。我的建議是對于每個核心參數(shù)16、0.75、8、6、64你至少要能答出它的來源和權(quán)衡邏輯。數(shù)字忘了可以現(xiàn)場推導(dǎo)但邏輯沒想清楚就會暴露真實水平。7.2 實戰(zhàn)中最容易忽略的細(xì)節(jié)寫代碼時大家都會用集合但很多細(xì)節(jié)是面試和線上問題的高發(fā)區(qū)。我在最后把這些低級錯誤但代價極高的坑列出來希望能幫大家避雷第一Arrays.asList()返回的不是java.util.ArrayList而是Arrays內(nèi)部的一個私有ArrayList它不支持add和remove操作。如果你對它調(diào)用add會拋UnsupportedOperationException。正確的轉(zhuǎn)換方式是new ArrayList(Arrays.asList(...))。第二集合嵌套使用時比如ListMapString, List 這種結(jié)構(gòu)操作內(nèi)部集合前一定要判空否則一個null就夠你排查半天。我習(xí)慣在組裝這種復(fù)雜結(jié)構(gòu)時提前用computeIfAbsent來避免空指針非常順手。第三注意集合序列化的坑。HashMap在序列化時并不會序列化整個table數(shù)組而是先遍歷所有Node節(jié)點把key和value分別序列化。因為擴(kuò)容后數(shù)組下標(biāo)會變化直接序列化數(shù)組反而會造成數(shù)據(jù)錯誤。這個設(shè)計也解釋了為什么HashMap的table不能用final修飾——因為擴(kuò)容時要重新賦值數(shù)組引用。第四如果需要頻繁遍歷并刪除集合中的元素不要用fori循環(huán)正序刪除因為刪除元素后索引會錯位可能跳過元素。正確做法是使用迭代器的remove方法或直接用removeIf。從Java 8開始removeIf是最簡潔的方案也是我日常開發(fā)中的首選。寫到這里我想起自己第一次深入研究HashMap源碼的時候被那一行行位運算和擴(kuò)容邏輯繞得暈頭轉(zhuǎn)向。后來我把每個參數(shù)都代入具體數(shù)字一點點推演流程突然發(fā)現(xiàn)這些設(shè)計像搭積木一樣環(huán)環(huán)相扣。如果你正在準(zhǔn)備面試別急把集合框架當(dāng)成一棵樹慢慢梳理從根接口到葉子實現(xiàn)類再到并發(fā)變體和工具類理順之后你會發(fā)現(xiàn)面試題變得不再八股而是有邏輯、有血有肉的知識體系。希望這篇總結(jié)能幫你少走一些彎路面試順利通過。