集合容器：ArrayList 源碼閱讀

一、概述

ArrayList是一個(gè)可以支持動態(tài)擴(kuò)容的數(shù)組，底層采用數(shù)組實(shí)現(xiàn)。ArrayList是AbstractList的子類，并且實(shí)現(xiàn)了List接口及相關(guān)方法，允許所有元素(包括null)的插入操作。ArrayList和Vector除了線程不同步之外，其它大致相同。

二、屬性

// 默認(rèn)初始容量
private static final int DEFAULT_CAPACITY = 10;

// 空數(shù)組常量
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默認(rèn)空數(shù)組常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存放元素的buffer
transient Object[] elementData;

// 包含元素的個(gè)數(shù)
private int size;

// 數(shù)組最大上線
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 繼承自父類的，結(jié)構(gòu)修改次數(shù)
protected transient int modCount = 0;

成員變量只有elementData和size兩個(gè)，可以看出ArrayList底層采用的是數(shù)組存儲。

所以具備數(shù)組具有的優(yōu)勢，插入、查找快，時(shí)間復(fù)雜度O(1)。

刪除的時(shí)候會進(jìn)行元素的移動，時(shí)間復(fù)雜度O(n)。

三、構(gòu)造方法

1. 無參空容量構(gòu)造

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

利用DEFAULTCAPACITY_EMPTY_ELEMENTDATA構(gòu)造了一個(gè)空的數(shù)組。數(shù)組長度為0，在初次使用的時(shí)候會擴(kuò)容到10。

2. 指定初始容量的構(gòu)造

public ArrayList(int initialCapacity) {
  // 參數(shù)合理化校驗(yàn)，容量不能為負(fù)數(shù)
  if (initialCapacity > 0) {
    // 構(gòu)造了一個(gè)給定長度的數(shù)組
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    // 構(gòu)造了一個(gè)空的數(shù)組
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    // 參數(shù)不合理，拋出異常
    throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  }
}

構(gòu)造一個(gè)給定初始容量的容器。

3. 根據(jù)指定集合構(gòu)建ArrayList

public ArrayList(Collection<? extends E> c) {
  // 將給定集合元素賦值給容器，如果給定的是null會拋出NPE
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    // c.toArray 可能是object[]的子類，所以需要再次進(jìn)行處理成Object[]
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // 容器是空數(shù)組
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

根據(jù)給定集合構(gòu)造容器。

四、添加元素

1. 數(shù)組尾端添加

在添加的時(shí)候，首先需要確保容器能放下要添加的元素，在判斷的過程中進(jìn)行了modCount++，然后將元素放在數(shù)組的尾端。

擴(kuò)容的次數(shù)很少，時(shí)間復(fù)雜度為O(1)。

public boolean add(E e) {
  // modCount自增，確保容器能放下最新元素
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 將插入的元素放入數(shù)組尾部
  elementData[size++] = e;
  return true;
}

2. 將元素添加到指定index處

在指定index處添加元素的時(shí)候，需要調(diào)用native方法將index后的元素向后移動。時(shí)間復(fù)雜度O(n)，涉及到數(shù)組的移動非常耗時(shí)。

public void add(int index, E element) {
  // 索引合理化校驗(yàn)
  rangeCheckForAdd(index);
  // modCount自增，確保容器能放下最新元素
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 調(diào)用native方法，將index后的所有元素向后移動
  System.arraycopy(elementData, index, elementData, index + 1, size - index);
  // 將element放在指定的index處
  elementData[index] = element;
  size++;
}

3. 替換指定索引處的元素

首先要判斷給定索引是否合理，需要處在[0,size)內(nèi)。替換后返回被替換掉的元素。時(shí)間復(fù)雜度O(1)

public E set(int index, E element) {
  // 指定索引檢查，是否是合理范圍，這里有一個(gè)bug，未校驗(yàn)負(fù)數(shù)。
  rangeCheck(index);
  E oldValue = elementData(index);
  // 替換指定索引處的元素為新元素
  elementData[index] = element;
  return oldValue;
}

4. 將給定集合的元素添加到容器

首先要對容器的容量進(jìn)行處理，確保容器能放下新老元素。不能放下則進(jìn)行擴(kuò)容，然后將新元素放到容器的尾端。

public boolean addAll(Collection<? extends E> c) {
  Object[] a = c.toArray();
  int numNew = a.length;
  // modCount自增并確保容器能放下新老元素
  ensureCapacityInternal(size + numNew);  // Increments modCount
  // 調(diào)用native方法，將新元素復(fù)制到容器內(nèi)
  System.arraycopy(a, 0, elementData, size, numNew);
  // 現(xiàn)有元素為新老元素的和
  size += numNew;
  return numNew != 0;
}

5. 將給定集合添加到index處

將給定的集合添加到index索引處，index后的元素需要向后移動。index后的元素需要向后挪動，時(shí)間復(fù)雜度O(n)

public boolean addAll(int index, Collection<? extends E> c) {
  // 索引合理化校驗(yàn)，index區(qū)間(0,size)，不合理則拋出異常
  rangeCheckForAdd(index);
  
  Object[] a = c.toArray();
  int numNew = a.length;
  // 確保容器能放下所有的新老元素，放不下則進(jìn)行擴(kuò)容
  ensureCapacityInternal(size + numNew);  // Increments modCount

  // index后元素挪動的索引數(shù)
  int numMoved = size - index;
  if (numMoved > 0)
    // 調(diào)用native方法，將index后的元素向后挪動numMoved個(gè)索引
    System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
  // 調(diào)用native方法，將新元素copy到指定的index處
  System.arraycopy(a, 0, elementData, index, numNew);
  size += numNew;
  return numNew != 0;
}

五、容量伸縮

1. 根據(jù)實(shí)際元素?cái)?shù)量縮容

