ArrayList 底層結構及原始碼分析

ArrayList 基本介紹

ArrayList實作了List介面，它可以存盤包括null的任何型別的物件，允許重復元素，ArrayList在內部使用一個陣列來存盤元素，當元素數量超過陣列容量時，ArrayList會自動重新分配更大的內部陣列，并且將現有元素復制到新陣列中，ArrayList基本等同于Vector，但是ArrayList是執行緒不安全的（執行效率高），在多執行緒情況下不建議使用ArrayList，

ArrayList 原始碼閱讀及操作機制

首先ArrayList中用來存盤元素的陣列是 Object 型別的陣列 elementData，ArrayList的容量就是這個陣列的大小，

transient Object[] elementData;

通過 debug 下面這段代碼來觀察ArrayList的擴容機制，

public class TestArrayList() {
  public static void main(String[] args) {
    ArrayList list = new ArrayList();
    // ArrayList list = new ArrayList(4);
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }
        for (int i = 11; i <= 15; i++) {
            list.add(i);
        }
  }
}

構造方法

當使用無參構造器創建ArrayList物件時，會創建一個默認容量為10的空陣列，

public ArrayList() {
  this.elementData = https://www.cnblogs.com/echo97/p/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 用于默認大小的空實體的共享空陣列，將其與 EMPTY_ELEMENTDATA 區分開，
// 以便在添加第一個元素時知道需要擴容多少，
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.cnblogs.com/echo97/p/{};

使用指定大小的構造器創建ArrayList物件時，則初始 elementData 容量為指定大小，

public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = https://www.cnblogs.com/echo97/p/new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  }
}

add(E e)

add(E e)方法將指定元素添加到串列末尾，該方法先呼叫ensureCapacityInternal()方法確保容量至少是所需的最小容量（即當前大小加一），然后再賦值，

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

由于ArrayList允許的元素型別是 Object，所以添加基本型別的資料時，會先將其轉換為對應的包裝型別，

ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity()

該方法計算需要的容量，如果elementData =https://www.cnblogs.com/echo97/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA（使用無參構造器時即符合該條件），則回傳DEFAULT_CAPACITY（10），否則回傳 minCapacity（size + 1），

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData =https://www.cnblogs.com/echo97/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private static final int DEFAULT_CAPACITY = 10;

ensureExplicitCapacity(int minCapacity)

modCount 記錄串列被結構性修改的次數（結構性修改是指添加或洗掉一個或多個元素，或顯式調整后備陣列的大小，僅僅設定元素的值不是結構性修改），如果需要的容量大于 elementData 的長度，則呼叫grow()方法進行擴容，

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

grow()

該方法增加容量以確保串列至少能夠容納最小容量引數minCapacity指定的元素數量，計算得到新容量應為舊容量的 1.5 倍，如果計算得到的新容量小于需要的最小容量，則新容量應為需要的最小容量（使用無參構造器第一次添加元素時即為這種情況，第一次擴容為 10），如果請求的陣列大小超過了虛擬機的限制，可能會導致 OutOfMemoryError，最后通過陣列復制copyOf.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);
  // minCapacity is usually close to size, so this is a win:
  elementData = https://www.cnblogs.com/echo97/p/copyOf.copyOf(elementData, newCapacity);
}

總結

當使用無參構造器創建ArrayList物件時，elementData 初始容量為 0，第一次添加元素時 elementData 擴容為 10，以后再需要擴容，按 1.5 倍來擴容，若使用有參構造器創建ArrayList物件，elementData 初始容量為指定大小，如果需要擴容，則擴容為 1.5 倍，

值得注意的是，由于每次調整容量都需要將所有元素復制到新陣列中，所以在元素數量較多時，頻繁地調整容量可能會導致性能下降，為了避免頻繁地調整容量，可以使用ArrayList的指定大小的構造方法或在添加大量元素之前使用ensureCapacity()方法預先指定較大的容量，以減少容量調整的次數，

另外，當從ArrayList中洗掉元素時，并不會立即縮小內部陣列的容量，如果希望減少記憶體占用，可以使用trimToSize()方法來調整ArrayList的容量，使其與元素數量匹配，這樣可以釋放未使用的記憶體空間，

標籤：Java

上一篇：快取雪崩、快取擊穿、快取穿透原因及解決辦法

下一篇：返回列表