送分題，ArrayList 的擴(kuò)容機(jī)制了解嗎？

最近在準(zhǔn)備暑期實(shí)習(xí)嘛，所以面經(jīng)刷的比較多，前幾天看見(jiàn)一位上岸的小伙伴寫(xiě)的面經(jīng)，他說(shuō)他在整理回顧知識(shí)點(diǎn)的時(shí)候（一般都用思維導(dǎo)圖吧），會(huì)把知識(shí)點(diǎn)寫(xiě)成疑問(wèn)句的形式，而不是陳述句，這樣你在看到這句話(huà)的時(shí)候，會(huì)去主動(dòng)的思考，而不是背誦。我這幾天做下來(lái)發(fā)現(xiàn)確實(shí)是這樣，這里安利給各位小伙伴。另外，本篇文章也會(huì)以問(wèn)答的形式引導(dǎo)全文的走向。

1. ArrayList 了解過(guò)嗎？它是啥？有啥用?

眾所周知，Java 集合框架擁有兩大接口 Collection 和 Map，其中，Collection 麾下三生子 List、Set 和 Queue。ArrayList 就實(shí)現(xiàn)了 List 接口，其實(shí)就是一個(gè)數(shù)組列表，不過(guò)作為 Java 的集合框架，它只能存儲(chǔ)對(duì)象引用類(lèi)型，也就是說(shuō)當(dāng)我們需要裝載的數(shù)據(jù)是諸如 int、float 等基本數(shù)據(jù)類(lèi)型的時(shí)候，必須把它們轉(zhuǎn)換成對(duì)應(yīng)的包裝類(lèi)。

ArrayList 的底層實(shí)現(xiàn)是一個(gè) Object 數(shù)組：

既然它是基于數(shù)組實(shí)現(xiàn)的，數(shù)組在內(nèi)存空間中是連續(xù)分配的，那必然查詢(xún)速率非常快，不過(guò)當(dāng)然也肯定逃不過(guò)增刪效率低的缺陷。

另外，和 ArrayList 一樣同樣實(shí)現(xiàn)了 List 接口的、我們比較常用的還有 LinkedList。LinkedList 比較特殊，它不僅實(shí)現(xiàn)了 List 接口，還實(shí)現(xiàn)了 Queue 接口，所以你可以看見(jiàn) LinkedList 經(jīng)常被當(dāng)作隊(duì)列使用：

Queue<Integer> queue = new LinkedList<>();

LinkedList 人如其名，它的底層自然是基于鏈表的，而且還是個(gè)雙向鏈表。鏈表的特性和數(shù)組正好是反的，由于沒(méi)有索引，所以查詢(xún)效率低，但是增刪速度快。

2. ArrayList 如何指定底層數(shù)組大小的？

OK，首先，既然咱真正存儲(chǔ)數(shù)據(jù)的地方是數(shù)組，那我們初始化 ArrayList 的時(shí)候自然要給數(shù)組分配一個(gè)大小，開(kāi)辟一個(gè)內(nèi)存空間。我們先來(lái)看看 ArrayList 的無(wú)參構(gòu)造函數(shù)：

可以看到，它為底層的 Object 數(shù)組也就是 elementData 賦值了一個(gè)默認(rèn)的空數(shù)組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是說(shuō)，使用無(wú)參構(gòu)造函數(shù)初始化 ArrayList 后，它當(dāng)時(shí)的數(shù)組容量為 0 。

這給咱初始化一個(gè)容量為 0 的數(shù)組有啥用？啥也存不了啊？別急，如果使用了無(wú)參構(gòu)造函數(shù)來(lái)初始化 ArrayList， 只有當(dāng)我們真正對(duì)數(shù)據(jù)進(jìn)行添加操作 add 時(shí)，才會(huì)給數(shù)組分配一個(gè)默認(rèn)的初始容量 DEFAULT_CAPACITY = 10。看下圖：

說(shuō)完了無(wú)參構(gòu)造，ArrayList 的有參構(gòu)造函數(shù)就是中規(guī)中矩了，按照用戶(hù)傳入的大小開(kāi)辟數(shù)組空間：

