求求大廠給個Offer：List面試題

2020 年 8 月 21 日
筆記

前言

只有光頭才能變強。

文本已收錄至我的GitHub精選文章，歡迎Star：//github.com/ZhongFuCheng3y/3y

從今天開始，我，三歪，正式開始寫面試系列。我給這個面試系列取了一個名字，叫做《求求大廠給個Offer》

上一篇就叫做《求求大廠給個Offer：如何寫簡歷》

所以這篇文章叫做《求求大廠給個Offer：List面試題》

接下來就開始吧。

本文有配套的影片觀看：//www.bilibili.com/video/BV1nT4y1L71r/ 歡迎三連。

面試現場

面試官：「你簡單自我介紹一下吧」

三歪：「我叫三歪，目前維護一個公眾號叫做Java3y，這幾年寫了300+原創技術文章，近1000頁的原創電子書和多個知識點的思維導圖。我的願景是：只要關注我並三連的同學都可以拿到大廠offer。我的….」

面試官：「停停停，別吹了，我們正式開始吧。」

面試官：「來講講Java的List吧，你對List了解多少？」

三歪：「List在Java裡邊是一個介面，常見的實現類有ArrayList和LinkedList，在開發中用得最多的是ArrayList」

面試官：「你再分別來講講ArrayList和LinkedList的區別唄」

三歪：「ArrayList的底層數據結構是數組，LinkedList底層數據結構是鏈表。」

面試官：「那我們本身就有數組了，為什麼要用ArrayList呢？」

三歪：「原生的數組會有一個特點：你在使用的時候必須要為它創建大小，而ArrayList不用」

面試官：「那你說說ArrayList是怎麼實現的吧，為什麼ArrayList就不用創建大小呢？」

三歪：「其實是這樣的，我看過源碼。當我們new ArrayList()的時候，默認會有一個空的Object數組，大小為0。當我們第一次add添加數據的時候，會給這個數組初始化一個大小，這個大小默認值為10」

面試官：「嗯」

三歪：「還有就是，數組的大小是固定的，而ArrayList的大小是可變的」

面試官：「那怎麼理解固定和可變的呢？你說說看」

三歪：「假設我們給定數組的大小是10，要往這個數組裡邊填充元素，我們只能添加10個元素。而ArrayList不一樣，ArrayList我們在使用的時候可以往裡邊添加20個，30個，甚至更多的元素」

三歪：「因為ArrayList是實現了動態擴容的」

面試官：「那它是怎麼實現的呢？」

三歪：「使用ArrayList在每一次add的時候，它都會先去計算這個數組夠不夠空間，如果空間是夠的，那直接追加上去就好了。如果不夠，那就得擴容」

面試官：「那怎麼擴容？一次擴多少？」

三歪：「在源碼裡邊，有個grow方法，每一次擴原來的1.5倍。比如說，初始化的值是10嘛。現在我第11個元素要進來了，發現這個數組的空間不夠了，所以會擴到15」

三歪：「空間擴完容之後，會調用arraycopy來對數組進行拷貝」

面試官：「哦，可以的。那為什麼你在前面提到，在日常開發中用得最多的是ArrayList呢？」

三歪：「是由底層的數據結構來決定的，在日常開發中，遍歷的需求比增刪要多，即便是增刪也是往往在List的尾部添加就OK了。像在尾部添加元素，ArrayList的時間複雜度也就O(1)」

三歪：「另外的是，ArrayList的增刪底層調用的copyOf()被優化過，現代CPU對記憶體可以塊操作，ArrayList的增刪一點兒也不會比LinkedList慢」

面試官：「Vector你了解嗎？」

三歪：「嗯，Vector是底層結構是數組，一般現在我們已經很少用了。相對於ArrayList，它是執行緒安全的，在擴容的時候它是直接擴容兩倍的，比如現在有10個元素，要擴容的時候，就會將數組的大小增長到20」

面試官：「嗯，那如果我們不用Vector，執行緒安全的List還有什麼？」

三歪：「首先，我們也可以用Collections來將ArrayList來包裝一下，變成執行緒安全。但這肯定不是你想聽的，對吧。在java.util.concurrent包下還有一個類，叫做CopyOnWriteArrayList」

