提起ArrayList,相信很多小伙伴都用過，而且還不少用。但在幾年之前，我在一場(chǎng)面試中，面試官要求說(shuō)出ArrayList的擴(kuò)容機(jī)制。很顯然，那個(gè)時(shí)候的我并沒有關(guān)注這些，從而錯(cuò)過了一次機(jī)會(huì)。不過好在我還算比較喜歡搞事情的，所以今天這篇文章也算是填坑吧。看完這邊文章你將了解到：

ArrayList底層實(shí)現(xiàn) ArrayList為什么允許null值 ArrayList為什么可重復(fù) ArrayList查詢效率和插入效率對(duì)比 類圖

下圖是ArrayList的類圖結(jié)構(gòu)

ArrayList繼承于 AbstractList，實(shí)現(xiàn)了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口。這里逐個(gè)分析一下這里接口的意義：

RandomAccess是一個(gè)標(biāo)志接口，表明實(shí)現(xiàn)這個(gè)這個(gè)接口的 List集合是支持快速隨機(jī)訪問的。有興趣可以看看Collections類中哪個(gè)方法用到了這個(gè)標(biāo)志性接口。 實(shí)現(xiàn) Cloneable接口并覆蓋了方法clone()，能被克隆。 實(shí)現(xiàn)了java.io.Serializable 接口，這意味著ArrayList支持序列化，能通過序列化去傳輸（請(qǐng)注意，ArrayList的序列化是有點(diǎn)小特殊的，后面會(huì)講解）。 源碼解析

成員變量在正式進(jìn)入源碼分析之前，我們有必要先看看它的成員變量都有哪些，這里列舉比較重要的成員變量：

private int size; // 實(shí)際元素個(gè)數(shù)transient Object[] elementData; //真正保存元素的數(shù)組private static final int DEFAULT_CAPACITY = 10;//默認(rèn)的初始容量大小

構(gòu)造方法我們有三種初始化辦法：無(wú)參數(shù)直接初始化、指定大小初始化、指定初始數(shù)據(jù)初始化，源碼如下:

//1、無(wú)參數(shù)直接初始化，數(shù)組大小為空public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//2、指定初始數(shù)據(jù)初始化public ArrayList(Collection<? extends E> c){ //elementData是保存數(shù)組的容器，默認(rèn)為null elementData=c.toArray(); //如果給定的集合（c)數(shù)據(jù)有值 if((size=elementData.length)!=0){ //c.toArray might(incorrectly)not return Object[](see 6260652) //如果集合元素類型不是Object類型，我們會(huì)轉(zhuǎn)成Object if(elementData.getClass()!=Object[].class){ elementData=Arrays.copyOf(elementData,size,Object].class); } }else{ //給定集合（c)無(wú)值，則默認(rèn)空數(shù)組 this.elementData=EMPTY_ELEMENTDATA }}//3、指定初始容量public ArrayList(int initialCapacity) {//指定的初始容量大于0，將elementData初始化為指定大小的數(shù)組 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //否則初始化成一個(gè)空數(shù)組 this.elementData = EMPTY_ELEMENTDATA; }}

除過源碼中注釋外，補(bǔ)充幾點(diǎn)：

ArrayList無(wú)參構(gòu)造器初始化時(shí)，默認(rèn)大小是空數(shù)組，并不是大家常說(shuō)的10,10是在第一次add的時(shí)候擴(kuò)容的數(shù)組值。 使用方式二進(jìn)行創(chuàng)建對(duì)象時(shí)，如果入?yún)⑷萜鞅４娴膶?duì)象不是Object，則轉(zhuǎn)換為Object。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA又是什么鬼？它其實(shí)是定義在成員變量的兩個(gè)空數(shù)組，

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};private static final Object[] EMPTY_ELEMENTDATA = {};

很明顯問題來(lái)了，既然都是空數(shù)組，為什么要聲明兩個(gè)？一個(gè)不行嗎？讀者請(qǐng)先思考一下，帶著疑問往下看。

