摘要：概述為了彌補(bǔ)普通數(shù)組無法自動(dòng)擴(kuò)容的不足提供了集合類其中就對數(shù)組進(jìn)行了封裝使其可以自動(dòng)的擴(kuò)容或縮小長度因?yàn)槭菍?shù)據(jù)進(jìn)行了封裝所以底層存儲(chǔ)結(jié)構(gòu)是數(shù)組結(jié)構(gòu)可以想象的到數(shù)組長度的自動(dòng)變化必須需要開辟新內(nèi)存然后進(jìn)行數(shù)組元素的拷貝因?yàn)閿?shù)組所以也就具有數(shù)

[TOC]

為了彌補(bǔ)普通數(shù)組無法自動(dòng)擴(kuò)容的不足, Java提供了集合類, 其中ArrayList就對數(shù)組進(jìn)行了封裝, 使其可以自動(dòng)的擴(kuò)容或縮小長度.

因?yàn)槭菍?shù)據(jù)進(jìn)行了封裝, 所以底層存儲(chǔ)結(jié)構(gòu)是數(shù)組結(jié)構(gòu). 可以想象的到, 數(shù)組長度的自動(dòng)變化必須需要開辟新內(nèi)存, 然后進(jìn)行數(shù)組元素的拷貝.

因?yàn)閿?shù)組, 所以ArrayList也就具有數(shù)組的一些性, 如支持隨機(jī)訪問.

第一節(jié)已經(jīng)說了, 它是一種自動(dòng)數(shù)組, 內(nèi)部存儲(chǔ)結(jié)構(gòu)就是數(shù)組了.

Object[] elementData;

先從構(gòu)造方法開始分析.

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注釋說, 構(gòu)造一個(gè)容量為10的空的list.

但是這里我們并沒有看到數(shù)組的容量變?yōu)?0, 而是一個(gè)空的數(shù)組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

那么什么時(shí)候會(huì)被初始化為10的數(shù)組呢？答案是有元素被加入時(shí)(add方法).

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

這個(gè)就比無參構(gòu)造方法清晰多了, 直接建立一個(gè)initialCapacity大小的數(shù)組.

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection"s
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

這里的意思傳入一個(gè)集合類(Collection的子類即可), 轉(zhuǎn)為list.

Collection有一個(gè)子抽象類, 默認(rèn)實(shí)現(xiàn)了toArray();, 如果子類比較特殊需要, 進(jìn)行重寫即可.

集合類的重要功能就是進(jìn)行交互(元素的存儲(chǔ)、修改、刪除、遍歷等).

內(nèi)部有四種方式的添加:

直接添加

指定位置添加

添加全部

在指定位置添加全部

因?yàn)槭莿?dòng)態(tài)數(shù)組, 所以元素添加時(shí)需要校驗(yàn)數(shù)組空間是否足夠, 如果不足, 需要進(jìn)行數(shù)組的擴(kuò)容(關(guān)于擴(kuò)容看第5節(jié)).

源碼如下:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return true (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

在指定位置添加, 必然會(huì)影響到該位置的元素以及后續(xù)元素, 對于數(shù)組這種數(shù)據(jù)結(jié)構(gòu), 只能進(jìn)行元素的后移了.

這就體現(xiàn)出數(shù)組這種數(shù)據(jù)結(jié)構(gòu)的不足了: 對元素的修改不太擅長.

同普通添加元素一樣, 需要校驗(yàn)數(shù)組容量數(shù)組足夠, 不過在校驗(yàn)之前還要檢查一下入?yún)⒌脑匚恢?index)是否在范圍內(nèi).

然后進(jìn)行數(shù)組元素的移動(dòng).

源碼如下:

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

與構(gòu)造方法類似, 這里也使用了toArray();

只不過需要進(jìn)行數(shù)組大小的校驗(yàn)擴(kuò)容, 然后進(jìn)行元素拷貝.

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;
}

通過上面的說明, 這個(gè)方法就很容易懂了.

