java ArrayList源碼分析

研究ArrayList源碼有一段時間了，說實話收益還是很大的。主要當方法的實作比較清楚時，用起來也比較放心。并且集合相關的源碼對了解資料結構還是有點幫助的。話不多說，開始分析。

（1）ArrayList實作了List接口，List接口中定義了list中通用的很多方法。

public class ArrayList<E> extends AbstractList<E>
	implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	...<span style="font-family: Arial, Helvetica, sans-serif;">}</span>

（2）ArrayList裡的屬性。其中elementData就是底層用來存儲ArrayList中元素的具體數組。

private static final long serialVersionUID = 8683452581122892189L;
    //預設初始化容量
    private static final int DEFAULT_CAPACITY = 10;
    //當不指定ArrayList大小時，elementdata<span style="font-family: Arial, Helvetica, sans-serif;">預設</span>初始化<span style="font-family: Arial, Helvetica, sans-serif;">是一個空的數組</span>
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //存儲ArrayList裡元素的數組<span style="white-space:pre">	</span>
    private transient Object[] elementData;
    //包含元素的數量
    private int size;
    //數組最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(3)構造方法

相比于之前的ArrayList的實作，之前當不指定ArrayList初始化容量時，預設在調用構造方法時，初始化elementData容量為DEFAULT_CAPACITY(即10)。現在隻會在調用add方法第一次添加元素時，會初始化容量。起到一點節約記憶體的作用。

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }


    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;//當不傳入大小時,預設是一個空的數組
    }
	//根據其他集合構造List
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)//toArray傳回的可能不是Object[]類型
            elementData = Arrays.copyOf(elementData, size, Object[].class);//[1]調用該方法傳回Object[]數組
    }

以上ArrayList(Collection<? extends E> c)這個構造方法根據傳入的集合建立ArrayList。當傳入的集合調用toArray方法傳回的數組類型不是Object[]數組時，在[1]處調用Arrays工具類中的copyOf方法傳回一個Object[]類型的數組并賦給elementData，由此達到建立ArrayList的目的。

Arrays類中的copyOf方法

[1].Arrays類中的copyOf方法
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

（4）boolean add(E e)方法：該方法用于向list末尾添加一個指定類型的元素。每次添加元素時，需要調用ensuerCapacityInternal方法來確定elementData數組的内部容量足夠存儲新添加的元素e。

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

ensureCapacityInternal方法如下，該方法隻會對elementData數組容量為0時（即無參構造方法中this.elementData = EMPTY_ELEMENTDATA;）,指定elementData的最小容量為DEFAULT_CAPACITY或add中傳入的大小中的較大者。如果elementData數組大小不為0，則會繼續調用ensureExplicitCapacity方法（確定數組的明确容量）。

[2]處調用ensureCapacityInternal(size+1)保證每次添加元素時數組容量夠用
   private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {//如果elementData是空數組
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//最小容量是size+1或預設容量(10)中的最大值
        }
        ensureExplicitCapacity(minCapacity);//[3]
    }

ensureExplicitCapacity方法中，當發現要存儲元素的容量（size+1）大于elementData的長度時，則調用grow方法對數組擴容。

[3]處調用ensureExplicitCapacity(minCapacity)方法  
   private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//如果指定的容量超出了elementData數組的現有容量,要擴容
            grow(minCapacity);//[4]
    }

千呼萬喚始出來，grow方法設定數組新容量為舊的數組容量+舊的數組容量右移一位。和size+1(這是能容納add進來的元素的最小容量minCapacity)比較，如果小于，則使用minCapacity。如果newCapacity超出了MAX_ARRAY_SIZE，還需要調用hugeCapacity方法進一步處理。

[4]處調用了grow(minCapcity)實作擴容
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量為舊的數組容量+舊的數組容量右移一位
        if (newCapacity - minCapacity < 0)//和minCapacity比較,至少也要能容納新添加進來的元素
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//[5]
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//數組擴容
    }

當容量超出Integer.MAX_VALUE時（即minCapacity<0），記憶體溢出。

[5]處調用hugeCapacity(minCapacity)
   private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow.容量超出Integer最大值(即為負數),記憶體溢出
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?//最大容量為Integer.MAX_VALUE或 MAX_ARRAY_SIZE
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

通過以上幾個繁複的方法後，終于可以保證add方法容量夠用了，此時add方法在elementData下标size+1處出入元素e即可。

（5）addAll方法

boolean addAll(Collection<? extends E> c):将集合c中的所有元素添加到elementData的末尾。

将要添加的集合調用toArray()轉換為數組,并得到數組長度numNew.然後確定elementData的容量（依然調用ensureCapacityInternal方法）足夠添加新的集合.。

将要添加的集合中的所有元素複制到elementData從size位置往後的位置,修改size.

public boolean addAll(Collection<? extends E> 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;//如果要添加的元素中沒有元素,傳回false
    }

boolean addAll(int index,Collection<? extends E>)重載的方法。從elementData指定下标位置開始添加集合c中的元素。判斷需要移動元素的數量。再調用arraycopy具體複制。

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);//下标檢查

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  //確定容量
		//從index及其以後的所有元素都需要移動,以便插入新的集合元素
        int numMoved = size - index;
        //如果需要移動,将index及其以後的所有元素移動到從index+numNew及其以後的位置處
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
		//将要添加的集合複制進來
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

