整體架構(gòu)

ArrayList整體架構(gòu)比較簡單,就是一個數(shù)組結(jié)構(gòu),比較簡單,如下圖:

圖中展示是長度為10的數(shù)組,從1開始計數(shù),index表示數(shù)組的下標,從0開始計數(shù),elementData表示數(shù)組本身,源碼中除了這兩個概念,還有以下三個基本概念:

• DEFAULT_CAPACITY表示數(shù)組的初始大小,默認是10,這個數(shù)字要記住;
• size表示當前數(shù)組的大小,類型int,沒有使用volatile修飾,非線程安全的;
• modCount統(tǒng)計當前數(shù)組被修改的版本次數(shù),數(shù)組結(jié)構(gòu)有變動,就會+1。

類注釋

看源碼,首先要看類注釋,我們看看類注釋上面都說了什么,如下:

• 允許put null值,會自動擴容;
• size、isEmpty、get、set、add等方法時間復(fù)雜度都是O(1);
• 是非線程安全的,多線程情況下,推薦使用線程安全類;
• 增強for循環(huán),或者使用迭代器過程中,如果數(shù)組大小被改變,會快速失敗,拋出異常。

除了上述注釋中提到的4點,初始化、擴容的本質(zhì)、迭代器等問題也經(jīng)常被問,接下來我們從源碼觸發(fā),一一解析。

源碼解析

初始化

