面試官：要不今天來講講Java的List吧，你對(duì)List了解多少？

候選者：List在Java里邊是一個(gè)接口，常見的實(shí)現(xiàn)類有ArrayList和LinkedList，在開發(fā)中用得最多的是ArrayList

候選者：ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，LinkedList底層數(shù)據(jù)結(jié)構(gòu)是鏈表。

面試官：那Java本身就有數(shù)組了，為什么要用ArrayList呢？

候選者：原生的數(shù)組會(huì)有一個(gè)特點(diǎn)：你在使用的時(shí)候必須要為它創(chuàng)建大小，而ArrayList不用。

候選者：在日常開發(fā)的時(shí)候，往往我們是不知道數(shù)組的大小的

候選者：如果數(shù)組的大小指定多了，內(nèi)存浪費(fèi)；如果數(shù)組大小指定少了，裝不下。

候選者：假設(shè)我們給定數(shù)組的大小是10，要往這個(gè)數(shù)組里邊填充元素，我們只能添加10個(gè)元素。

候選者：而ArrayList不一樣，ArrayList我們在使用的時(shí)候可以往里邊添加20個(gè)，30個(gè)，甚至更多的元素

候選者：因?yàn)锳rrayList是實(shí)現(xiàn)了動(dòng)態(tài)擴(kuò)容的

候選者：大概的意思就是：

候選者：當(dāng)我們new ArrayList()的時(shí)候，默認(rèn)會(huì)有一個(gè)空的Object數(shù)組，大小為0。

候選者：當(dāng)我們第一次add添加數(shù)據(jù)的時(shí)候，會(huì)給這個(gè)數(shù)組初始化一個(gè)大小，這個(gè)大小默認(rèn)值為10

候選者：使用ArrayList在每一次add的時(shí)候，它都會(huì)先去計(jì)算這個(gè)數(shù)組夠不夠空間

候選者：如果空間是夠的，那直接追加上去就好了。如果不夠，那就得擴(kuò)容

面試官：那怎么擴(kuò)容？一次擴(kuò)多少？

候選者：在源碼里邊，有個(gè)grow方法，每一次擴(kuò)原來的1.5倍。比如說，初始化的值是10嘛。

候選者：現(xiàn)在我第11個(gè)元素要進(jìn)來了，發(fā)現(xiàn)這個(gè)數(shù)組的空間不夠了，所以會(huì)擴(kuò)到15

候選者：空間擴(kuò)完容之后，會(huì)調(diào)用arraycopy來對(duì)數(shù)組進(jìn)行拷貝

面試官：哦，可以的。

面試官：那為什么你在前面提到，在日常開發(fā)中用得最多的是ArrayList呢？

候選者：是由底層的數(shù)據(jù)結(jié)構(gòu)來決定的，在日常開發(fā)中，遍歷的需求比增刪要多，即便是增刪也是往往在List的尾部添加就OK了。

候選者：像在尾部添加元素，ArrayList的時(shí)間復(fù)雜度也就O(1)

候選者：另外的是，ArrayList的增刪底層調(diào)用的copyOf()被優(yōu)化過

候選者：現(xiàn)代CPU對(duì)內(nèi)存可以塊操作，ArrayList的增刪一點(diǎn)兒也不會(huì)比LinkedList慢

面試官：Vector你了解嗎？

候選者：嗯，Vector是底層結(jié)構(gòu)是數(shù)組，一般現(xiàn)在我們已經(jīng)很少用了。

候選者：相對(duì)于ArrayList，它是線程安全的，在擴(kuò)容的時(shí)候它是直接擴(kuò)容兩倍的

候選者：比如現(xiàn)在有10個(gè)元素，要擴(kuò)容的時(shí)候，就會(huì)將數(shù)組的大小增長到20

面試官：嗯，那如果我們不用Vector，線程安全的List還有什么？

候選者：首先，我們也可以用Collections來將ArrayList來包裝一下，變成線程安全。

候選者：但這肯定不是你想聽的，對(duì)吧。在java.util.concurrent包下還有一個(gè)類，叫做CopyOnWriteArrayList

候選者：要講CopyOnWriteArrayList之前，我還是想說說copy-on-write這個(gè)意思，下面我會(huì)簡稱為cow。

候選者：比如說在Linux中，我們知道所有的進(jìn)程都是init進(jìn)程fork出來的

候選者：除了進(jìn)程號(hào)之外，fork出來的進(jìn)程，默認(rèn)跟父進(jìn)程一模一樣的。

候選者：當(dāng)使用了cow機(jī)制；子進(jìn)程在被fork之后exec之前，兩個(gè)進(jìn)程用的是相同的內(nèi)存空間的

候選者：這意味著子進(jìn)程的代碼段、數(shù)據(jù)段、堆棧都是指向父進(jìn)程的物理空間

候選者：當(dāng)父子進(jìn)程中有更改的行為發(fā)生時(shí)，再為子進(jìn)程分配相應(yīng)物理空間。

候選者：這樣做的好處就是，等到真正發(fā)生修改的時(shí)候，才去分配資源，可以減少分配或者復(fù)制大量資源時(shí)帶來的瞬間延時(shí)。

候選者：簡單來說，就可以理解為我們的懶加載，或者說單例模式的懶漢式。等真正用到的時(shí)候再分配

面試官：嗯

候選者：在文件系統(tǒng)中，其實(shí)也有cow的機(jī)制。

候選者：文件系統(tǒng)的cow就是在修改數(shù)據(jù)的時(shí)候，不會(huì)直接在原來的數(shù)據(jù)位置上進(jìn)行操作，而是重新找個(gè)位置修改。

候選者：比如說：要修改數(shù)據(jù)塊A的內(nèi)容，先把A讀出來，寫到B塊里面去。

候選者：如果這時(shí)候斷電了，原來A的內(nèi)容還在。這樣做的好處就是可以保證數(shù)據(jù)的完整性，瞬間掛掉了容易恢復(fù)。

候選者：再回頭來看CopyOnWriteArrayList吧，CopyOnWriteArrayList是一個(gè)線程安全的List，底層是通過復(fù)制數(shù)組的方式來實(shí)現(xiàn)的。

候選者：我來說說它 的add()方法的實(shí)現(xiàn)吧

面試官：好

候選者：在add()方法其實(shí)他會(huì)加lock鎖，然后會(huì)復(fù)制出一個(gè)新的數(shù)組，往新的數(shù)組里邊add真正的元素，最后把a(bǔ)rray的指向改變?yōu)樾碌臄?shù)組

候選者：get()方法又或是size()方法只是獲取array所指向的數(shù)組的元素或者大小。讀不加鎖，寫加鎖

候選者：可以發(fā)現(xiàn)的是，CopyOnWriteArrayList跟文件系統(tǒng)的COW機(jī)制是很像的

面試官：那你能說說CopyOnWriteArrayList有什么缺點(diǎn)嗎？

候選者：很顯然，CopyOnWriteArrayList是很耗費(fèi)內(nèi)存的，每次set()/add()都會(huì)復(fù)制一個(gè)數(shù)組出來

候選者：另外就是CopyOnWriteArrayList只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。

候選者：假設(shè)兩個(gè)線程，線程A去讀取CopyOnWriteArrayList的數(shù)據(jù)，還沒讀完

候選者：現(xiàn)在線程B把這個(gè)List給清空了，線程A此時(shí)還是可以把剩余的數(shù)據(jù)給讀出來。

面試官：嗯，還可以。

對(duì)線面試官PDF版本，可+V: java3yyy 免費(fèi)領(lǐng)取