將容器的容量縮小為當(dāng)前元素的實(shí)際個(gè)數(shù)，減少實(shí)例的存儲。

public void trimToSize() {
  // 修改次數(shù)自增
  modCount++;
  // 實(shí)際元素?cái)?shù)量小于容器容量的時(shí)候，進(jìn)行縮容
  if (size < elementData.length) {
    elementData = (size == 0)
      ? EMPTY_ELEMENTDATA
      // 創(chuàng)建了一個(gè)以size為大小的數(shù)組，并把元素放到新數(shù)組。
      : Arrays.copyOf(elementData, size);
  }
}

2. 確?？梢匀菁{minCapacity個(gè)元素

public void ensureCapacity(int minCapacity) {
  int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    // 如果不是默認(rèn)的空數(shù)組，將允許給定的數(shù)值
    ? 0
    // 默認(rèn)空數(shù)組的時(shí)候?yàn)槟J(rèn)容量 10
    : DEFAULT_CAPACITY;

  // 如果給定數(shù)值大于
  if (minCapacity > minExpand) {
    // 確保給定的容量
    ensureExplicitCapacity(minCapacity);
  }
}

根據(jù)給定的容量與實(shí)際容量比較，確定合適的容量大小。

六、元素獲取相關(guān)

1. get指定索引處的元素

時(shí)間復(fù)雜度O(1)，但是需要注意此處參數(shù)校驗(yàn)的時(shí)候未判斷負(fù)數(shù)，只判斷了是否小于size。

public E get(int index) {
  // index索引合理化校驗(yàn)，此處未校驗(yàn)負(fù)數(shù)。需要注意
  rangeCheck(index);
  return elementData(index);
}

2. 判斷容器內(nèi)是否包含給定元素

此處調(diào)用的是indexOf方法，如果indexOf返回的當(dāng)前元素的索引大于0則證明這個(gè)元素存在，時(shí)間復(fù)雜度O(n)，和indexOf一致。

public boolean contains(Object o) {
  return indexOf(o) >= 0;
}

3. 獲取給定元素第一次出現(xiàn)的索引

利用循環(huán)遍歷判斷給定的元素在數(shù)組中出現(xiàn)的索引，如果未匹配到則返回-1。時(shí)間復(fù)雜度O(n)

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

4. 獲取給定元素最后一次出現(xiàn)的位置

采用倒序遍歷，判斷元素出現(xiàn)的索引，如果未匹配到返回-1.時(shí)間復(fù)雜度O(n)。

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

七、元素刪除相關(guān)

1. 移除指定索引處的元素

將指定位置的元素刪除，并將后續(xù)元素向前移動補(bǔ)位。最后將刪除掉的元素失去引用，明確GC回收。

public E remove(int index) {
  // index索引合理化校驗(yàn)，此處未校驗(yàn)負(fù)數(shù)。需要注意
  rangeCheck(index);
  // 修改次數(shù)自增
  modCount++;
  // 要刪除索引處的元素
  E oldValue = elementData(index);

  // 將待刪除后的元素向前移動
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 調(diào)用native方法將，待刪除后的元素向前移動
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  // 根據(jù)GC可達(dá)性分析，明確GC要回收掉刪除后失去引用的對象
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

2. 移除給定元素

采用for循環(huán)遍歷，對元素一一匹配，找到要刪除的元素將其刪除，如果未找到則返回false。這里要注意，只刪除了元素首次出現(xiàn)，并不是將集合內(nèi)的全部這個(gè)元素都刪除。時(shí)間復(fù)雜度O(n)。

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])) {
        // modCount自增，并且將找到的index索引后的元素向前移動，最后將刪除掉的元素失去引用。
        fastRemove(index);
        return true;
      }
  }
  return false;
}

