java jdk是如何實(shí)現(xiàn)ArrayList的？

ArrayList的實(shí)現(xiàn)很簡(jiǎn)單，總的來(lái)說(shuō)，就是arraylist內(nèi)置了一個(gè)Object類(lèi)型的數(shù)組，當(dāng)插入或刪除數(shù)據(jù)時(shí)，都操作這個(gè)內(nèi)置數(shù)組array。當(dāng)用戶想new的ArrayList大于內(nèi)置數(shù)組時(shí)，會(huì)在后面串一個(gè)數(shù)組，具體數(shù)組怎么遞增看下文。

1. ArrayList中的屬性

    //數(shù)組每次增加長(zhǎng)度時(shí)最小增量（具體每次增加時(shí)，增量不一定是MIN_CAPACITY_INCREMENT，有一定的策略）
    private static final int MIN_CAPACITY_INCREMENT = 12;
    
    //ArrayList的長(zhǎng)度
    int size;
    
    //數(shù)組
    transient Object[] array; 

2. 構(gòu)造函數(shù)

我們先來(lái)看看構(gòu)造函數(shù)怎么實(shí)現(xiàn)的。

2.1 不指定大小

像這樣定義：

ArrayList arrayList = new ArrayList();

直接創(chuàng)建一個(gè)大小為0的ArrayList實(shí)例。

public ArrayList() {
     array = EmptyArray.OBJECT;
 }
 

2.2 指定int類(lèi)型的大小（容量）

像這樣定義：

ArrayList arrayList = new ArrayList(10);

如果指定的容量大小capacity為0，則只創(chuàng)建一個(gè)容量為0的ArrayList實(shí)例，否則，直接new一個(gè)指定大小的Object類(lèi)型的數(shù)組。

public ArrayList(int capacity) {
if (capacity < 0) {
   throw new IllegalArgumentException("capacity < 0: " + capacity);
 }
 array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
 

2.3 創(chuàng)建一個(gè)包含指定Collection的list

像這樣定義：

ArrayList arrayList = new ArrayList(Collection collection);

直接把Collection轉(zhuǎn)換為數(shù)組，并復(fù)制給ArrayList的數(shù)組array。具體實(shí)現(xiàn)如下：

private static int newCapacity(int currentCapacity) {
    int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
    return currentCapacity + increment;
}

3 增量的確定

3.1 插入數(shù)據(jù)時(shí)，ArrayList內(nèi)置數(shù)組增量的確定

ArrayList插入涉及到數(shù)組增量的問(wèn)題，即插入一個(gè)數(shù)或一組數(shù)時(shí)，ArrayList內(nèi)置的數(shù)組該如何增長(zhǎng)？如果頻繁增長(zhǎng)，既浪費(fèi)時(shí)間又會(huì)使內(nèi)存碎片化；可如果每次增量很大，如每插入數(shù)據(jù)內(nèi)置數(shù)組就增加很大的容量值，那么會(huì)導(dǎo)致很多空間浪費(fèi)。 jdk有一個(gè)方法提供了具體策略：

private static int newCapacity(int currentCapacity) {
    int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
    return currentCapacity + increment;
}

如果指定增量currentCapacity小于12/2=6，則增量為12；否則增量為currentCapacity/2.

注：currentCapacity >> 1 即為currentCapacity/2.如：

0000 0111（7）>> 1 右移一位變?yōu)?0000 0011（3）。

0000 1100（12）>> 1 右移一位變?yōu)?0000 0110（6）。

3.2 在index位置插入一個(gè)數(shù)object

我們來(lái)看一下方法，add(int index, E object),在index位置插入一個(gè)Object類(lèi)型的數(shù)。

@Override 
public void add(int index, E object) {
    Object[] a = array;
    int s = size;
    if (index > s || index < 0) {
        throwIndexOutOfBoundsException(index, s);
    }

    if (s < a.length) {
        System.arraycopy(a, index, a, index + 1, s - index);
    } else {
        // assert s == a.length;
        Object[] newArray = new Object[newCapacity(s)];
        System.arraycopy(a, 0, newArray, 0, index);
        System.arraycopy(a, index, newArray, index + 1, s - index);
        array = a = newArray;
    }
    a[index] = object;
    size = s + 1;
    //父類(lèi)AbstractList的一個(gè)屬性，記錄list改變了幾項(xiàng)
    modCount++;
}

其實(shí)就是

1. 先根據(jù)newCapacity方法獲取到數(shù)組增量，

2. 然后new一個(gè)臨時(shí)數(shù)組newArray，先把當(dāng)前數(shù)組array從[0,index]都copy給newArray的[0,index]，

3. 然后把a(bǔ)rray從 [index,s]（數(shù)組末尾）copy給newArray的[index+1,s+1]，這樣全部數(shù)組就復(fù)制過(guò)來(lái)了，然后把newArray copy給array；

4. 最后令array[index+1]為新插入的值object，size+1。

3.3 在index位置插入一個(gè)collection

這種情況下增量是多少呢？

注意：ArrayList并不是直接增加collection.length()的長(zhǎng)度，而是通過(guò)newCapacity方法來(lái)計(jì)算增量，傳入的參數(shù)是 當(dāng)前數(shù)組的長(zhǎng)度(size+newSize).
其中 newSize為新數(shù)組newArray(collection.toArray())的長(zhǎng)度.

前面我們說(shuō)過(guò)，如果一次增量過(guò)小，會(huì)造成頻繁增加數(shù)組，這樣既浪費(fèi)時(shí)間，又會(huì)損耗性能。

代碼如下：

@Override
public boolean addAll(int index, Collection<? extends E> collection) {
    int s = size;
    if (index > s || index < 0) {
        throwIndexOutOfBoundsException(index, s);
    }
    Object[] newPart = collection.toArray();
    int newPartSize = newPart.length;
    if (newPartSize == 0) {
        return false;
    }
    Object[] a = array;
    int newSize = s + newPartSize; // If add overflows, arraycopy will fail
    if (newSize <= a.length) {
         System.arraycopy(a, index, a, index + newPartSize, s - index);
    } else {
        int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(a, 0, newArray, 0, index);
        System.arraycopy(a, index, newArray, index + newPartSize, s-index);
        array = a = newArray;
    }
    System.arraycopy(newPart, 0, a, index, newPartSize);
    size = newSize;
    modCount++;
    return true;
}

4. remove方法

4.1 remove(int index)

先把index后面的值全部向前移一位，然后把最后一位a[s]置為空。

@Override 
    public E remove(int index) {
    Object[] a = array;
    int s = size;
    if (index >= s) {
        throwIndexOutOfBoundsException(index, s);
    }
    @SuppressWarnings("unchecked") E result = (E) a[index];
    //核心代碼
    //把數(shù)組a[index+1,s]復(fù)制給數(shù)組a[index,s-1]
    System.arraycop
    y(a, index + 1, a, index, --s - index);
    //數(shù)組最后以為置空
    a[s] = null;  // Prevent memory leak
    size = s;
    modCount++;
    return result;
}

4.2 clean方法

把數(shù)組全部置空。

@Override public void clear() {
    if (size != 0) {
        Arrays.fill(array, 0, size, null);
        size = 0;
        modCount++;
    }
}

public static void fill(Object[] array, int start, int end, Object value) {
    Arrays.checkStartAndEnd(array.length, start, end);
    for (int i = start; i < end; i++) {
        array[i] = value;
    }
}