系列文章：

• Java集合系列01之概覽
• Java集合系列02之ArrayList源碼分析
• Java集合系列03之LinkedList源碼分析
• Java集合系列04之fail-fast機(jī)制分析
• Java集合系列05之Vector&Stack源碼分析及List總結(jié)
• Java集合系列06之Map接口概覽
• Java集合系列07之HashMap源碼分析
• Java集合系列08之WeakHashMap源碼分析
• Java集合系列09之TreeMap源碼分析
• Java集合系列10之Hashtable源碼分析

前言

本文開(kāi)始分析具體集合的源碼和實(shí)現(xiàn)原理恰梢，首先來(lái)看ArrayList。ArrayList可以理解為一個(gè)動(dòng)態(tài)數(shù)組杈湾，與普通數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)。其定義如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到ArrayList繼承了AbstractList類析恢，實(shí)現(xiàn)了List，RandomAccess冯痢，Cloneable和java.io.Serializable四個(gè)接口氮昧。

上文提到，AbstractList類提供了大部分List接口的實(shí)現(xiàn)浦楣，幫助我們減少了實(shí)現(xiàn)List接口的工作袖肥。

RandomAccess接口是List實(shí)現(xiàn)所使用的標(biāo)記接口，表明List支持快速隨機(jī)訪問(wèn)功能(就是通過(guò)索引獲取元素)振劳。

實(shí)現(xiàn)Cloneable接口表明覆蓋了Clone()函數(shù)椎组，能被克隆，實(shí)現(xiàn)java.io.Serializable接口表明ArrayList支持序列化历恐。

本文源碼分析基于jdk 1.8.0_121

繼承關(guān)系

ArrayList的繼承關(guān)系

java.lang.Object
  |___java.util.AbstractCollection<E>
      |___ java.util.AbstractList<E>
          |___ java.util.ArrayList<E>
所有已實(shí)現(xiàn)的接口：
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
直接已知子類：
AttributeList, RoleList, RoleUnresolvedList

關(guān)系圖

ArrayList關(guān)系圖

ArrayList的兩個(gè)成員elementData和size比較重要：

• elementData是Object類型的數(shù)組寸癌，保存了ArrayList的數(shù)據(jù)，是ArrayList的底層實(shí)現(xiàn)弱贼，它是個(gè)動(dòng)態(tài)數(shù)組蒸苇，在添加數(shù)據(jù)過(guò)程中不斷擴(kuò)展容量，最大容量為Integer.MAX_VALUE - 8吮旅；容量的增長(zhǎng)方式在源碼中具體再分析
• size是當(dāng)前動(dòng)態(tài)數(shù)組的實(shí)際大小

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

public ArrayList() {}       // 默認(rèn)構(gòu)造函數(shù)  
public ArrayList(int initialCapacity) {} // 構(gòu)造一個(gè)具有特定初始容量的ArrayList
public ArrayList(Collection<? extends E> c) {} // 創(chuàng)建一個(gè)包含Collection的ArrayList

以上三種構(gòu)造函數(shù)在不同JDK版本之間也略有差異溪烤，但思想或者做的工作都基本一致。
public ArrayList()在JDK1.8.0_121中令elementData為一個(gè)空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA庇勃，而此版本中還存在另一個(gè)空數(shù)組成員EMPTY_ELEMENTDATA檬嘀，此兩者的區(qū)別是用來(lái)區(qū)分ArrayList添加第一個(gè)元素時(shí)容量要擴(kuò)張多少。在之前的JDK版本中默認(rèn)構(gòu)造函數(shù)是直接初始化一個(gè)容量為10的數(shù)組责嚷。 （具體哪一版本開(kāi)始出現(xiàn)這一區(qū)別不知道）
public ArrayList(int initialCapacity)構(gòu)造一個(gè)指定初始容量的空列表鸳兽，當(dāng)initialCapacity為0時(shí)，令elementData為EMPTY_ELEMENTDATA罕拂。
public ArrayList(Collection<? extends E> c)構(gòu)造一個(gè)包含Collection的元素的列表揍异，這些元素按照該Collection的迭代器返回它們的順序排列的，先將Collection轉(zhuǎn)為數(shù)組聂受，再將數(shù)組拷貝給elementData蒿秦。

API

// Collection中定義的API(部分)
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear()
boolean             contains(Object object)
boolean             containsAll(Collection<?> collection)
boolean             equals(Object object)
int                 hashCode()
boolean             isEmpty()
Iterator<E>         iterator()
boolean             remove(Object object)
boolean             removeAll(Collection<?> collection)
boolean             retainAll(Collection<?> collection)
int                 size()
<T> T[]             toArray(T[] array)
Object[]            toArray()
// AbstractList API(部分)
void                add(int index, E element) 
boolean             addAll(int index, Collection<? extends E> c)
E                   get(int index)
int                 indexOf(Object o)
ListIterator<E>     listIterator()
ListIterator<E>     listIterator(final int index)
E                   remove(int index)
E                   set(int index, E element)
List<E>             subList(int fromIndex, int toIndex) 
// ArrayList API(部分)
Object              clone()
void                ensureCapacity(int minCapacity)
void                trimToSize()
void                removeRange(int fromIndex, int toIndex)

源碼分析

成員對(duì)象

// List默認(rèn)容量
private static final int DEFAULT_CAPACITY = 10;

