關(guān)于ArrayList的幾大問(wèn)題，看完還不懂來(lái)打我！
時(shí)間：2021-08-13 17:06:50
關(guān)鍵字：
ArrayList
集合
數(shù)據(jù)結(jié)構(gòu)
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]前言ArrayList是Java集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自AbstractList，實(shí)現(xiàn)了List接口。底層基于數(shù)組實(shí)現(xiàn)容量大小動(dòng)態(tài)變化。一看就是一個(gè)比較重要的模塊，所以我們今天就來(lái)學(xué)習(xí)一下ArrayList相關(guān)知識(shí)。ArrayList的數(shù)據(jù)結(jié)構(gòu)和作用ArrayLis...
ArrayList是Java集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自AbstractList，實(shí)現(xiàn)了List接口。底層基于數(shù)組實(shí)現(xiàn)容量大小動(dòng)態(tài)變化。一看就是一個(gè)比較重要的模塊，所以我們今天就來(lái)學(xué)習(xí)一下ArrayList相關(guān)知識(shí)。前言
ArrayList的數(shù)據(jù)結(jié)構(gòu)和作用
ArrayList數(shù)據(jù)結(jié)構(gòu)是數(shù)組，用來(lái)裝載數(shù)據(jù)。相對(duì)于LinkedList，查詢(xún)效率高，因?yàn)榈讓邮菙?shù)組，分配的是連續(xù)的內(nèi)存空間，CPU在讀取時(shí)可以緩存連續(xù)的內(nèi)存空間，大幅度降低讀取的性能開(kāi)銷(xiāo)；增刪效率低，相對(duì)于Vector來(lái)說(shuō)是線(xiàn)程不安全。
雖然ArrayList是線(xiàn)程不安全的，但在我們實(shí)際的應(yīng)用過(guò)程中，一般都是用來(lái)查詢(xún)，涉及到增刪的操作比較少，如果涉及到的增刪操作比較頻繁的場(chǎng)景，我們可以選擇LinkedList，如果想保證線(xiàn)程安全，可以使用Vector、CopyOrWriteArray。
如何實(shí)現(xiàn)存放任意數(shù)量的對(duì)象
ArrayList構(gòu)造器有無(wú)參構(gòu)造和有參構(gòu)造。在有參構(gòu)造器中，ArrayList可以通過(guò)構(gòu)造方法在初始化的時(shí)候進(jìn)行指定底層數(shù)組的大小。但是我們?cè)谑褂糜袇?gòu)造時(shí)，會(huì)不會(huì)初始化數(shù)組大小呢？我們先來(lái)看一下代碼：public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "
initialCapacity);
}
}
由代碼可知，我們可以很明確地得出結(jié)論：不會(huì)初始化數(shù)組大小。不信的話(huà)我們可以測(cè)試一下:
public static void main(String[] args){
//此處使用有參構(gòu)造，大小為10
ArrayListarrayList = new ArrayList<>(10);
System.out.println("size:" arrayList);
arrayList.set(1, "A");
}
看到這里是不是已經(jīng)懵圈了？不要慌，我們慢慢來(lái)分析。我們的參數(shù)是 initialCapacity，這里是將參數(shù)基于 elementData 設(shè)置的，并不是直接設(shè)置的數(shù)組大?。ㄖ档米⒁獾氖?，ensureCapacity();方法也是這種原理）。我們也可以理解為這個(gè)數(shù)組現(xiàn)在理論上最大可以裝10個(gè)數(shù)據(jù)，但是他現(xiàn)在還是空的。在無(wú)參構(gòu)造器中，初始化出一個(gè)默認(rèn)空的數(shù)組，數(shù)組容量為 0，當(dāng)我們調(diào)用add();方法是，默認(rèn)分配【DEFAULT_CAPACITY = 10】的初始容量。下面會(huì)具體介紹新增過(guò)程，此處不再贅述。
/**
* 數(shù)組默認(rèn)初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于默認(rèn)大小的空實(shí)例的共享空數(shù)組實(shí)例。
* 與 EMPTY_ELEMENTDATA 區(qū)分開(kāi)來(lái)，以了解何時(shí)膨脹多少添加第一個(gè)元素。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 構(gòu)造一個(gè)初始空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
但是，對(duì)于無(wú)參構(gòu)造和有參構(gòu)造，數(shù)組都是有長(zhǎng)度限制的，ArrayList是通過(guò)什么方式去實(shí)現(xiàn)可以存放任意數(shù)量的對(duì)象，長(zhǎng)度沒(méi)有限制的呢？不要慌，原來(lái)這個(gè)地方也是用到了數(shù)組的擴(kuò)容。
數(shù)組的擴(kuò)容
當(dāng)前我們有一個(gè)初始容器為10的數(shù)組，且每個(gè)位置已經(jīng)插滿(mǎn)數(shù)據(jù)，但是現(xiàn)在又要新增一條數(shù)據(jù)，這個(gè)時(shí)候當(dāng)前數(shù)組已經(jīng)不能滿(mǎn)足我們的要求了，那我們就需要進(jìn)行擴(kuò)容；然后我們就需要進(jìn)行擴(kuò)容，擴(kuò)大到原來(lái)的1.5倍，即【10 10 / 2】；最后將原數(shù)組的數(shù)據(jù)原封不動(dòng)地移動(dòng)到新數(shù)組，再返回新數(shù)組的地址，這樣ArrayList中數(shù)據(jù)就是新的數(shù)組了。接下來(lái)，我們就看一下源碼中的具體實(shí)現(xiàn)吧//擴(kuò)容前置判斷
private void ensureExplicitCapacity(int minCapacity) {
modCount ;
//minCapacity: 插入數(shù)據(jù)后容器大小或者默認(rèn)容器大小
//當(dāng)minCapacity比當(dāng)前數(shù)組大時(shí)，說(shuō)明需要擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容具體過(guò)程
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//此處java 8采用了位運(yùn)算，提升效率
int newCapacity = oldCapacity (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 直接使用數(shù)組的復(fù)制方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList的的新增
在ArrayList中，新增有三個(gè)方法分別是以下三種：//1\. 將指定的元素附加到此列表的末尾
public boolean add(E e) {
ensureCapacityInternal(size 1); // Increments modCount!!
elementData[size ] = e;
return true;
}
//2\. 在此指定位置插入指定元素列表。
public void add(int index, E element) {
//判斷指定參數(shù)是否超過(guò)范圍
rangeCheckForAdd(index);
ensureCapacityInternal(size 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index 1,
size - index);
elementData[index] = element;
size ;
}
//3\. 將指定集合中的所有元素追加到末尾這個(gè)列表，
// 按照它們返回的順序指定集合的迭代器。
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size = numNew;
return numNew != 0;
}
由代碼可知，不管是哪種插入，我們都需要通過(guò)調(diào)用 ensureCapacityInternal(); 方法來(lái)校驗(yàn)數(shù)組長(zhǎng)度，如果長(zhǎng)度不夠，就進(jìn)行擴(kuò)容，前面我們已經(jīng)了解過(guò)。對(duì)于指定位置新增時(shí)，我們?cè)谛ｒ?yàn)完成之后通過(guò)調(diào)用 arraycopy(); 方法來(lái)實(shí)現(xiàn)數(shù)組的復(fù)制。下面我們就來(lái)了解一下指定位置插入的過(guò)程。
當(dāng)前我們有一個(gè)長(zhǎng)度為10，還有一個(gè)空位的數(shù)組；
現(xiàn)在我們需要插入一個(gè)【a】，目標(biāo)位置是【5】，則先復(fù)制一個(gè)數(shù)組，指定位置之前的數(shù)據(jù)不變，從【5】開(kāi)始把后面的數(shù)據(jù)從【5 1】的位置開(kāi)始復(fù)制，新數(shù)組空出位置【5】；上一步我們已經(jīng)把【5】這個(gè)位置空出來(lái)了，然后將數(shù)據(jù)【a】插入空位，這樣就完成了指定位置插入的操作了。由上可知，ArrayList在新增的需要把數(shù)據(jù)復(fù)制一份，這個(gè)操作如果是針對(duì)大數(shù)據(jù)量List，再加上擴(kuò)容的操作，那效率就慢了。ArrayList的刪除
話(huà)不多說(shuō)，我們先來(lái)看一下代碼：public E remove(int index) {
rangeCheck(index);
modCount ;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index 1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
由代碼可知，如果是刪除末位，則直接刪除就完成了操作；如果是將中間數(shù)據(jù)刪除，則此過(guò)程中也是類(lèi)似于插入操作，將數(shù)組進(jìn)行了復(fù)制，調(diào)用arraycopy();方法。下面我們就來(lái)了解一下指定位置刪除的過(guò)程。
當(dāng)前我們有一個(gè)長(zhǎng)度為10；
現(xiàn)在我們需要?jiǎng)h除目標(biāo)位置為【5】的數(shù)據(jù)，則先復(fù)制一個(gè)數(shù)組，指定位置之前的數(shù)據(jù)不變，從【5 1】之后的數(shù)據(jù)進(jìn)行復(fù)制到新數(shù)組；得到新的數(shù)組，就是刪除了指定位置【5】數(shù)據(jù)的數(shù)組了。同理，ArrayList的刪除和新增一樣效率比較低。對(duì)于數(shù)據(jù)量大的數(shù)組需要復(fù)制和移動(dòng)的位置就比較大了。ArrayList適合做隊(duì)列嗎
一般的隊(duì)列是先進(jìn)先出隊(duì)列（FIFO），從尾部出入，頭部刪除。對(duì)于數(shù)組是十分適合做隊(duì)列的，比如 ArrayBlockingQueue內(nèi)部的實(shí)現(xiàn)就是通過(guò)一個(gè)定長(zhǎng)數(shù)組來(lái)實(shí)現(xiàn)一個(gè)環(huán)形定長(zhǎng)隊(duì)列，使用兩個(gè)偏移量來(lái)標(biāo)記數(shù)組的讀位置和寫(xiě)位置，如果超過(guò)長(zhǎng)度就折回到數(shù)組開(kāi)頭。但是前提必須是一個(gè)定長(zhǎng)的數(shù)組。
因?yàn)樵贏rrayList中，底層雖然是數(shù)組，但是數(shù)組長(zhǎng)度是不確定的。這樣我們就需要進(jìn)行大量的增加和刪除操作，就算是指定位置的刪除和新增，它也是需要經(jīng)過(guò)數(shù)組復(fù)制，這樣的話(huà)，會(huì)比較消耗性能。
因此，定長(zhǎng)數(shù)組適合做隊(duì)列，ArrayList不適合做隊(duì)列。
下載文檔
