Java之ArrayList解剖學

• 2019 年 10 月 8 日
• 筆記

「 一起來了解集合中ArrayList的源碼實現 。」 —— 23號老闆

0

1

引入

先送一張圖。好好珍藏~ （來自網路）

回歸基礎，回歸原理，你會有更深的領悟。今天來聊一聊在Java當中常用的一個集合類：ArrayList。

在大學學習數據結構的時候，我們知道常見的一種數據結構，就是集合。而在Java中的集合，是用於存儲對象的工具類容器，它實現了常用的數據結構，提供了一系列公開的方法用於增加、刪除、修改、查找和遍曆數據，降低了日常開發的成本，提高了開發效率。

從上面的框架圖中可以看出，Java的集合主要分為兩類。

1、按照單個元素存儲的Collection，在其繼承樹中，Set、List都實現了Collection介面；

2、按照Key – Value存儲的Map，也是當下最流行的一種數據結構，業內出現了以此為基礎的各式Nosql數據存儲層產品。

02

了解ArrayList

List集合是線性數據結構的主要實現，集合元素通常存在一個明確的元素關係，Pre、Next。因此，List集合的遍歷結果是穩定的。ArrayList就是List集合中的一個實現類，在開發中也是最常使用的一個集合類。這裡以最常使用的JDK8為例，如果有版本上的不一致，請參看對比。

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

也許你會在面試當中，常說到這樣的話，和LinkedList作一次對比。ArrayList在使用上查詢效率較高，新增元素的效率較低，balabala……然後就沒什麼可說的。再一問，這是為什麼？不知道。

簡單來說，ArrayList在記憶體上的存儲，是利用了一個連續的存儲空間，是一個順序容器。即元素存放的數據與放進去的順序相同，允許放入null元素，底層通過數組實現。

ArrayList的幾個實現。

1、實現RandomAccess類

其原理的本質就在於indexedBinarySerach(list,key)或iteratorBinarySerach(list,key)方法。你會發現實現RandomAccess介面的List集合採用一般的for循環遍歷，而未實現這介面則採用迭代器。通過大量的測試可以知道，使用迭代器遍歷集合的速度會比for循環遍歷差。

2、實現Cloneable類

Cloneable是一個標記介面，只有實現這個介面後，然後在類中重寫Object中的clone方法，然後通過類調用clone方法才能克隆成功，如果不實現這個介面，則會拋出CloneNotSupportedException(克隆不被支援)異常。

3、實現Serializable類

實現Serializable介面的作用是就是可以把對象存到位元組流，然後可以恢復（反序列化），能夠進行關於對象的網路傳輸方式。

0

3

深入理解

/**   * 默認初始容量   */  private static final int DEFAULT_CAPACITY = 10;    private static final Object[] EMPTY_ELEMENTDATA = {};    /**   * 空表的表示方法   */  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    /**   * 底層的數組為elementData   */  transient Object[] elementData; // non-private to simplify nested class access    /**   * ArrayList的大小   */  private int size;    /**   * 帶有初始容量的構造器   */  public ArrayList(int initialCapacity) {      if (initialCapacity > 0) {//大於0時創建一個initialCapacity大小的數組          this.elementData = new Object[initialCapacity];      } else if (initialCapacity == 0) {          this.elementData = EMPTY_ELEMENTDATA;      } else {          throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);      }  }    /**   * 無參構造，默認空表數組 {}   */  public ArrayList() {      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  }    /**   * 當size大於0，採用Arrays.copyOf的複製方法賦值數組   */  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;      }  }

03

add、remove等

ArrayList的底層是基於動態數組實現的原因，動態數組的意思就是指底層的數組大小並不是固定的，而是根據添加的元素大小進行一個判斷，不夠的話就動態擴容，擴容的程式碼就在ensureCapacity里。

/**   * 確保在擴容時的容量   */  public void ensureCapacity(int minCapacity) {      int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)          // any size if not default element table          ? 0          // larger than default for default empty table. It's already          // supposed to be at default size.          : DEFAULT_CAPACITY;        if (minCapacity > minExpand) {          ensureExplicitCapacity(minCapacity);      }  }    /**   * 數組的最大長度值，超過則OutOfMemoryError   * OutOfMemoryError: Requested array size exceeds VM limit   */  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;    /**   * 擴容，原數組長度的2倍+1，採用的Arrays.copyOf複製方法   */  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);      elementData = Arrays.copyOf(elementData, newCapacity);  }      public int size() { return size;}    public boolean isEmpty() { return size == 0;}    public boolean contains(Object o) { return indexOf(o) >= 0;}  

空間的問題解決後，插入過程就顯得非常簡單。

/**   * 獲取index位置的元素   */  public E get(int index) {      rangeCheck(index);        return elementData(index);  }    /**   * 替換index位置上的元素   */  public E set(int index, E element) {      rangeCheck(index);      E oldValue = elementData(index);      elementData[index] = element;      return oldValue;  }    /**   * 新增元素   */  public boolean add(E e) {      ensureCapacityInternal(size + 1);  // Increments modCount!!      elementData[size++] = e;      return true;  }    /**   * 刪除元素   */  public E remove(int index) {      rangeCheck(index);      modCount++;      E oldValue = elementData(index);        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      return oldValue;  }    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;  }    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  }  

刪除是每次進行數組複製，然後讓舊的elementData置為null進行垃圾回收。

以remove()方法為例。

可以看到這個 remove() 方法被重載了，一種是根據下標刪除，一種是根據元素刪除，這也都很好理解。

根據下標刪除的 remove() 方法，大致的步驟如下：

1、檢查有沒有下標越界，就是檢查一下當前的下標有沒有大於等於數組的長度

2、列表被修改（add和remove操作）的次數加1

3、保存要刪除的值

4、計算移動的元素數量

5、刪除位置後面的元素向左移動，這裡是用數組拷貝實現的

6、將最後一個位置引用設為 null，使垃圾回收器回收這塊記憶體

7、返回刪除元素的值

根據元素刪除的 remove() 方法，大致的步驟如下：

1、元素值分為null和非null值

2、循環遍歷判等

3、調用 fastRemove(i) 函數

a、修改次數加1

b、計算移動的元素數量

c、數組拷貝實現元素向左移動

d、將最後一個位置引用設為 null

e、返回 fase

4、返回 true

04

小結

現在，你對ArrayList是不是有了一個更深入的理解。深入源碼，有時候能夠讓你更加理解程式碼的邏輯和數據結構。

文章部分內容來自網路部落格，綜合整理，在此鳴謝。