ArrayList源碼詳細分析——jdk1.8

手撕ArrayList源碼

• • 1.前言
  • 2.ArrayList關系圖
  • • 2.1 Iterable
    • 2.2 Cloneable
    • 2.3 RandomAccess
    • 2.4 Serializable
    • 2.5 AbstractList
  • 3. ArrayList
  • • 3.1 常量
    • 3.2 以debug的形式了解ArrayList
    • 3.3 自動失敗機制(fail-fast)
  • 4總結

1.前言

源碼一般由大量代碼組成，一上來就一行一行讀可能會覺得難以讀懂甚至放棄，這個時候不妨試試以debug的形式打開，一步一步來了解源碼的運作機制，是以本文将主要使用Debug的形式對java.util.ArrayList的源碼進行分析

首先打開設定，進行下圖操作，在Debugger中找到Stepping，然後取消勾選Don’t step into the classes，這一步是為了在debug過程中可以步入到ArrayList源碼中。

2.ArrayList關系圖

右鍵ArrayList找到diagram，就可以得到關系圖，如圖所示，從上往下依次分析

2.1 Iterable

Collection內建了Iterable接口，那麼ArrayList隻要實作Iterator就可以使用foreach進行循環疊代，下面就是ArrayList中的疊代器實作

private class Itr implements Iterator<E> {
     int cursor;       // 下一個元素的索引
     int lastRet = -1; // 最後一個元素的索引; 沒有就是-1
     int expectedModCount = modCount;// 這個是java的快速失敗機制，後文講

     Itr() {}

     public boolean hasNext() {
     	// 檢查ArrayList中有沒有下一個元素，size是ArrayList中儲存的元素個數，隻要下一個索引cursor不等于元素個數，那肯定就有元素了
         return cursor != size;
     }

     @SuppressWarnings("unchecked")
     public E next() {
         checkForComodification(); // 快速失敗機制
         int i = cursor;
         // 超出實際大小size的元素是空元素
         if (i >= size)
             throw new NoSuchElementException();
         // 本類Itr()是一個内部類，調用外部類的字段要用ArrayList.this.的形式
         Object[] elementData = ArrayList.this.elementData;
         if (i >= elementData.length)
             throw new ConcurrentModificationException();
         cursor = i + 1;
         // 取出下一個元素的值
         return (E) elementData[lastRet = i];
     }

