小茵：要不今天來講講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)是鏈表晴氨。

image.png

小茵：那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我們?cè)谑褂玫臅r(shí)候可以往里邊添加20個(gè)，30個(gè)蓖宦，甚至更多的元素

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

image.png

小奧：大概的意思就是：

小奧：當(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)行拷貝

image.png

小茵：嗯...

小茵：那為什么你在前面提到苔货，在日常開發(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慢

image.png

小茵：Vector你了解嗎敢会？

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

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

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

image.png

小茵：嗯卧土，那如果我們不用Vector惫皱，線程安全的List還有什么？

小奧：首先尤莺，我們也可以用Collections來將ArrayList來包裝一下旅敷，變成線程安全。

小奧：但這肯定不是你想聽的颤霎，對(duì)吧媳谁。在java.util.concurrent包下還有一個(gè)類涂滴，叫做CopyOnWriteArrayList

小奧：要講CopyOnWriteArrayList之前，我還是想說說copy-on-write這個(gè)意思晴音，下面我會(huì)簡(jiǎn)稱為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í)夹供。

小奧：簡(jiǎn)單來說灵份，就可以理解為我們的懶加載，或者說單例模式的懶漢式哮洽。等真正用到的時(shí)候再分配

image.png

小茵：嗯

小奧：在文件系統(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ī)制是很像的

image.png

小茵：那你能說說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ù)給讀出來嘲更。

image.png

小茵：嗯...