我們有三種初始化方法: 無參數(shù)直接初始化、指定大小初始化、指定初始數(shù)據(jù)初始化,源碼如下:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//無參數(shù)直接初始化，數(shù)組大小為空
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//指定初始數(shù)據(jù)初始化
public ArrayList(Collection<? extends E> c) {
    //elementData 是保存數(shù)組的容器，默認為 null
    elementData = c.toArray();
    //如果給定的集合（c）數(shù)據(jù)有值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果集合元素類型不是 Object 類型，我們會轉(zhuǎn)成 Object
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // 給定集合（c）無值，則默認空數(shù)組
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

除了源碼的中文注釋,我們補充兩點:

1. ArrayList無參構(gòu)造器初始化時,默認大小是空數(shù)組,并不是大家常說的10,10是在第一次add的時候擴容的數(shù)組值。
2. 指定初始數(shù)據(jù)初始化時,我們發(fā)現(xiàn)一個這樣子的注釋 see 6260652,這是Java的一個bug,意思是當給定集合內(nèi)的元素不是Object類型時,我們會轉(zhuǎn)化成Object的類型。一般情況下都不會觸發(fā)此bug,只有在下列場景才會觸發(fā): ArrayList初始化之后(ArrayList元素非Object類型),再次調(diào)用toArray方法,得到Object數(shù)組,并且往Object數(shù)組賦值時,才會觸發(fā)此bug,代碼和原因如圖:
   
   
   官方查看文檔地址：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652，問題在 Java 9 中被解決。

新增和擴容實現(xiàn):

新增就是往數(shù)組中添加元素,主要分成兩步:

• 判斷是否需要擴容,如果需要執(zhí)行擴容操作;
• 直接賦值。

兩步源碼體現(xiàn)如下:

public boolean add(E e) {
  //確保數(shù)組大小是否足夠，不夠執(zhí)行擴容，size 為當前數(shù)組的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接賦值，線程不安全的
  elementData[size++] = e;
  return true;
}

我們先看下擴容()的源碼:

private void ensureCapacityInternal(int minCapacity) {
  //如果初始化數(shù)組大小時，有給定初始值，以給定的大小為準，不走 if 邏輯
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //確保容積足夠
  ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
  //記錄數(shù)組被修改
  modCount++;
  // 如果我們期望的最小容量大于目前數(shù)組的長度，那么就擴容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//擴容，并把現(xiàn)有數(shù)據(jù)拷貝到新的數(shù)組里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果擴容后的值 < 我們的期望值，擴容后的值就等于我們的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果擴容后的值 > jvm 所能分配的數(shù)組的最大值，那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通過復(fù)制進行擴容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

我們需要注意的四點是:

• 擴容的規(guī)則并不是范圍,是原來容量大小+容量大小的一半,直白來說,擴容后的大小是原來容量的1.5倍;
• ArrayList中的數(shù)組的最大值是Integer.MAX_VALUE,超過這個值,JVM就不會給數(shù)組分配內(nèi)存空間了。
• 新增是,并沒有對值進行嚴格的校驗,所以ArrayList是允許null值的。

從新增和擴容源碼中,下面這點值得我們借鑒:

• 源碼在擴容的時候,有數(shù)組大小溢出意識,就是說庫容數(shù)組的大小下界不能小于0,上界不能大于Integer的最大值,這種意識我們可以學(xué)習(xí)。

擴容完成之后，賦值是非常簡單的，直接往數(shù)組上添加元素即可：elementData [size++] = e。

擴容的本質(zhì)

擴容是通過這行代碼來實現(xiàn)的:Arrays.copyOf(elementData, newCapacity);,這行代碼描述的本質(zhì)是數(shù)組之間的拷貝,擴容是會先創(chuàng)建一個符合我們預(yù)期容量的新數(shù)組,然后把老鼠組的數(shù)據(jù)拷貝過去,我們通過System.arraycopy方法進行拷貝,此方法是native的方法,源碼如下:

/**
 * @param src 被拷貝的數(shù)組
 * @param srcPos 從數(shù)組那里開始
 * @param dest 目標數(shù)組
 * @param destPos 從目標數(shù)組那個索引位置開始拷貝
 * @param length 拷貝的長度
 * 此方法是沒有返回值的,通過dest的引用進行傳值
 */
public static native void arraycopy(Object src,  int  srcPos,
                                Object dest, int destPos,
                                int length);

我們可以通過下面這行代碼進行調(diào)用，newElementData 表示新的數(shù)組：

System.arraycopy(elementData, 0, newElementData, 0,Math.min(elementData.length,newCapacity))

刪除

ArrayList刪除元素有很多種方式,比如根據(jù)數(shù)組索引刪除、根據(jù)值刪除或批量刪除等等,原理和思路都差不多,我們選取根據(jù)值刪除方式來進行源碼說明:

public boolean remove(Object o) {
  // 如果要刪除的值是 null，找到第一個值是 null 的刪除
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果要刪除的值不為 null，找到第一個和要刪除的值相等的刪除
    for (int index = 0; index < size; index++)
      // 這里是根據(jù)  equals 來判斷值相等的，相等后再根據(jù)索引位置進行刪除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

我們需要注意的兩點是:

• 新增的時候是沒有對null進行校驗的,所以刪除的時候也是允許刪除null值的;
• 找到值在數(shù)組中的索引位置,是通過equals來判斷的,如果數(shù)組元素不是基本類型,需要我們管錐equals的具體實現(xiàn)。
  上面代碼已經(jīng)找到要刪除元素的索引位置了,下面代碼是根據(jù)索引位置進行元素的刪除:

private void fastRemove(int index) {
  // 記錄數(shù)組的結(jié)構(gòu)要發(fā)生變動了
  modCount++;
  // numMoved 表示刪除 index 位置的元素后，需要從 index 后移動多少個元素到前面去
  // 減 1 的原因，是因為 size 從 1 開始算起，index 從 0開始算起
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 從 index +1 位置開始被拷貝，拷貝的起始位置是 index，長度是 numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //數(shù)組最后一個位置賦值 null，幫助 GC
  elementData[--size] = null;
}

迭代器

如果要自己實現(xiàn)迭代器,實現(xiàn)java.util.Iterator類就好了,ArrayList也是這樣做的,我們來看下迭代器的幾個重要的參數(shù):

int cursor;// 迭代過程中，下一個元素的位置，默認從 0 開始。
int lastRet = -1; // 新增場景：表示上一次迭代過程中，索引的位置；刪除場景：為 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代過程中，期望的版本號；modCount 表示數(shù)組實際的版本號。

迭代器一般來說有三個方法:

• hasNext還有沒有值可以迭代
• next如果有值可以迭代,迭代的值是多少
• remove刪除當前迭代的值

我們分別看下三個方法的源碼:
hasNext

public boolean hasNext() {
  return cursor != size;//cursor 表示下一個元素的位置，size 表示實際大小，如果兩者相等，說明已經(jīng)沒有元素可以迭代了，如果不等，說明還可以迭代
}

next

public E next() {
  //迭代過程中，判斷版本號有無被修改，有被修改，拋 ConcurrentModificationException 異常
  checkForComodification();
  //本次迭代過程中，元素的索引位置
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  // 下一次迭代時，元素的位置，為下一次迭代做準備
  cursor = i + 1;
  // 返回元素值
  return (E) elementData[lastRet = i];
}
// 版本號比較
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

從源碼中可以看到,next方法就干了兩件事情,第一是檢驗?zāi)懿荒芾^續(xù)迭代,第二是找到迭代的值,并為下一次迭代做準備(cursor+1)。
remove

public void remove() {
  // 如果上一次操作時，數(shù)組的位置已經(jīng)小于 0 了，說明數(shù)組已經(jīng)被刪除完了
  if (lastRet < 0)
    throw new IllegalStateException();
  //迭代過程中，判斷版本號有無被修改，有被修改，拋 ConcurrentModificationException 異常
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    // -1 表示元素已經(jīng)被刪除，這里也防止重復(fù)刪除
    lastRet = -1;
    // 刪除元素時 modCount 的值已經(jīng)發(fā)生變化，在此賦值給 expectedModCount
    // 這樣下次迭代時，兩者的值是一致的了
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

這里我們需要注意的兩點是:

• lastRet=-1的操作目的,是防止重復(fù)刪除操作
• 刪除元素成功,數(shù)組當前modCount就會發(fā)生變化,這里會把expectedModCount重新復(fù)制,下次迭代時兩者的值就會一致了

時間復(fù)雜度

從我們上面新增或刪除方法的源碼解析,對數(shù)組元素的操作,只需要根據(jù)數(shù)組索引,直接新增和刪除,所以時間復(fù)雜度是O(1)。

線程安全

我們需要強調(diào)的是,只有當ArrayList作為共享變量時,才會有線程安全問題,當ArrayList是方法內(nèi)的局部變量時,是沒有線程安全的問題的。
ArrayList 有線程安全問題的本質(zhì)，是因為 ArrayList 自身的 elementData、size、modConut 在進行各種操作時，都沒有加鎖，而且這些變量的類型并非是可見（volatile）的，所以如果多個線程對這些變量進行操作時，可能會有值被覆蓋的情況。
類注釋中推薦我們使用 Collections#synchronizedList 來保證線程安全，SynchronizedList 是通過在每個方法上面加上鎖來實現(xiàn)，雖然實現(xiàn)了線程安全，但是性能大大降低，具體實現(xiàn)源碼：

public boolean add(E e) {
    synchronized (mutex) {// synchronized 是一種輕量鎖，mutex 表示一個當前 SynchronizedList
        return c.add(e);
    }
}