概述類(lèi)面試題
1. 請(qǐng)說(shuō)一下Java容器集合的分類(lèi)，各自的繼承結(jié)構(gòu)
- Java中的容器集合分為兩大陣營(yíng)，一個(gè)是Collection，一個(gè)是Map
- Collection下分為Set，List，Queue
- Set的常用實(shí)現(xiàn)類(lèi)有HashSet，TreeSet等
- List的常用實(shí)現(xiàn)類(lèi)有ArrayList，LinkedList等
- Queue的常用實(shí)現(xiàn)類(lèi)有LinkedList，ArrayBlockingQueue等
- Map下沒(méi)有進(jìn)一步分類(lèi)，它的常用實(shí)現(xiàn)類(lèi)有HashMap，ConcurrentHashMap等
能把上面的基本框架答出來(lái)基本就沒(méi)問(wèn)題了，對(duì)于各種類(lèi)型我只列舉了一些實(shí)際工作中常用的實(shí)現(xiàn)類(lèi)。但其實(shí)在Set，List和Queue下還有更細(xì)的劃分，如果想要在面試時(shí)表現(xiàn)一番，那得對(duì)著JDK好好背一背了>_<
2. 請(qǐng)談一談Java集合中的fail-fast和fail-safe機(jī)制
fail-fast是一種錯(cuò)誤檢測(cè)機(jī)制，Java在適合單線程使用的集合容器中很好地實(shí)現(xiàn)了fail-fast機(jī)制，舉一個(gè)簡(jiǎn)單的例子：在多線程并發(fā)環(huán)境下，A線程在通過(guò)迭代器遍歷一個(gè)ArrayList集合，B線程同時(shí)對(duì)該集合進(jìn)行增刪元素操作，這個(gè)時(shí)候線程A就會(huì)拋出并發(fā)修改異常，中斷正常執(zhí)行的邏輯。
而fail-safe機(jī)制更像是一種對(duì)fail-fast機(jī)制的補(bǔ)充，它被廣泛地實(shí)現(xiàn)在各種并發(fā)容器集合中?；仡^看上面的例子，如果線程A遍歷的不是一個(gè)ArrayList，而是一個(gè)CopyOnWriteArrayList，則符合fail-safe機(jī)制，線程B可以同時(shí)對(duì)該集合的元素進(jìn)行增刪操作，線程A不會(huì)拋出任何異常。
要理解這兩種機(jī)制的表象，我們得了解這兩種機(jī)制背后的實(shí)現(xiàn)原理：
我們同樣用ArrayList解釋fail-fast背后的原理：首先ArrayList自身會(huì)維護(hù)一個(gè)modCount變量，每當(dāng)進(jìn)行增刪元素等操作時(shí)，modCount變量都會(huì)進(jìn)行自增。當(dāng)使用迭代器遍歷ArrayList時(shí)，迭代器會(huì)新維護(hù)一個(gè)初始值等于modCount的expectedModCount變量，每次獲取下一個(gè)元素的時(shí)候都會(huì)去檢查expectModCount和modCount是否相等。在上面舉的例子中，由于B線程增刪元素會(huì)導(dǎo)致modCount自增，當(dāng)A線程遍歷元素時(shí)就會(huì)發(fā)現(xiàn)兩個(gè)變量不等，從而拋出異常。
CopyOnWriteArrayList所實(shí)現(xiàn)的fail-safe在上述情況下沒(méi)有拋出異常，它的原理是：當(dāng)使用迭代器遍歷集合時(shí)，會(huì)基于原數(shù)組拷貝出一個(gè)新的數(shù)組（ArrayList的底層是數(shù)組），后續(xù)的遍歷行為在新數(shù)組上進(jìn)行。所以線程B同時(shí)進(jìn)行增刪操作不會(huì)影響到線程A的遍歷行為。
這種題目我覺(jué)得要先答出核心原理，如果你對(duì)多線程和單線程下容器的使用有自己的見(jiàn)解，可以考慮多聊點(diǎn)。
3. 如何一邊遍歷一邊刪除Collection中的元素？
使用集合迭代器自身的remove方法進(jìn)行刪除
Iterator<Integer> it = list.iterator(); while(it.hasNext()){ *// do something* it.remove(); }
可能筆試考的更多，算是Java的基本常識(shí)吧
List類(lèi)面試題
4. 談?wù)凙rrayList和LinkedList的區(qū)別
本質(zhì)的區(qū)別來(lái)源于兩者的底層實(shí)現(xiàn)：ArrayList的底層是數(shù)組，LinkedList的底層是雙向鏈表。
數(shù)組擁有O(1)的查詢效率，可以通過(guò)下標(biāo)直接定位元素；鏈表在查詢?cè)氐臅r(shí)候只能通過(guò)遍歷的方式查詢，效率比數(shù)組低。
數(shù)組增刪元素的效率比較低，通常要伴隨拷貝數(shù)組的操作；鏈表增刪元素的效率很高，只需要調(diào)整對(duì)應(yīng)位置的指針即可。
以上是數(shù)組和鏈表的通俗對(duì)比，在日常的使用中，兩者都能很好地在自己的適用場(chǎng)景發(fā)揮作用。
比如說(shuō)我們常常用ArrayList代替數(shù)組，因?yàn)榉庋b了許多易用的api，而且它內(nèi)部實(shí)現(xiàn)了自動(dòng)擴(kuò)容機(jī)制，由于它內(nèi)部維護(hù)了一個(gè)當(dāng)前容量的指針size，直接往ArrayList中添加元素的時(shí)間復(fù)雜度是O(1)的，使用非常方便。
而LinkedList常常被用作Queue隊(duì)列的實(shí)現(xiàn)類(lèi)，由于底層是雙向鏈表，能夠輕松地提供先入先出的操作。
我覺(jué)得可以分兩部分答，一個(gè)是數(shù)組與鏈表底層實(shí)現(xiàn)的不同，另一個(gè)是答ArrayList和LinkedList的實(shí)現(xiàn)細(xì)節(jié)。
5. 談?wù)凙rrayList和Vector的區(qū)別
兩者的底層實(shí)現(xiàn)相似，關(guān)鍵的不同在于Vector的對(duì)外提供操作的方法都是用synchronized修飾的，也就是說(shuō)Vector在并發(fā)環(huán)境下是線程安全的，而ArrayList在并發(fā)環(huán)境下可能會(huì)出現(xiàn)線程安全問(wèn)題。
由于Vector的方法都是同步方法，執(zhí)行起來(lái)會(huì)在同步上消耗一定的性能，所以在單線程環(huán)境下，Vector的性能是不如ArrayList的
除了線程安全這點(diǎn)本質(zhì)區(qū)別外，還有一個(gè)實(shí)現(xiàn)上的小細(xì)節(jié)區(qū)別：ArrayList每次擴(kuò)容的大小為原來(lái)的1.5倍；Vector可以指定擴(kuò)容的大小，默認(rèn)是原來(lái)大小的兩倍。
感覺(jué)可以順帶談?wù)劧嗑€程環(huán)境下ArrayList的替代品，比如CopyOnWriteArrayList，但是要談?wù)剝?yōu)缺點(diǎn)。
6. 為什么ArrayList的elementData數(shù)組要加上transient修飾
由于ArrayList有自動(dòng)擴(kuò)容機(jī)制，所以ArrayList的elementData數(shù)組大小往往比現(xiàn)有的元素?cái)?shù)量大，如果不加transient直接序列化的話會(huì)把數(shù)組中空余的位置也序列化了，浪費(fèi)不少的空間。
ArrayList中重寫(xiě)了序列化和反序列化對(duì)應(yīng)的writeObject和readObject方法，在遍歷數(shù)組元素時(shí)，以size作為結(jié)束標(biāo)志，只序列化ArrayList中已經(jīng)存在的元素。
細(xì)節(jié)題
Map類(lèi)面試題
HashMap死亡連環(huán)Call即將來(lái)臨，看爽了記得點(diǎn)個(gè)贊啊
7. 請(qǐng)介紹一下HashMap的實(shí)現(xiàn)原理
- 我們一般用HashMap存儲(chǔ)key-value類(lèi)型的數(shù)據(jù)，它的底層是一個(gè)數(shù)組，當(dāng)我們調(diào)用put方法的時(shí)候，首先會(huì)對(duì)key進(jìn)行計(jì)算得出一個(gè)hash值，然后根據(jù)hash值計(jì)算出存放在數(shù)組上的位置
- 這個(gè)時(shí)候我們會(huì)遇到兩種情況：一是數(shù)組上該位置為空，可以直接放入數(shù)據(jù)；還有一種情況是該位置已經(jīng)存放值了，這就發(fā)生了哈希沖突。
- 在現(xiàn)在使用較為普遍的JDK1.8中是這樣處理哈希沖突的：先用鏈表把沖突的元素串起來(lái)，如果鏈表的長(zhǎng)度達(dá)到了8，并且哈希表的長(zhǎng)度大于64，則把鏈表轉(zhuǎn)為紅黑樹(shù)。（在JDK1.7中沒(méi)有轉(zhuǎn)化為紅黑樹(shù)這一步，只用鏈表解決沖突）
先熱身
8. HashMap是怎樣確定key存放在數(shù)組的哪個(gè)位置的？
JDK1.8
首先計(jì)算key的hash值，計(jì)算過(guò)程是：先得到key的hashCode（int類(lèi)型，4字節(jié)），然后把hashCode的高16位與低16位進(jìn)行異或，得到key的hash值。
接下來(lái)用key的hash值與數(shù)組長(zhǎng)度減一的值進(jìn)行按位與操作，得到key在數(shù)組中對(duì)應(yīng)的下標(biāo)。
追問(wèn)：為什么計(jì)算key的hash時(shí)要把hashCode的高16位與低16位進(jìn)行異或？（變式：為什么不直接用key的hashCode）
計(jì)算key在數(shù)組中的下標(biāo)時(shí)，是通過(guò)hash值與數(shù)組長(zhǎng)度減一的值進(jìn)行按位與操作的。由于數(shù)組的長(zhǎng)度通常不會(huì)超過(guò)2^16，所以hash值的高16位通常參與不了這個(gè)按位與操作。
為了讓hashCode的高16位能夠參與到按位與操作中，所以把hashCode的高16位與低16位進(jìn)行異或操作，使得高16位的影響能夠均勻稀釋到低16位中，使得計(jì)算key位置的操作能夠充分散列均勻。
9. 為什么要把鏈表轉(zhuǎn)為紅黑樹(shù)，閾值為什么是8？
在極端情況下，比如說(shuō)key的hashCode()返回的值不合理，或者多個(gè)密鑰共享一個(gè)hashCode，很有可能會(huì)在同一個(gè)數(shù)組位置產(chǎn)生嚴(yán)重的哈希沖突。
這種情況下，如果我們?nèi)匀皇褂檬褂面湵戆讯鄠€(gè)沖突的元素串起來(lái)，這些元素的查詢效率就會(huì)從O(1)下降為O(N)。為了能夠在這種極端情況下仍保證較為高效的查詢效率，HashMap選擇把鏈表轉(zhuǎn)換為紅黑樹(shù)，紅黑樹(shù)是一種常用的平衡二叉搜索樹(shù)，添加，刪除，查找元素等操作的時(shí)間復(fù)雜度均為O(logN)
至于閾值為什么是8，這是HashMap的作者根據(jù)概率論的知識(shí)得到的。當(dāng)key的哈希碼分布均勻時(shí)，數(shù)組同一個(gè)位置上的元素?cái)?shù)量是成泊松分布的，同一個(gè)位置上出現(xiàn)8個(gè)元素的概率已經(jīng)接近千分之一了，這側(cè)面說(shuō)明如果鏈表的長(zhǎng)度達(dá)到了8，key的hashCode()肯定是出了大問(wèn)題，這個(gè)時(shí)候需要紅黑樹(shù)來(lái)保證性能，所以選擇8作為閾值。
追問(wèn)：為什么紅黑樹(shù)轉(zhuǎn)換回鏈表的閾值不是7而是6呢？
如果是7的話，那么鏈表和紅黑樹(shù)之間的切換范圍值就太小了。如果我的鏈表長(zhǎng)度不停地在7和8之間切換，那豈不是得來(lái)回變換形態(tài)？所以選擇6是一種折中的考慮。
10. 請(qǐng)說(shuō)一下HashMap的擴(kuò)容原理
- 首先得到新的容量值和新的擴(kuò)容閾值，默認(rèn)都是原來(lái)大小的兩倍。
- 然后根據(jù)新容量創(chuàng)建新的數(shù)組
- 最后把元素從舊數(shù)組中遷移到新數(shù)組中
在JDK1.7中，遷移數(shù)據(jù)的時(shí)候所有元素都重新計(jì)算了hash，并根據(jù)新的hash重新計(jì)算數(shù)組中的位置。
在JDK1.8中，這個(gè)過(guò)程進(jìn)行了優(yōu)化：如果當(dāng)前節(jié)點(diǎn)是單獨(dú)節(jié)點(diǎn)（后面沒(méi)有接著鏈表），則根據(jù)該節(jié)點(diǎn)的hash值與新容量減一的值按位與得到新的地址。
如果當(dāng)前節(jié)點(diǎn)后面帶有鏈表，則根據(jù)每個(gè)節(jié)點(diǎn)的hash值與舊數(shù)組容量進(jìn)行按位與的結(jié)果進(jìn)行劃分。如果得到的值為0，這些元素會(huì)被分配回原來(lái)的位置；如果得到的結(jié)果不為0，則分配到新位置，新位置的下標(biāo)為當(dāng)前位置下標(biāo)加上舊數(shù)組容量。
還有一種情況是當(dāng)前節(jié)點(diǎn)是樹(shù)節(jié)點(diǎn)，那么會(huì)調(diào)用一個(gè)專門(mén)的拆分方法進(jìn)行拆分。
追問(wèn)：為什么HashMap不支持動(dòng)態(tài)縮容？
開(kāi)放性題目？以下是個(gè)人見(jiàn)解：
如果要支持動(dòng)態(tài)縮容，可能就要把縮容安排在remove方法里，這樣可能會(huì)導(dǎo)致remove方法的時(shí)間復(fù)雜度從O(1)上升為O(N)。
還有一點(diǎn)可能和我們編寫(xiě)Java代碼的習(xí)慣有關(guān)：由于Java有自動(dòng)垃圾回收機(jī)制，讓我們得以可勁地new對(duì)象，Java也默認(rèn)了我們這種吃飯不收拾盤(pán)子的行為。既然對(duì)象會(huì)被回收，HashMap動(dòng)態(tài)縮容在這樣的大環(huán)境下似乎就顯得沒(méi)那么重要了，這可以說(shuō)是一種空間換時(shí)間的策略吧。
11. 為什么HashMap中適合用Integer，String這樣的基礎(chǔ)類(lèi)型作為key？
因?yàn)檫@些基礎(chǔ)類(lèi)內(nèi)部已經(jīng)重寫(xiě)了hashCode和equals方法，遵守了HashMap內(nèi)部的規(guī)范。
追問(wèn)：如果要用我們自己實(shí)現(xiàn)的類(lèi)作為key，要注意什么？
一定要重寫(xiě)hashCode()和equals()方法，而且要遵從以下規(guī)則：
equals()是我們判斷兩個(gè)對(duì)象是否相同的依據(jù)，如果我們重寫(xiě)了equals方法，用自己的邏輯去判斷兩個(gè)對(duì)象是否相同，那么一定要保證：
兩個(gè)equals()返回true的對(duì)象，一定要返回相同的hashCode。
這樣，在HashMap的put方法中才能正確判斷key是否相同。
不是經(jīng)常有一個(gè)問(wèn)題嘛，兩個(gè)對(duì)象hashCode相同，equals一定返回true嗎？答案肯定是否的，這和你的設(shè)計(jì)密切相關(guān)：如果在你的編程思路中這兩個(gè)對(duì)象是不同的，那么就算恰巧兩個(gè)對(duì)象的hashCode相同，equals也應(yīng)該返回false。
12. 為什么HashMap數(shù)組的長(zhǎng)度是2的冪次方？
因?yàn)檫@樣能夠提高根據(jù)key計(jì)算數(shù)組位置的效率。
HashMap根據(jù)key計(jì)算數(shù)組位置的算法是：用key的hash值與數(shù)組長(zhǎng)度減1的值進(jìn)行按位與操作。
在我們正常人的思維中，獲取數(shù)組的某個(gè)位置最直接的方法是對(duì)數(shù)組的長(zhǎng)度取余數(shù)。但是如果被除數(shù)是2的冪次方，那么這個(gè)對(duì)數(shù)組長(zhǎng)度取余的方法就等價(jià)于對(duì)數(shù)組長(zhǎng)度減一的值進(jìn)行按位與操作。
在計(jì)算機(jī)中，位運(yùn)算的效率遠(yuǎn)高于取模運(yùn)算，所以為了提高效率，把數(shù)組的長(zhǎng)度設(shè)為2的冪次方。
13. HashMap與HashTable有什么區(qū)別？
在JDK1.7之前，兩者的實(shí)現(xiàn)極為相似，最大的區(qū)別在于HashTable的方法都用synchronized關(guān)鍵字修飾起來(lái)了，表明它是線程安全的。
但是由于直接在方法上加synchronized關(guān)鍵字的同步效率較低，在并發(fā)情況下，官方推薦我們使用ConcurrentHashMap。
所以我們看到在JDK1.8中，官方甚至沒(méi)有對(duì)HashTable進(jìn)行鏈表轉(zhuǎn)樹(shù)這樣的優(yōu)化，HashTable已經(jīng)不被推薦使用了。
14. 請(qǐng)說(shuō)一下ConcurrentHashMap的實(shí)現(xiàn)原理
在JDK1.7中ConcurrentHashMap采用了一種分段鎖的機(jī)制，它的底層實(shí)現(xiàn)是一個(gè)segment數(shù)組，每個(gè)segment的底層結(jié)構(gòu)和HashMap相似，也是數(shù)組加鏈表。
當(dāng)對(duì)segment里面的元素進(jìn)行操作之前，需要獲得該segment獨(dú)有的一把ReentrantLock。ConcurrentHashMap如果不進(jìn)行手動(dòng)設(shè)置的話，默認(rèn)有16個(gè)segment，可以支持16個(gè)線程對(duì)16個(gè)不同的segment進(jìn)行并發(fā)寫(xiě)操作。
在JDK1.8之后摒棄了segment這種臃腫的設(shè)計(jì)，新的實(shí)現(xiàn)和HashMap非常相似，底層用的也是數(shù)組加鏈表加紅黑樹(shù)。
在新實(shí)現(xiàn)中，在put方法里使用了CAS + synchronized進(jìn)行同步。如果插入元素的位置為空，則使用CAS進(jìn)行插入。如果插入的位置不為空，則對(duì)當(dāng)前位置的對(duì)象進(jìn)行加鎖，也就鏈表或紅黑樹(shù)的頭節(jié)點(diǎn)，加鎖后再進(jìn)行后續(xù)的插入操作。
這樣設(shè)計(jì)的好處是：
- CAS是十分輕量的加鎖操作，如果能夠直接插入，用CAS能夠大幅度節(jié)省加鎖的開(kāi)銷(xiāo)。
- 如果發(fā)生沖突，只用鎖住當(dāng)前位置的頭結(jié)點(diǎn)，理論上數(shù)組的長(zhǎng)度有多大，并發(fā)操作的線程數(shù)就能有多少，比原來(lái)只能有16個(gè)線程效率更高。
這道題如果想深挖擴(kuò)展可以開(kāi)始往Java多線程并發(fā)方面扯：synchronized，CAS。Java多線程方面我也會(huì)出一份總結(jié)，有興趣的不妨先點(diǎn)贊關(guān)注一波