新增和擴(kuò)容實(shí)現(xiàn)

通過構(gòu)造方法可以很清楚的看到，ArrayList的確是基于數(shù)組的，但動(dòng)態(tài)又從何說(shuō)起？新增時(shí)就是給數(shù)組中添加元素，主要分為兩步走：

判斷是否需要擴(kuò)容，如果需要擴(kuò)容執(zhí)行擴(kuò)容操作； 直接賦值。

對(duì)應(yīng)源碼如下：

public boolean add(E e) {//確保數(shù)組大小是否足夠，不夠執(zhí)行擴(kuò)容，size為當(dāng)前數(shù)組元素個(gè)數(shù)，判斷size+1是因?yàn)楹竺孢€要size++ ensureCapacityInternal(size + 1); //1 elementData[size++] = e;//2 return true;}

我們先來(lái)看一下擴(kuò)容部分的源碼：

private void ensureCapacityInternal(int minCapacity) {//先調(diào)用calculateCapacity計(jì)算容量 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果當(dāng)前數(shù)組還是個(gè)空數(shù)組，也就是他用過無(wú)參構(gòu)造去初始化的 //那么直接返回DEFAULT_CAPACITY，即10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;}private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果當(dāng)前容量已經(jīng)大于當(dāng)前數(shù)組的長(zhǎng)度了，說(shuō)明需要去擴(kuò)容了 if (minCapacity - elementData.length > 0) //擴(kuò)容 grow(minCapacity);}private void grow(int minCapacity){ int oldCapacity = elementData.length; //oldCapacity>>1是把oldCapacity除以2的意思 int newCapacity=oldCapacity+(oldCapacity>>1); //如果擴(kuò)容后的值<我們的期望值，擴(kuò)容后的值就等于我們的期望值 if(newCapacity-minCapacity<0) newCapacity = minCapacity; //如果擴(kuò)容后的值>jvm所能分配的數(shù)組的最大值，那么就用Integer的最大值 if(newCapacity-MAX_ARRAY_SIZE>0) elementData=Arrays.copyOf(elementData,newCapacity);}

注釋相對(duì)來(lái)說(shuō)已經(jīng)比較詳細(xì)了，這里需要注意以下幾點(diǎn)：

上面有個(gè)問題是為什么需要聲明兩個(gè)空數(shù)組。我們?cè)诳吹缴厦嬖创a的時(shí)候有一個(gè)方法為calculateCapacity，這個(gè)方法內(nèi)部邏輯只有在通過無(wú)參構(gòu)造初始化ArrayList的時(shí)候才會(huì)改變將要返回的minCapacity。而返回的這個(gè)值將會(huì)決定下面的數(shù)組是否需要擴(kuò)容。如果我們通過指定大小的方式初始化ArrayList并指定大小為0，這說(shuō)明我們需要的就是一個(gè)空的ArrayList，不需要去擴(kuò)容，你細(xì)品； 新增時(shí)，沒有對(duì)值進(jìn)行校驗(yàn)，所以新增值可以為null，且沒有做重復(fù)值判斷，所以元素可以重復(fù)； ArrayList中的數(shù)組的最大值是Integer.MAX_VALUE，超過這個(gè)值，JVM就不會(huì)給數(shù)組分配內(nèi)存空間了； 擴(kuò)容是原來(lái)容量大小+容量大小的一半，簡(jiǎn)單說(shuō)就是擴(kuò)容后的大小是原來(lái)容量的1.5倍。

擴(kuò)容完成之后，就是簡(jiǎn)單的賦值了，賦值時(shí)并沒有加鎖，所以是線程不安全的。

擴(kuò)容的本質(zhì)

在grow方法的最后，擴(kuò)容是通過Arrays.copyOf(elementData,newCapacity);這行代碼實(shí)現(xiàn)的。這個(gè)方法實(shí)際上調(diào)用的方法是我們經(jīng)常使用的System.arraycopy：

/***@param src 被拷貝的數(shù)組*@param srcPos 從數(shù)組那里開始*@param dest 目標(biāo)數(shù)組*@param destPos從目標(biāo)數(shù)組那個(gè)索引位置開始拷貝*@param length 拷貝的長(zhǎng)度*此方法是沒有返回值的，通過dest的引用進(jìn)行傳值*/public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

這個(gè)方法是一個(gè)native方法，雖然不能看到方法內(nèi)部的具體實(shí)現(xiàn)，但通過參數(shù)也可以管中窺豹。這個(gè)方法會(huì)移動(dòng)元素。所以說(shuō)數(shù)組如果要擴(kuò)容，需要重新分配一塊更大的空間，再把數(shù)據(jù)全部復(fù)制過去，時(shí)間復(fù)雜度 O(N)；而且你如果想在數(shù)組中間進(jìn)行插入和刪除，每次必須搬移后面的所有數(shù)據(jù)以保持連續(xù)，時(shí)間復(fù)雜度 O(N)。由于數(shù)組又是一塊連續(xù)的內(nèi)存空間，能夠根據(jù)索引快速訪問元素。上面也就解釋了一開始那個(gè)問題：ArrayList為什么插入慢，查詢快。

刪除

ArrayList有多種刪除方法，這里以根據(jù)值刪除的方式進(jìn)行說(shuō)明(其他原理類似)：

public boolean remove(Object o) { //如果要?jiǎng)h除的值是null,刪除第一個(gè)是null的值 if(o==null){ for(int index=0;index<size;index++) if(elementData[index]==null){ fastRemove(index) return true; } }else{ //如果要?jiǎng)h除的值不為null,找到第一個(gè)和要?jiǎng)h除的值相等的刪除 for(int index=0;index<size;index++) //這里是根據(jù) equals來(lái)判斷值相等的，相等后再根據(jù)索引位置進(jìn)行刪除 //所以根據(jù)對(duì)象刪除時(shí)，一般來(lái)說(shuō)，如果你確定要?jiǎng)h除的是某一類的業(yè)務(wù)對(duì)象，則需要重寫equals if(o.equals(elementData[index]){ fastRemove(index) return true; } } return false}

核心其實(shí)是fastRemove方法：

private void fastRemove(int index){ //記錄數(shù)組的結(jié)構(gòu)要發(fā)生變動(dòng)了 nodCount++; //numMoved表示刪除index位置的元素后，需要從index后移動(dòng)多少個(gè)元素到前面去 //減1的原因，是因?yàn)閟ize從1開始算起，index從0開始算起 int numMoved=size-index-1; if(numMoved>0) //從index+1位置開始被拷貝，拷貝的起始位置是index,長(zhǎng)度是numMoved System.arraycopy(elementData, index+1, elementData, index, numMoved); //數(shù)組最后一個(gè)位置賦值null,幫助GC(沒有引用則自動(dòng)回收了) elementData[--size] = null;}

從源碼中，我們可以看出，某一個(gè)元素被刪除后，為了維護(hù)數(shù)組結(jié)構(gòu)，我們都會(huì)把數(shù)組后面的元素往前移動(dòng)，同時(shí)釋放最后一個(gè)引用，便于回收。

總結(jié)

本文主要從ArrayList的源碼入手，分別從初始化、新增、擴(kuò)容、刪除四個(gè)方面展開學(xué)習(xí)。我們發(fā)現(xiàn)ArrayList內(nèi)部其實(shí)就是圍繞了一個(gè)數(shù)組，在數(shù)組容量不足時(shí)將數(shù)組擴(kuò)容至更大，所以也就自然被稱作基于動(dòng)態(tài)數(shù)組。微信搜索Java成神之路或掃描下方二維碼，發(fā)現(xiàn)更多Java有趣知識(shí)，讓我們一起成長(zhǎng)！

以上就是Java ArrayList使用總結(jié)的詳細(xì)內(nèi)容，更多關(guān)于Java ArrayList使用的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！