     public void remove() {
         if (lastRet < 0)
             throw new IllegalStateException();
         checkForComodification();

         try {
             ArrayList.this.remove(lastRet);
             cursor = lastRet;
             lastRet = -1;
             expectedModCount = modCount; // remove不使用快速失敗機制
         } catch (IndexOutOfBoundsException ex) {
             throw new ConcurrentModificationException();
         }
     }
           

使用舉例：

public static void main(String[] args){
       ArrayList<String> list = new ArrayList<String>();
       list.add("a");
       list.add("b");
       list.add("b");
       list.add("c");

       for (String s : list) {
           System.out.println("element : " + s);
       }
   }
           

2.2 Cloneable

實作了該接口并實作Object.clone()方法就可以使用克隆(複制)方法，從下面的源碼可以看到，在ArrayList中的克隆方法是對目前ArrayList中所有元素的一個複制

public Object clone() {
       try {
           ArrayList<?> v = (ArrayList<?>) super.clone();
           v.elementData = Arrays.copyOf(elementData, size);
           v.modCount = 0;
           return v;
       } catch (CloneNotSupportedException e) {
           // this shouldn't happen, since we are Cloneable
           throw new InternalError(e);
       }
   }
           

2.3 RandomAccess

随機通路，這個接口是聲明ArrayList是具備随機通路的特性，也就是說通過索引通路元素的時間複雜度為常數，這是由于ArrayList是數組實作的，隻要通過a[i]就可以在常數時間内索引到對應的元素，而LinkedList這種使用連結清單實作的，需要從頭開始周遊，時間複雜度為O(n)，自然LinkedList就不是随機通路的。(有無機制差別很大，将會在LinkedList源碼中進行詳細分析)

2.4 Serializable

序列化，這個是為了儲存目前ArrayList對象的，通過輸入輸出流的形式對ArrayList對象進行讀寫操作

2.5 AbstractList

抽象類是可以有具體實作方法的，官方說他的存在是為了擴充一些方法進而減輕ArrayList的工作

3. ArrayList

一般而言，拿到源碼可以先看常量

3.1 常量

// 預設ArrayList的容量為10
private static final int DEFAULT_CAPACITY = 10; 
// 指定ArrayList為空
private static final Object[] EMPTY_ELEMENTDATA = {};	
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// transient是保護機制，序列化的時候不會被寫入到流中，elementData就是一個對象數組了
transient Object[] elementData; 
// ArrayList中存放的元素個數，注意這裡和ArrayList的容量區分開
private int size;
           

3.2 以debug的形式了解ArrayList

現在開始使用debug進行一些分析，先寫一個add方法我們進去看一下，然後再main函數出打一個斷點，開始debug，以下隻做一些重點部分說明(比如調用父類構造函數就不展示了)。

1.首先，由于我們new的時候沒有傳入參數，是以調用ArrayList的無參構造，預設是指派ArrayList一個空值

2.自動裝箱，因為我們add(2)，将int類型的2裝箱成Integer對象

3.現在進入到add方法裡面，但是此時的ArrayList是空的，是以ensureCapacityInternal就是來擴充ArrayList的大小的，初始size是0，這裡傳入size+1為參數，表明ArrayList的容量至少要為size+1=1

4.進入ensureCapacityInternal，發現其調用了ensureExplicitCapacity，參數有一個calculateCapacity方法，第二張圖是這個方法的實作，他會取size+1和預設值10兩者中的最大的值，顯然這裡直接取10，然後10就傳給了minCapacity

5. 是以10就傳入到ensureExplicitCapacity中，初始空間elementData,length是0，判斷成立，執行執行grow函數，顧名思義，grow應該是用于擴充ArrayList大小的

6.然後就進入到grow函數，oldCapacity >> 1表示右移一位(移位運算符是在二進制上進行操作，右移一位表示原數除以2，可以聯想十進制100右移一位就變成了10，也就是除以10)，newCapacity = oldCapacity + (oldCapacity >> 1)也就是容量變成原來的1.5倍，然後下面的代碼就是判斷一下傳進來的minCapacity和1.5倍oldCapacity誰大一些，就用大的，而hugeCapacity(minCapacity)就是虛拟機允許的最大容量

7.進入到copyOf方法，很容易發現這個方法就是重新new一個擴容的數組，然後把原來數組中的元素一個一個搬到新數組中，完成數組動态增長

8.至此就完成了所有的工作，其實這已經将ArrayList的核心搞懂了，像其他的一些方法，get、set、addAll就都很簡單了，讀者可以嘗試自己去試試

3.3 自動失敗機制(fail-fast)

最難最核心的東西基本上都展現出來了，現在講講自動失敗機制(fail-fast)

這個機制其實是為了安全，比如當我使用Iterator周遊ArrayList的時候，對ArrayList進行修改怎麼辦，比如使用ArrayList.remove方法把我即将要周遊讀取的元素給删了，這個時候我周遊出來的數組就不是原來的數組了(下面是單線程下的一個示例，多線程更容易出現該問題，并且更隐蔽)

public static void main(String[] args) {
       List<String> list = new ArrayList<>();
       for (int i = 0 ; i < 10 ; i++ ) {
            list.add(i + "");
       }
       Iterator<String> iterator = list.iterator();
       int i = 0 ;
       while(iterator.hasNext()) {
            if (i == 3) {
                 list.remove(3);
            }
            System.out.println(iterator.next());
            i ++;
       }
 }
           

這個時候會報錯

那怎麼實作這個機制呢，那就是用一個标志modCount，每當ArrayList做一次add、remove的時候就會讓modCount加一，疊代器裡面有一個expectedModCount，然後當你進行Iterator疊代的時候，會執行 expectedModCount = modCount，開始周遊後，如果修改了ArrayList，ModCount仍然會增加，而expectedModCount隻有一次指派，是以這兩個的值将會不相等，隻要不相等就會抛出并發修改異常

4總結

1.ArrayList繼承了RandomAccess，由于ArrayList本質是數組，是以查詢元素很快，時間複雜度為常數，但是插入删除元素需要逐個挪動其他元素，時間複雜度為O(n)，是以查詢工作量大的時候用ArrayList比較好，需要反複插入删除元素使用LinkedList比較好

2.ArrayList預設初始容量為10，如果容量不夠，則建立一個容量為原來1.5倍的數組，然後将舊數組的元素逐一複制到新數組中，這就完成了grow操作

3.ArrayList具有快速失敗機制fail-fast，在使用疊代器周遊ArrayList的時候，如果外界對ArrayList進行了修改，則會抛出并發修改異常