ArrayList源碼解析（jdk1.6）

一、定義

ArrayList 是一個數組隊列，相當于動态數組。與Java中的數組相比，它的容量能動态增長。它繼承于AbstractList類，實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

要點：

1、繼承于AbstractList類，實作了List接口

2、實作RandomAccess接口，提供了随機通路功能。RandmoAccess是java中用來被List實作，為List提供快速通路功能。

3、ArrayList中的操作不是線程安全的！是以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList（系列源碼後續講到）。

二、屬性

// 儲存ArrayList中資料的數組
private transient Object[] elementData;
// ArrayList中實際資料的數量
private int size;

要點：

1、elementData是個動态數組，我們能通過構造函數 ArrayList(int initialCapacity)來執行它的初始容量為initialCapacity；如果通過不含參數的構造函數ArrayList()來建立ArrayList，則elementData的容量預設是10。可進行動态擴容

2、有個關鍵字需要解釋：transient。Java的serialization提供了一種持久化對象執行個體的機制。當持久化對象時，可能有一個特殊的對象資料成員，我們不想用serialization機制來儲存它。為了在一個特定對象的一個域上關閉serialization，可以在這個域前加上關鍵字transient。簡單了解為就是：序列化該對象時，某個屬性不想被序列化，可加transient關鍵字避免。

3、注意size為動态數組的實際大小。

三、構造函數

// ArrayList帶容量大小的構造函數。
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    // 建立一個數組
    this.elementData = new Object[initialCapacity];
}

// ArrayList構造函數。預設容量是10。
public ArrayList() {
    this(10);
}

// 構造一個包含指定元素的list，這些元素的是按照Collection的疊代器傳回的順序排列的
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

第一個構造方法使用提供的initialCapacity來初始化elementData數組的大小。
第二個構造方法調用第一個構造方法并傳入參數10，即預設elementData數組的大小為10。
第三個構造方法則将提供的集合轉成數組傳回給elementData（傳回若不是Object[]将調用Arrays.copyOf方法将其轉為Object[]），也很常用。

四、常見API

1、添加

在講添加元素之前，我們先來看一個函數：

/**
     * 數組容量檢查，不夠時則進行擴容
     */
   public void ensureCapacity( int minCapacity) {
       //對于modCount變量，我們後面會給出解釋
       modCount++;
       // 目前數組的長度
        int oldCapacity = elementData .length;
       // 最小需要的容量大于目前數組的長度則進行擴容
        if (minCapacity > oldCapacity) {
           Object oldData[] = elementData;
          // 新擴容的數組長度為舊容量的1.5倍+1
           int newCapacity = (oldCapacity * 3)/2 + 1;
          // 如果新擴容的數組長度還是比最小需要的容量小，則以最小需要的容量為長度進行擴容
           if (newCapacity < minCapacity)
              newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            // 進行資料拷貝，Arrays.copyOf底層實作是System.arrayCopy()
            elementData = Arrays.copyOf( elementData, newCapacity);
       }
    }

當進行添加元素時，需要進行是否擴容判斷。當增加modCount之後，判斷minCapacity（即size+1）是否大于oldCapacity（即elementData.length），若大于，則調整容量為max((oldCapacity*3)/2+1,minCapacity)（将一個集合插入到list會出現後者，比如addAll），調整elementData容量為新的容量，即将傳回一個内容為原數組元素，大小為新容量的數組賦給elementData；否則不做操作。

注意：當需要擴容時，jdk1.6容量為max((oldCapacity*3)/2+1,minCapacity)；

jdk1.7容量為max(oldCapacity + (oldCapacity >> 1),minCapacity) 。

關于添加的四個函數：

