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