// 空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空數(shù)組，使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建蛋济，則默認(rèn)對(duì)象內(nèi)容默認(rèn)是該值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 保存ArrayList中數(shù)據(jù)的數(shù)組棍鳖，transient表示不參與序列化
transient Object[] elementData;

// 實(shí)際容量大小
private int size;

// 數(shù)組最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

// 帶初始容量的構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
   if (initialCapacity > 0) {
       // 新建數(shù)組
       this.elementData = new Object[initialCapacity];
   } else if (initialCapacity == 0) {
       this.elementData = EMPTY_ELEMENTDATA;
   } else {
       throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
   }
}

// 默認(rèn)構(gòu)造函數(shù)   
public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 帶Collection對(duì)象的構(gòu)造函數(shù)
public ArrayList(Collection<? extends E> 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;
   }
}

改變?nèi)萘恐?/h2>

// 將當(dāng)前容量值設(shè)置為實(shí)際元素個(gè)數(shù)
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

確定容量

// 判斷待設(shè)置的最小容量minCapacity和默認(rèn)容量大小
// minCapacity大于minExpand時(shí)才擴(kuò)張容量
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0:DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// 修改次數(shù)+1，如果minCapacity大于數(shù)組長(zhǎng)度，則擴(kuò)張容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 設(shè)置新容量為(原始容量x3)/2
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 當(dāng)minCapacity超出Integer.MAX_VALUE時(shí)渡处，minCapacity變?yōu)樨?fù)數(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;
}

增加元素

// 添加元素e到ArrayList
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 添加元素到指定位置
public void add(int index, E element) {
   rangeCheckForAdd(index);

   ensureCapacityInternal(size + 1);  // Increments modCount!!
   // 把原數(shù)組index索引開(kāi)始后的所有元素向后移動(dòng)一個(gè)位置
   System.arraycopy(elementData, index, elementData, index + 1,
        size - index);
   elementData[index] = element;
   size++;
}

// 集合c追加到ArrayList中
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 將集合c轉(zhuǎn)換為數(shù)組后復(fù)制到elementData中
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

// 從位置index開(kāi)始，將集合c添加到ArrayList中
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

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

    int numMoved = size - index;
    // 先在elementData中空出長(zhǎng)度為集合c中元素個(gè)數(shù)的位置
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    
    // 復(fù)制集合元素到elementData中
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;  
}

toArray

// 轉(zhuǎn)化為ArrayList的Object數(shù)組
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
    
// 返回T類型的數(shù)組
public <T> T[] toArray(T[] a) {
    // 如果數(shù)組a的大小小于ArrayList的實(shí)際大小
    // 則新建一個(gè)數(shù)組(T[])數(shù)組医瘫，將ArrayList中元素全部拷貝到新數(shù)組中
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 若數(shù)組a的大小大于ArrayList的實(shí)際大小
    // 則將ArrayList中全部元素拷貝到數(shù)組a中
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

調(diào)用toArray方法有以下兩種：

java.lang.Integer[] obj = (java.lang.Integer[])list.toArray();
java.lang.Integer[] obj1 = list.toArray(new Integer[0]);

調(diào)用第一種方法會(huì)拋出“java.lang.ClassCastException”異常侣肄，調(diào)用 toArray(T[] contents) 能正常返回 T[]。
這是因?yàn)閷?code>Object[]轉(zhuǎn)換為的Integer[]則會(huì)拋出“java.lang.ClassCastException”異常醇份，因?yàn)镴ava不支持向下轉(zhuǎn)型稼锅。

設(shè)置元素

// 設(shè)置index處元素值，并返回舊值
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

讀取元素

// 獲取index位置的元素值
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

刪除元素

// 刪除index處元素僚纷，并返回
public E remove(int index) {
    rangeCheck(index);

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

    int numMoved = size - index - 1;
    // 移動(dòng)數(shù)組中元素位置矩距，保證數(shù)組連續(xù)性
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

// 刪除指定元素
public boolean remove(Object o) {
    // 判斷o是否為null
    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;
}

// 快速刪除第index個(gè)元素
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
}

// 刪除一定索引范圍內(nèi)元素值
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

// 刪除所有元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

序列化

// 將ArrayList的“容量，所有的元素值”都寫(xiě)入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // 寫(xiě)入數(shù)組容量
    s.writeInt(size);

    // 寫(xiě)入所有元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

// 將ArrayList的“容量”讀出怖竭，再將“所有的元素值”讀出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // 讀出容量
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 讀取所有元素值
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

遍歷方式

• 迭代器遍歷锥债，即通過(guò)Iterator遍歷

Iterator iter = list.iterator();
while(iter.hasNext()) {
    iter.next();
}

• 隨機(jī)訪問(wèn)，索引值

for (int i=0; i<list.size(); i++) {
    list.get(i);        
}

• foreach循環(huán)

for (Integer integ:list) {
    ;
}

通過(guò)比較以上三種遍歷方式痊臭，我們發(fā)現(xiàn)通過(guò)隨機(jī)訪問(wèn)方式效率最高哮肚，而另兩種方式效率都不高。

參考內(nèi)容

• Java 集合系列03之 ArrayList詳細(xì)介紹(源碼解析)和使用示例
• ArrayList 的實(shí)現(xiàn)原理