/**
     * 添加一個元素
     */
    public boolean add(E e) {
       // 進行擴容檢查
       ensureCapacity( size + 1);  // Increments modCount
       // 将e增加至list的資料尾部，容量+1
        elementData[size ++] = e;
        return true;
    }

    /**
     * 在指定位置添加一個元素
     */
    public void add(int index, E element) {
        // 判斷索引是否越界，這裡會抛出多麼熟悉的異常。。。
        if (index > size || index < 0)
           throw new IndexOutOfBoundsException(
               "Index: "+index+", Size: " +size);

       // 進行擴容檢查
       ensureCapacity( size+1);  // Increments modCount  
       // 對數組進行複制處理，目的就是空出index的位置插入element，并将index後的元素位移一個位置，共有
       //size-index個元素需要進行移動
       System. arraycopy(elementData, index, elementData, index + 1,
                      size - index);
       // 将指定的index位置指派為element
        elementData[index] = element;
       // list容量+1
        size++;
    }
    /**
     * 增加一個集合元素
     */
    public boolean addAll(Collection<? extends E> c) {
       //将c轉換為數組
       Object[] a = c.toArray();
        int numNew = a.length ;
       //擴容檢查
       ensureCapacity( size + numNew);  // Increments modCount
       //将c添加至list的資料尾部
        System. arraycopy(a, 0, elementData, size, numNew);
       //更新目前容器大小
        size += numNew;
        return numNew != 0;
    }
    /**
     * 在指定位置，增加一個集合元素
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
           throw new IndexOutOfBoundsException(
               "Index: " + index + ", Size: " + size);

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

       // 計算需要移動的長度（index之後的元素個數）
        int numMoved = size - index;
       // 數組複制，空出第index到index+numNum的位置，即将數組index後的元素向右移動numNum個位置
        if (numMoved > 0)
           System. arraycopy(elementData, index, elementData, index + numNew,
                          numMoved);

       // 将要插入的集合元素複制到數組空出的位置中
        System. arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

2、删除

删除操作常見API如下：

/**
     * 根據索引位置删除元素
     */
    public E remove( int index) {
      // 數組越界檢查
       RangeCheck(index);

        modCount++;
      // 取出要删除位置的元素，供傳回使用
       E oldValue = (E) elementData[index];
       // 計算數組要複制的數量
        int numMoved = size - index - 1;
       // 數組複制，就是将index之後的元素往前移動一個位置
        if (numMoved > 0)
           System. arraycopy(elementData, index+1, elementData, index,
                          numMoved);
       // 将數組最後一個元素置空（因為删除了一個元素，然後index後面的元素都向前移動了，是以最後一個就沒用了），好讓gc盡快回收
       // 不要忘了size減一
        elementData[--size ] = null; // Let gc do its work

        return oldValue;
    }

    /**
     * 根據元素内容删除，隻删除比對的第一個
     */
    public boolean remove(Object o) {
       // 對要删除的元素進行null判斷
       // 對資料元素進行周遊查找，知道找到第一個要删除的元素，删除後進行傳回，如果要删除的元素正好是最後一個那就慘了，時間複雜度可達O(n) 。。。
        if (o == null) {
            for (int index = 0; index < size; index++)
              // null值要用==比較
               if (elementData [index] == null) {
                  fastRemove(index);
                  return true;
              }
       } else {
           for (int index = 0; index < size; index++)
              // 非null當然是用equals比較了
               if (o.equals(elementData [index])) {
                  fastRemove(index);
                  return true;
              }
        }
        return false;
    }

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
       // 原理和之前的add一樣，還是進行數組複制，将index後的元素向前移動一個位置，不細解釋了，
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System. arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //後面的元素交給垃圾回收器
       elementData[--size ] = null; // Let gc do its work
    }

    /**
     * 數組越界檢查
     */
    private void RangeCheck(int index) {
        if (index >= size )
           throw new IndexOutOfBoundsException(
               "Index: "+index+", Size: " +size);
    }

上面講增加元素可能會進行擴容，而删除元素卻不會進行縮容，如果進行一次大擴容後，我們後續隻使用了幾個空間或者繼續進行删除操作？

/**
     * 将底層數組的容量調整為目前實際元素的大小，來釋放空間。
     */
    public void trimToSize() {
        modCount++;
       // 目前數組的容量
        int oldCapacity = elementData .length;
       // 如果目前實際元素大小 小于 目前數組的容量，則進行縮容
        if (size < oldCapacity) {
            elementData = Arrays.copyOf( elementData, size );
       }

3、查詢/更新太簡單，就不貼上了。

4、是否包含：

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    //找到指定對象的第一個索引位置，從前往後，判斷對象是否為null
    public int indexOf(Object o) {
        if (o == null) {
           for (int i = 0; i < size; i++)
               if (elementData [i]==null)
                  return i;
       } else {
           for (int i = 0; i < size; i++)
               if (o.equals(elementData [i]))
                  return i;
       }
        return -1;
    }

    //與前面相反，從後往前
    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;
    }

五、Fast-Fail快速失敗機制

此類的

iterator

和

listIterator

方法傳回的疊代器是快速失敗的：在建立疊代器之後，除了通過疊代器自身的

remove

或

add

方法從結構上對清單進行修改，否則在任何時間以任何方式對清單進行修改，疊代器都會抛出

ConcurrentModificationException

。是以，面對并發的修改，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險。

注意，疊代器的快速失敗行為無法得到保證，快速失敗疊代器會盡最大努力抛出

ConcurrentModificationException

。疊代器的快速失敗行為應該僅用于檢測 bug。

前面說到

ArrayList

中定義了一個

modCount

來記錄對容器進行結構修改的次數，在

add

、

addAll

、

remove

、

clear

、

clone

方法中都會引起

modCount

變化，而在建立疊代器時，會使用局部變量儲存目前的

modCount

值：

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        ...

在進行疊代的過程中，會先檢查

modCount

有沒有發生變化，以此來判定是否有外部操作改變了容器：

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

最後，因為

ArrayList

是非同步的，是以，在多線程環境下，如果有對容器進行結構修改的操作，則必須使用外部同步。