3. 清空當(dāng)前集合容器

循環(huán)遍歷將數(shù)組內(nèi)所有的元素都失去引用，并將數(shù)組的每個(gè)索引都指向null。時(shí)間復(fù)雜度O(n)。

public void clear() {
  // 修改次數(shù)自增
  modCount++;

  // clear to let GC do its work
  for (int i = 0; i < size; i++)
    elementData[i] = null;
  // 現(xiàn)有元素歸零
  size = 0;
}

4. 刪除給定索引范圍內(nèi)的元素

刪除掉的是包含fromIndex處，但不包含toIndex處的元素。時(shí)間復(fù)雜度O(2n)

protected void removeRange(int fromIndex, int toIndex) {
  // 修改次數(shù)自增
  modCount++;
  // 計(jì)算出要刪除掉的元素個(gè)數(shù)，將toIndex處的元素向前移動。
  int numMoved = size - toIndex;
  System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

  // clear to let GC do its work
  // 最新元素個(gè)數(shù)為原size減去刪除掉的元素個(gè)數(shù)
  int newSize = size - (toIndex-fromIndex);
  for (int i = newSize; i < size; i++) {
    // GC可達(dá)性算法明確GC回收刪除掉的代碼
    elementData[i] = null;
  }
  size = newSize;
}

5. 刪除給定集合的所有元素

public boolean removeAll(Collection<?> c) {
  // 判空，拋出NPE
  Objects.requireNonNull(c);
  return batchRemove(c, false);
}

6. 批量刪除/保留指定集合元素

根據(jù)參數(shù)complement的值，如果為true則取容器內(nèi)和給定集合的交集，如果為false則從容器內(nèi)刪除給定集合內(nèi)的元素。

private boolean batchRemove(Collection<?> c, boolean complement) {
  final Object[] elementData = this.elementData;
  int r = 0, w = 0;
  boolean modified = false;
  try {
    for (; r < size; r++)
      if (c.contains(elementData[r]) == complement)
        elementData[w++] = elementData[r];
  } finally {
    // Preserve behavioral compatibility with AbstractCollection,
    // even if c.contains() throws.
    // r不等于size，說明遍歷過程中容器內(nèi)元素有增刪操作。
    if (r != size) {
      // 
      System.arraycopy(elementData, r, elementData, w, size - r);
      w += size - r;
    }
    if (w != size) {
      // clear to let GC do its work
      for (int i = w; i < size; i++)
        elementData[i] = null;
      modCount += size - w;
      size = w;
      modified = true;
    }
  }
  return modified;
}

7. 快速刪除指定index處的元素(內(nèi)部方法)

private void fastRemove(int index) {
  // 修改次數(shù)自增
  modCount++;
  // 計(jì)算要移動元素的位置
  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
}