面試官：「嗯，你繼續說」

三歪：「要講CopyOnWriteArrayList之前，我還是想說說copy-on-write這個意思，下面我會簡稱為cow。比如說在Linux中，我們知道所有的進程都是init進程fork出來的，除了進程號之外，fork出來的進程，默認跟父進程一模一樣的。在fork之後exec之前，兩個進程用的是相同的記憶體空間的，這意味著子進程的程式碼段、數據段、堆棧都是指向父進程的物理空間」

面試官：「嗯」

三歪：「當父子進程中有更改的行為發生時，再為子進程分配相應物理空間。這樣做的好處就是，等到真正發生修改的時候，才去分配資源，可以減少分配或者複製大量資源時帶來的瞬間延時。簡單來說，就可以理解為我們的懶載入，或者說單例模式的懶漢式。等真正用到的時候再分配」

面試官：「嗯」

三歪：「在文件系統中，其實也有cow的機制。文件系統的cow就是在修改數據的時候，不會直接在原來的數據位置上進行操作，而是重新找個位置修改。比如說：要修改數據塊A的內容，先把A讀出來，寫到B塊裡面去。如果這時候斷電了，原來A的內容還在。這樣做的好處就是可以保證數據的完整性，瞬間掛掉了容易恢復。

三歪：「再回頭來看CopyOnWriteArrayList吧，CopyOnWriteArrayList是一個執行緒安全的List，底層是通過複製數組的方式來實現的。

三歪：「我來說說它的add()方法的實現吧」

面試官：「好」

三歪：「在add()方法其實他會加lock鎖，然後會複製出一個新的數組，往新的數組裡邊add真正的元素，最後把array的指向改變為新的數組」

三歪：「其實get()方法又或是size()方法只是獲取array所指向的數組的元素或者大小。讀不加鎖，寫加鎖」

三歪：「可以發現的是，CopyOnWriteArrayList跟文件系統的COW機制是很像的」

面試官：「那你能說說CopyOnWriteArrayList有什麼缺點嗎？」

三歪：「很顯然，CopyOnWriteArrayList是很耗費記憶體的，每次set()/add()都會複製一個數組出來，另外就是CopyOnWriteArrayList只能保證數據的最終一致性，不能保證數據的實時一致性。假設兩個執行緒，執行緒A去讀取CopyOnWriteArrayList的數據，還沒讀完，現在執行緒B把這個List給清空了，執行緒A此時還是可以把剩餘的數據給讀出來。」

面試官：「嗯，還可以，今天的面試就到這裡結束了，你有什麼想問我的嗎？」

三歪：「你覺得我今天的表現怎麼樣？」

面試官：「今天的表現還可以，如果這一次你沒有100個點贊，估計HR就不會再聯繫你了。如果超過100個點贊，第二輪好好表現吧。」

面試官：「給你透露一下，Map集合可以好好準備一下，下一輪將會考察Map的知識」

題外話

List集合總體來說不會太難，但CopyOnWriteArrayList可能很多同學還不知道有這麼一個類。

針對這次的面試可能你想了解更多List的細節，比如說ArrayList/LinkedList/CopyOnWriteArrayList的源碼以及上面提到的COW機制，可以在公眾號下回復「List」即可獲取我之前寫的原創文章。

需要預習或者領取電子書的同學，在公眾號下回復「888」即可獲取。

本文有配套的影片觀看：//www.bilibili.com/video/BV1nT4y1L71r/ 歡迎三連。

各類知識點總結

下面的文章都有對應的原創精美PDF，在持續更新中，可以來找我催更~

涵蓋Java後端所有知識點的開源項目（已有10K+ star）：

如果大家想要實時關注我更新的文章以及分享的乾貨的話，微信搜索Java3y。

PDF文檔的內容均為手打，有任何的不懂都可以直接來問我（公眾號有我的聯繫方式）。

我是三歪，一個想要變強的男人，感謝大家的點贊收藏和轉發，下期見。給三歪點個贊，對三歪真的非常重要！