面試官：要不今天來講講Java的List吧，你對List了解多少？
候選者：List在Java里邊是一個介面，常見的實作類有ArrayList和LinkedList，在開發中用得最多的是ArrayList
候選者：ArrayList的底層資料結構是陣列，LinkedList底層資料結構是鏈表，
面試官：那Java本身就有陣列了，為什么要用ArrayList呢？
候選者：原生的陣列會有一個特點：你在使用的時候必須要為它創建大小，而ArrayList不用，
候選者：在日常開發的時候，往往我們是不知道陣列的大小的
候選者：如果陣列的大小指定多了，記憶體浪費；如果陣列大小指定少了，裝不下，
候選者：假設我們給定陣列的大小是10，要往這個陣列里邊填充元素，我們只能添加10個元素，
候選者：而ArrayList不一樣，ArrayList我們在使用的時候可以往里邊添加20個，30個，甚至更多的元素
候選者：因為ArrayList是實作了動態擴容的
候選者：大概的意思就是：
候選者：當我們new ArrayList()的時候，默認會有一個空的Object陣列，大小為0，
候選者：當我們第一次add添加資料的時候，會給這個陣列初始化一個大小，這個大小默認值為10
候選者：使用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出來的行程，默認跟父行程一模一樣的，
候選者：當使用了cow機制；子行程在被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此時還是可以把剩余的資料給讀出來，
面試官：嗯，還可以，
【對線面試官-移動端】系列 一周兩篇持續更新中！
【對線面試官-電腦端】系列 一周兩篇持續更新中！
原創不易！！求三連！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/307233.html
標籤：java