3. 數(shù)組的大小一旦被規(guī)定就無(wú)法改變，那 ArrayList 是怎么對(duì)底層數(shù)組進(jìn)行擴(kuò)容的？

ArrayList 的底層實(shí)現(xiàn)是 Object 數(shù)組，我們知道，數(shù)組的大小一旦被規(guī)定就無(wú)法改變。那如果我們不斷的往里面添加數(shù)據(jù)的話(huà)，ArrayList 是如何進(jìn)行擴(kuò)容的呢？或者說(shuō) ArrayList 是如何實(shí)現(xiàn)存放任意數(shù)量對(duì)象的呢？

OK，擴(kuò)容發(fā)生在啥時(shí)候？那肯定是我們往數(shù)組中新加入一個(gè)元素但是發(fā)現(xiàn)數(shù)組滿(mǎn)了的時(shí)候。沒(méi)錯(cuò)，我們?nèi)?add 方法中看看 ArrayList 是怎么做擴(kuò)容的：

ensureExplicitCapacity 判斷是否需要進(jìn)行擴(kuò)容，很顯然，grow 方法是擴(kuò)容的關(guān)鍵：

說(shuō)實(shí)話(huà)，別的都不用看了，看上面圖中的黃色框框就知道 ArrayList 是怎么擴(kuò)容的了：擴(kuò)容后的數(shù)組長(zhǎng)度 = 當(dāng)前數(shù)組長(zhǎng)度 + 當(dāng)前數(shù)組長(zhǎng)度 / 2。最后使用 Arrays.copyOf 方法直接把原數(shù)組中的數(shù)組 copy 過(guò)來(lái)，需要注意的是，Arrays.copyOf 方法會(huì)創(chuàng)建一個(gè)新數(shù)組然后再進(jìn)行拷貝。

舉個(gè)例子畫(huà)個(gè)圖來(lái)演示一下：

4. 既然擴(kuò)容發(fā)生在添加數(shù)據(jù)的時(shí)候，講講 ArrayList 具體是怎么添加數(shù)據(jù)的

OK，add 方法我們剛剛講了一半，添加數(shù)據(jù)前會(huì)先判斷一下是否需要擴(kuò)容，真正的添加數(shù)據(jù)的操作在下半部分：

先講下 add(int index, E element) 這個(gè)方法的含義，就是在指定索引 index 處插入元素 element。比如說(shuō) ArrayList.add(0, 3)，意思就是在頭部插入元素 3。

再來(lái)看看 add 方法的核心 System.arraycopy，這個(gè)方法有 5 個(gè)參數(shù)：

• elementData：源數(shù)組
• index：從源數(shù)組中的哪個(gè)位置開(kāi)始復(fù)制
• elementData：目標(biāo)數(shù)組
• index + 1：復(fù)制到目標(biāo)數(shù)組中的哪個(gè)位置
• size - index：要復(fù)制的源數(shù)組中數(shù)組元素的數(shù)量

解釋一下上面代碼中 arraycopy 的意思，舉個(gè)例子，我們想要在 index = 5 的位置插入元素，首先，我們會(huì)復(fù)制一遍源數(shù)組 elementData（這里我們稱(chēng)復(fù)制的數(shù)組為新數(shù)組吧），然后把源數(shù)組中從 index = 5 的位置開(kāi)始到數(shù)組末尾的元素，放到新數(shù)組的 index + 1 = 6 的位置上：

于是，這就給我們要新增的元素騰出了位置，然后在新數(shù)組 index = 5 的位置放入元素 element 就完成了添加的操作：

顯然，不用多說(shuō)，ArrayList 的將數(shù)據(jù)插入到指定位置的操作性能非常低下，因?yàn)橐_(kāi)辟新數(shù)組復(fù)制元素啊，要是涉及到擴(kuò)容那就更慢了。

另外，ArrayList 還內(nèi)置了一個(gè)直接在末尾添加元素的 add 方法，不用復(fù)制數(shù)組，直接 size ++ 就好，這個(gè)方法應(yīng)該是我們最常使用的：

5. ArrayList 又是如何刪除數(shù)據(jù)的呢？

Ctrl + F 找到 remove 方法，就這？和添加一個(gè)道理，也是復(fù)制數(shù)組