public boolean addAll(int index, Collection c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

修改操作比較簡單, 就是給數(shù)組的某個(gè)下標(biāo)重新賦值.

只有一個(gè)方法: E set(int index, E element)

將指定位置上的元素進(jìn)行更新, 會(huì)對index進(jìn)行越界檢查.

刪除操作也意味著數(shù)組中會(huì)有元素移動(dòng), 除非刪除的是最后一個(gè)元素.

刪除方法有一下幾個(gè):

E remove(int index)

boolean remove(Object o)

boolean removeAll(Collection c)

boolean retainAll(Collection c)

刪除指定位置上的元素, 如果刪除的不是最后一個(gè)元素, 則要進(jìn)行元素的移動(dòng).

public E remove(int index) {
    rangeCheck(index); // 檢查下標(biāo)是否越界

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1; // 最后 -1 是為了數(shù)組下標(biāo)不越界
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

刪除數(shù)組中的某個(gè)元素, 會(huì)分為兩種情況: null OR !null.

找到元素之后會(huì)使用fastRemove(index)進(jìn)行刪除.

源碼如下:

// 刪除成功返回true, 失敗false
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 快速刪除指定下標(biāo)的元素, 無越界檢查
private void fastRemove(int index) {
    modCount++;
    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
}

傳入一個(gè)集合c, 如果集合c中包含本集合中的元素, 則對改元素進(jìn)行處理, 這里利用了一個(gè)complement屬性, 來決定含有的元素是刪除還是保留.

簡單說一下批量刪除/保留操作, 把匹配的元素(c.contains(elementData[r]) == complement)進(jìn)行保留.

然后對不需要保留的下標(biāo)賦予null值.

public boolean removeAll(Collection c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 如果complement為false, 則c集合包含本集合中的元素, 則不進(jìn)行操作, 這就是保留不屬于c集合中的所有元素.
            // 這就是 4-3-4. boolean retainAll(Collection c)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.

        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

這部分就不貼源碼了, 很容易理解.

查找可以分為兩種情況:

通過下標(biāo)直接定位元素

通過元素進(jìn)行定位下標(biāo)

包含的方法:

boolean contains(Object o)

int indexOf(Object o)

int lastIndexOf(Object o)

E elementData(int index)

E get(int index)

contains(Object o)方法使用了indexOf(Object o)作為底層實(shí)現(xiàn), 我們需要了解indexOf(Object o)的底層實(shí)現(xiàn).

indexOf(Object o)是從數(shù)組的頭開始查找, 查找到相同元素時(shí), 進(jìn)行返回, 而lastIndexOf(Object o)正好相反, 從數(shù)組的尾開始查找, 查找到相同元素時(shí)進(jìn)行返回.

可以使用indexOf和lastIndexOf進(jìn)行返回值的比較, 如果相等, 說明該元素在數(shù)組中唯一(前提是返回非-1).

elementData(int index)則是內(nèi)部方法, 獲取指定下標(biāo)處的元素.

而get(int index)內(nèi)部調(diào)用了element(int index), 調(diào)用之前會(huì)進(jìn)行下標(biāo)越界的校驗(yàn).

遍歷分為三種方式:

普通for

foreach

iterator

至于三種方式的性能, 自己測試吧, 哈哈哈

重點(diǎn): 只有某種情況下的普通for和iterator可以在循環(huán)的同事進(jìn)行元素的刪除.

例如:

// 該情況下不會(huì)發(fā)生異常
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);
    // do something...
    list.remove(i);
}

// 這種情況會(huì)出現(xiàn)越界問題
int size = list.size();
for (int i = 0; i < size; i++) {
    String s = list.get(i);
    // do something...
    list.remove(i);
}

第一種情況下, for循環(huán)的終止條件會(huì)隨著數(shù)組元素的移除不斷的變化.
第二種情況下, for循環(huán)的種植條件不會(huì)變化.

for (String s : list) {
    // do something...
    list.remove(s);
}

這種方式會(huì)發(fā)生ConcurrentModificationException, 因?yàn)锳rrayList內(nèi)部有一個(gè)屬性為modCount, 每當(dāng)數(shù)組中的元素發(fā)生變化是, 該數(shù)值會(huì)增1, 而foreach形式的循環(huán)編譯后會(huì)變?yōu)?/p>

Iterator var2 = list.iterator();

while(var2.hasNext()) {
    String s = (String)var2.next();
    list.remove(s);
}

這種形式. 因?yàn)锳rrayList內(nèi)部的Iterator也維護(hù)了一個(gè)屬性expectedModCount來標(biāo)識(shí)數(shù)組元素的變化, 初始化為modCount, 如果modCount與expectedModCount不一致的話, 就會(huì)拋出這個(gè)異常.

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    // do something...
    iterator.remove();
}

foreach時(shí)我們直接調(diào)用了list.remove(s);方法, 該方法只會(huì)改變modCount的值, 并不會(huì)改變expectedModCount的值, 相反, 使用Iterator提供的remove方法則會(huì)對兩個(gè)值一起修改.

首先記住一點(diǎn): 每次會(huì)擴(kuò)容原數(shù)組的 1.5倍(正常情況下).

非正常情況當(dāng)前是兩端的情況:

初始化時(shí)第一次擴(kuò)容會(huì)擴(kuò)容到初始化容量(DEFAULT_CAPACITY)

當(dāng)容量達(dá)到最大值時(shí)不會(huì)遵循這個(gè)規(guī)律

擴(kuò)容方式: 在每次添加新元素時(shí), 會(huì)調(diào)用擴(kuò)容代碼, 擴(kuò)容方式還是比較簡單的. 只是進(jìn)行了一些防止溢出的判斷.

// 進(jìn)行擴(kuò)容調(diào)用
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 計(jì)算是使用 DEFAULT_CAPACITY 還是傳入的 minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {

    // 當(dāng)使用 new ArrayList() 創(chuàng)建實(shí)例時(shí), 數(shù)組的默認(rèn)容量為10就是在這里產(chǎn)生的.
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 進(jìn)行一次modCount的修改, 表示數(shù)組元素發(fā)生了變動(dòng)
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // 防止元素溢出
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 獲取舊數(shù)組長度
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 計(jì)算出新數(shù)組長度 oldCapacity + oldCapacity / 2.
    if (newCapacity - minCapacity < 0) // 如果計(jì)算出的長度比傳入的長度小, 則使用傳入的長度作為新數(shù)組長度.
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新數(shù)組長度比MAX_ARRAY_SIZE, 進(jìn)行溢出的校驗(yàn)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 進(jìn)行數(shù)組的拷貝
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 如果minCapacity比MAX_ARRAY_SIZE大, 就取Integer.MAX_VALUE的值作為新數(shù)組長度, 否則使用MAX_ARRAY_SIZE
// 也就是傳入的長度, 而非通過原數(shù)組計(jì)算出來的長度.
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

ArrayList就是一個(gè)動(dòng)態(tài)數(shù)組.

ArrayList的擴(kuò)容操作必然會(huì)進(jìn)行內(nèi)存的申請以及數(shù)組元素的拷貝.

實(shí)例化時(shí)盡可能的確定好數(shù)組中元素的數(shù)量, 避免發(fā)生擴(kuò)容.

使用List subList(int fromIndex, int toIndex)時(shí), 返回的不是ArrayList對象, 是SubList(ArrayList的內(nèi)部類)對象, 但是操作的元素還是ArrayList的元素.