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

[TOC]

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

因為是對數(shù)據(jù)進行了封裝, 所以底層存儲結構是數(shù)組結構. 可以想象的到, 數(shù)組長度的自動變化必須需要開辟新內(nèi)存, 然后進行數(shù)組元素的拷貝.

因為數(shù)組, 所以ArrayList也就具有數(shù)組的一些性, 如支持隨機訪問.

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

Object[] elementData;

先從構造方法開始分析.

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

注釋說, 構造一個容量為10的空的list.

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

那么什么時候會被初始化為10的數(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);
    }
}

這個就比無參構造方法清晰多了, 直接建立一個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;
    }
}

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

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

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

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

直接添加

指定位置添加

添加全部

在指定位置添加全部

因為是動態(tài)數(shù)組, 所以元素添加時需要校驗數(shù)組空間是否足夠, 如果不足, 需要進行數(shù)組的擴容(關于擴容看第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;
}

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

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

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

然后進行數(shù)組元素的移動.

源碼如下:

/**
 * 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++;
}

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

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

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

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

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ù)組的某個下標重新賦值.

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

將指定位置上的元素進行更新, 會對index進行越界檢查.

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

刪除方法有一下幾個:

E remove(int index)

boolean remove(Object o)

boolean removeAll(Collection c)

boolean retainAll(Collection c)

刪除指定位置上的元素, 如果刪除的不是最后一個元素, 則要進行元素的移動.

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

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

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

    return oldValue;
}

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

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

源碼如下:

// 刪除成功返回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;
}

// 快速刪除指定下標的元素, 無越界檢查
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
}

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

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

然后對不需要保留的下標賦予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集合包含本集合中的元素, 則不進行操作, 這就是保留不屬于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;
}

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

查找可以分為兩種情況:

通過下標直接定位元素

通過元素進行定位下標

包含的方法:

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)作為底層實現(xiàn), 我們需要了解indexOf(Object o)的底層實現(xiàn).

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

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

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

而get(int index)內(nèi)部調用了element(int index), 調用之前會進行下標越界的校驗.

遍歷分為三種方式:

普通for

foreach

iterator

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

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

例如:

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

// 這種情況會出現(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)的終止條件會隨著數(shù)組元素的移除不斷的變化.
第二種情況下, for循環(huán)的種植條件不會變化.

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

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

Iterator var2 = list.iterator();

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

這種形式. 因為ArrayList內(nèi)部的Iterator也維護了一個屬性expectedModCount來標識數(shù)組元素的變化, 初始化為modCount, 如果modCount與expectedModCount不一致的話, 就會拋出這個異常.

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

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

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

非正常情況當前是兩端的情況:

初始化時第一次擴容會擴容到初始化容量(DEFAULT_CAPACITY)

當容量達到最大值時不會遵循這個規(guī)律

擴容方式: 在每次添加新元素時, 會調用擴容代碼, 擴容方式還是比較簡單的. 只是進行了一些防止溢出的判斷.

// 進行擴容調用
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

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

// 進行一次modCount的修改, 表示數(shù)組元素發(fā)生了變動
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); // 計算出新數(shù)組長度 oldCapacity + oldCapacity / 2.
    if (newCapacity - minCapacity < 0) // 如果計算出的長度比傳入的長度小, 則使用傳入的長度作為新數(shù)組長度.
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新數(shù)組長度比MAX_ARRAY_SIZE, 進行溢出的校驗
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 進行數(shù)組的拷貝
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 如果minCapacity比MAX_ARRAY_SIZE大, 就取Integer.MAX_VALUE的值作為新數(shù)組長度, 否則使用MAX_ARRAY_SIZE
// 也就是傳入的長度, 而非通過原數(shù)組計算出來的長度.
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就是一個動態(tài)數(shù)組.

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

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

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