舉個例子：移除ArrayList某一個指定元素：

import java.util.ArrayList;
public class ArrayListRemove 
{
	public static void main(String[] args)
	{
		ArrayList<String> list = new ArrayList<String>();
		list.add("a");
		list.add("b");
		list.add("b");
		list.add("c");
		list.add("c");
		list.add("c");
		remove(list);
 
		for (String s : list) 
		{
			System.out.println("element : " + s);
		}
	}
	public static void remove(ArrayList<String> list) 
	{
		// TODO:
	}
}

如果要想删除list的b字元，有下面兩種常見的錯誤例子：

錯誤寫法執行個體一：

public static void remove(ArrayList<String> list) 
{
	for (int i = 0; i < list.size(); i++) 
	{
		String s = list.get(i);
		if (s.equals("b")) 
		{
			list.remove(s);
		}
	}
}

錯誤的原因：這種最普通的循環寫法執行後會發現第二個“b”的字元串沒有删掉。

錯誤寫法執行個體二：

public static void remove(ArrayList<String> list) 
{
	for (String s : list)
	{
		if (s.equals("b")) 
		{
			list.remove(s);
		}
	}
}

錯誤的原因：這種for-each寫法會報出著名的并發修改異常：java.util.ConcurrentModificationException。

先解釋一下執行個體一的錯誤原因。翻開JDK的ArrayList源碼，先看下ArrayList中的remove方法（注意ArrayList中的remove有兩個同名方法，隻是入參不同，這裡看的是入參為Object的remove方法）是怎麼實作的：

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

一般情況下程式的執行路徑會走到else路徑下最終調用faseRemove方法：

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; // Let gc do its work
}

可以看到會執行System.arraycopy方法，導緻删除元素時涉及到數組元素的移動。針對錯誤寫法一，在周遊第一個字元串b時因為符合删除條件，是以将該元素從數組中删除，并且将後一個元素移動（也就是第二個字元串b）至目前位置，導緻下一次循環周遊時後一個字元串b并沒有周遊到，是以無法删除。針對這種情況可以倒序删除的方式來避免：

public static void remove(ArrayList<String> list) 
{
	for (int i = list.size() - 1; i >= 0; i--) 
	{
		String s = list.get(i);
		if (s.equals("b")) 
		{
			list.remove(s);
		}
	}
}

因為數組倒序周遊時即使發生元素删除也不影響後序元素周遊。

接着解釋一下執行個體二的錯誤原因。錯誤二産生的原因卻是foreach寫法是對實際的Iterable、hasNext、next方法的簡寫，問題同樣處在上文的fastRemove方法中，可以看到第一行把modCount變量的值加一，但在ArrayList傳回的疊代器（該代碼在其父類AbstractList中）：

public Iterator<E> iterator() {
	return new Itr();
}

這裡傳回的是AbstractList類内部的疊代器實作private class Itr implements Iterator，看這個類的next方法：

public E next() {
	checkForComodification();
	try {
		E next = get(cursor);
		lastRet = cursor++;
		return next;
	} catch (IndexOutOfBoundsException e) {
		checkForComodification();
		throw new NoSuchElementException();
	}
}

第一行checkForComodification方法：

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

這裡會做疊代器内部修改次數檢查，因為上面的remove(Object)方法修改了modCount的值，是以才會報出并發修改異常。要避免這種情況的出現則在使用疊代器疊代時（顯示或for-each的隐式）不要使用ArrayList的remove，改為用Iterator的remove即可。

public static void remove(ArrayList<String> list) 
{
	Iterator<String> it = list.iterator();
	while (it.hasNext()) 
	{
		String s = it.next();
		if (s.equals("b")) 
		{
			it.remove();
		}
	}
}

總結：

在需要擴容的時候，調用Arrays.copyOf()，這個是建立新數組，底層也是System.arraycopy()

其他操作時用的是System.arraycopy()，直接在原數組上操作。

ArrayList源碼解析（jdk1.6）

繼續閱讀

DOS源碼相關資料

java基礎知識問答集

centos 下安裝 jdk

Mybatis源碼閱讀（一）：Mybatis初始化1.1 解析properties、settings前言入口引申結語

MyBatis源碼解析(一)——MyBatis初始化過程解MyBatis源碼解析(一)——MyBatis初始化過程解1. 準備工作2. MyBatis初始化過程

《資料結構》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明先附上文檔歸類目錄：部落客有話說：(已遷移到部落格園 ☛☛☛ 新部落格連結)

i = i++ 的困惑

一步一步解析集合架構ArrayList源碼（2）

如何配置Eclipse進行Perl開發

JAVA導入項目報錯Description Resource PathLocation Type Java compiler level does not match the version of

數組複制

JDK6新特性

關于JSch的問題描述

基于jdk1.8的Vector源碼分析

如何提高個人開源網站源碼開發使用率

JBoss,Geronimo和Glassfish初窺