看完所有集合關于增add,addAll的操作。總結起來，涉及向ArrayList中添加元素之前，要先調用ensureCapacityInternal方法確定内部容量。然後可能會出現接下來的方法調用。

ensureCapacityInternal->ensureExplicitCapacity->grow->hugeCapacity，均是為了保證配置設定合适的容量用來添加元素。如果涉及根據指定下标添加元素時，需要調用rangeCheckForAdd方法來保證下标的正确性。緊接着，就是向elementData數組中添加元素的相關操作了。如果添加一個元素，直接在相應位置添加。如果添加多個元素，使用System.arraycopy方法或Arrays.copyof方法等進行操作。

（6）看完增(add)，接下來再看删(remove)的相關方法。

E remove(int index):list中獨有的根據指定下标來移除元素的方法。

先調用rangeCheck方法確定要移除元素的下标的正确性。由于要删除該index下标處的元素，是以index往後的所有元素響應的要向前移動一位。使用System.arraycopy方法，将elementData從index+1到最後的所有元素複制到index開始往後。最後将之前elementData中size-1位置的元素(list中的最後一個元素)置為null。傳回移除的值。

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
	//需要移動的元素的數量
    int numMoved = size - index - 1;
    if (numMoved > 0)//如果數量大于0,移動
    	//将從index+1以及之後的所有元素向前移動
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;//傳回值為移除的值

rangeCheck方法如下

調用rangeCheck方法,檢查下标,若下标越界,抛異常    
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

boolean remove(Object o):該方法在集合中移除指定的元素。在周遊集合過程中，如果找到指定元素，則調用fastRemove方法移除該元素。

remove(Object o):該方法根據指定的元素在集合中移除該元素
  public boolean remove(Object o) {
  		//如果要移除的元素為null,周遊集合找到為null的元素移除
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);//[8]
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

調用fastRemove來移除元素,該方法和remove(int index)方法相比,就少調用了rangeCheck(index)而已,

因為上面的remove(Object 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
    }

clear方法相比較于remove一個個的移除元素而言，clear方法則是清空集合中的所有元素。

clear
将集合中所有元素的引用設定為null,讓垃圾回收器去解決吧.别忘了把size設定為0,代表現在list中沒有元素
 public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

（7）看完了增(add,addAll)删(remove,clear)操作，再來看看改(set)相關的方法。

set(int index,E element):該方法用于在指定下标處替換原來的元素,傳回原來的元素。涉及下标相關的都要進行rangeCheck操作。

public E set(int index, E element) {
        rangeCheck(index);

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

（8）增删改都介紹完了，下面介紹查(get)相關的方法。

get(int index)

get:該方法根據指定下标傳回集合中的元素
 public E get(int index) {
        rangeCheck(index);//[7]
        return elementData(index);
    }

indexOf():該方法傳回集合中要查詢元素第一次出現的下标。

public int indexOf(Object o) {
    if (o == null) {//如果要查詢的元素為null
        for (int i = 0; i < size; i++)
        //直接找到elementData中元素為null的下标并傳回即可
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
        //周遊集合,如果equals,則傳回下标
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;//查無,則傳回-1
}

boolean contains(Object o)：

public boolean contains(Object o) {
 //由于indexOf方法在查詢不到指定元素時傳回-1,查詢到時傳回下标,是以通過>=0即可判斷是否包含指定元素o
        return indexOf(o) >= 0;
    }

int lastIndexOf(Object o):傳回該元素最後一次出現的下标。

public int lastIndexOf(Object o) {
    if (o == null) {
    //從後往前周遊
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

（9）toArray方法：該方法将elementData從下标0開始size長度的元素(即所有存儲在集合中的元素)複制并傳回。

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

T[] toArray(T[] a)重載的方法，需要指定一個類型的數組，并傳回該類型的數組。如果指定的數組大小小于size，則傳回一個包含ArrayList中所有元素的新數組，否則複制并将size下标處的元素設定為null

public <T> T[] toArray(T[] a)
 public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;//a數組size下标處置為null
        return a;
    }

舉個例子。

@Test
	public void testToArray(){
		List<Integer> list=new ArrayList<Integer>();
		for(int i=0;i<5;i++){
			list.add(i);
		}
		Integer[] arr=list.toArray(new Integer[]{11,22,33,44,55,66,77,88});
		System.out.println(Arrays.toString(arr));//[0, 1, 2, 3, 4, null, 77, 88]
	}

就說到這裡，寫了好幾個小時，準備了好久，有不足之處和錯誤之處還望指正。

java ArrayList源碼分析

繼續閱讀

變量作用域及局部變量，成員變量，靜态變量的差別

關于JAVA的學習路線

黑嗎程式員----[20150527][張孝祥7K面試][銀行業務排程]銀行業務排程系統

JVM工作原理簡述

a=a++了解代碼：

一維數組練習

JAVA Math類與Random類Math類Random類

面向對象與面向過程思想的概述

delphi播放flash

java多線程初步

JavaSE概念

數組複制

javaEE和javaweb的差別JavaEEJavaSEJavaEE 與 JavaSE 的差別與聯系JavaEE和JavaWeb的差別JavaEE與Java 的關系

基于jdk1.8的Vector源碼分析

Java列印出任意規模空心菱形（菱形）

Java中的日期類（Date）月曆類(Calendar)及其與String的轉換綜合練習——輸入生産日期計算保存期限及促銷日