舉個(gè)例子，假設(shè)我們要?jiǎng)h除數(shù)組的 index = 5 的元素，首先，我們會(huì)復(fù)制一遍源數(shù)組，然后把源數(shù)組中從 index + 1 = 6 的位置開(kāi)始到數(shù)組末尾的元素，放到新數(shù)組的 index  = 5 的位置上：

也就是說(shuō) index = 5 的元素直接被覆蓋掉了，給了你被刪除的感覺(jué)。同樣的，它的效率自然也是十分低下的

6. ArrayList 是線(xiàn)程安全的嗎？不安全的表現(xiàn)

ArrayList 和 LinkedList 都不是線(xiàn)程安全的，我們以在末尾添加元素的 add 方法為例，來(lái)看看 ArrayList 線(xiàn)程不安全的表現(xiàn)是啥：

黃色框里的并不是一個(gè)原子操作，它由兩步操作構(gòu)成：

elementData[size] = e;
size = size + 1;

在單線(xiàn)程執(zhí)行這兩條代碼時(shí)，那當(dāng)然沒(méi)有任何問(wèn)題，但是當(dāng)多線(xiàn)程環(huán)境下執(zhí)行時(shí)，可能就會(huì)發(fā)生一個(gè)線(xiàn)程添加的值覆蓋另一個(gè)線(xiàn)程添加的值。舉個(gè)例子：

• 假設(shè) size = 0，我們要往這個(gè)數(shù)組的末尾添加元素
• 線(xiàn)程 A 開(kāi)始添加一個(gè)元素，值為 A。此時(shí)它執(zhí)行第一條操作，將 A 放在了數(shù)組 elementData 下標(biāo)為 0 的位置上
• 接著線(xiàn)程 B 剛好也要開(kāi)始添加一個(gè)值為 B 的元素，且走到了第一步操作。此時(shí)線(xiàn)程 B 獲取到的 size 值依然為 0，于是它將 B 也放在了 elementData 下標(biāo)為 0 的位置上
• 線(xiàn)程 A 開(kāi)始增加 size 的值，size = 1
• 線(xiàn)程 B 開(kāi)始增加 size 的值，size = 2

這樣，線(xiàn)程 A、B 都執(zhí)行完畢后，理想的情況應(yīng)該是 size = 2，elementData[0] = A，elementData[1] = B。而實(shí)際情況變成了 size = 2，elementData[0] = B（線(xiàn)程 B 覆蓋了線(xiàn)程 A 的操作），下標(biāo) 1 的位置上什么都沒(méi)有。并且后續(xù)除非我們使用 set 方法修改下標(biāo)為 1 的值，否則這個(gè)位置上將一直為 null，因?yàn)樵谀┪蔡砑釉貢r(shí)將會(huì)從 size = 2 的位置上開(kāi)始。

上段代碼驗(yàn)證下：

結(jié)果和我們分析的一樣：

ArrayList 的線(xiàn)程安全版本是 Vector，它的實(shí)現(xiàn)很簡(jiǎn)單，就是把所有的方法統(tǒng)統(tǒng)加上 synchronized：

既然它需要額外的開(kāi)銷(xiāo)來(lái)維持同步鎖，所以理論上來(lái)說(shuō)它要比 ArrayList 要慢。

7. 為什么線(xiàn)程不安全還要用它呢？

因?yàn)樵诖蠖鄶?shù)場(chǎng)景中，查詢(xún)的情況居多，不會(huì)涉及太頻繁的增刪。那如果真的涉及頻繁的增刪，可以使用LinkedList，底層鏈表實(shí)現(xiàn)，為增刪而生。而如果你非得保證線(xiàn)程安全那就使用 Vector。當(dāng)然實(shí)際開(kāi)發(fā)中使用最多的還是 ArrayList，雖然線(xiàn)程不安全、增刪效率低，但是查詢(xún)效率高啊。

公眾號(hào)開(kāi)通較晚，暫無(wú)留言功能。各位可以點(diǎn)擊下方鏈接進(jìn)行留言

點(diǎn)擊進(jìn)入小牛肉的留言板 ??