ArrayList 概述

ArrayList 是一種變長的集合類，底層是基于陣列來實作的，所以 ArrayList 查詢效率高、增刪效率低
ArrayList 集合中的元素是有序、可重復的，且可以存盤 null 空值
當每次向 ArrayList 容器中添加元素時，會進行容量檢查：當往 ArrayList 中添加的元素數量大于其底層陣列容量時，會通過擴容機制重新生成一個更大容量的陣列，然后把舊陣列上面的資料復制進新陣列
ArrayList 是執行緒不安全的，在并發環境下，多個執行緒同時操作 ArrayList，會引發不可預知的錯誤，所以在多執行緒環境下可以使用 concurrent 并發包下的 CopyOnWriteArrayList 類來替代 ArrayList 類，或者使用 Collections.synchronizedList(List l) 回傳一個執行緒安全的 ArrayList 類

屬性

// 容器中真正存放元素的地方，使用 transient 是為了不序列化這個欄位，elementData 陣列的長度指的是容器的容量
transient Object[] elementData;

// 容器中真正存盤的元素個數
private int size;

// 定義默認空容量的陣列：當使用 new ArrayList() 創建容器時，會將這個空陣列直接賦值給 elementData
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.cnblogs.com/sbgong/archive/2022/11/14/{};

// 默認的容量大小：使用 new ArrayList() 創建容器后，并往容器中添加第一個元素時才會使用這個默認容量進行初始化
private static final int DEFAULT_CAPACITY = 10;

// 定義空容量的陣列：當使用 new ArrayList(0) 創建容器時，會使用這個空陣列
private static final Object[] EMPTY_ELEMENTDATA = {};

構造方法

ArrayList()

// 無參的構造方法
public ArrayList() {
  // 當直接創建ArrayList時，elementData被賦予了默認空容量的陣列，此時ArrayList容器的容量是0
  this.elementData = https://www.cnblogs.com/sbgong/archive/2022/11/14/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int)

// 傳容量的構造方法：根據傳入的數值大小，創建指定長度的陣列
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = https://www.cnblogs.com/sbgong/archive/2022/11/14/new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  }
}

當 initialCapacity > 0 時，會在堆上 new 一個大小為 initialCapacity 的陣列，然后將其參考賦給 elementData，此時 ArrayList 的容量為 initialCapacity，元素個數 size 為默認值 0
當 initialCapacity = 0 時，elementData 被賦予了默認空陣列，因為其被 final 修飾了，所以此時 ArrayList 的容量為 0，元素個數 size 為默認值 0
當 initialCapacity < 0 時，會拋出例外

ArrayList(Collection)

// 傳入Collection元素串列的構造方法
public ArrayList(Collection<? extends E> c) {
  Object[] a = c.toArray();
  if ((size = a.length) != 0) {
    if (c.getClass() == ArrayList.class) {
      elementData = https://www.cnblogs.com/sbgong/archive/2022/11/14/a;
    } else {
      elementData = Arrays.copyOf(a, size, Object[].class);
    }
  } else {
    // replace with empty array.
    elementData = EMPTY_ELEMENTDATA;
  }
}

將引數集合轉化為一個 Object 型別的陣列：

如果引數集合轉換為陣列后的陣列長度為 0，會初始化 elementData 為空陣列，此時 ArrayList 的容量是 0，元素個數 size 為 0
如果引數集合轉換為陣列后的陣列長度不等于 0
- 如果引數集合的型別是 ArrayList，則直接將引數賦值給 elementData
- 否則，將引數陣列的陣列型別轉換為 Object 物件陣列的陣列型別，并賦值給 elementData

添加元素

當我們探討擴容時，肯定要從ArrayList的add方法走起

add(E)

// 在容器尾部插入指定元素
public boolean add(E e) {
  // 添加元素之前，首先需要確定集合的容量（檢測集合是否需要擴容）
  ensureCapacityInternal(size + 1);
  // 將指定元素插入容器尾部
  elementData[size++] = e;
  return true;
}

// 確保容器內部的容量：即容器擴容的入口方法
private void ensureCapacityInternal(int minCapacity) { // minCapacity是集合當前大小+1
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 計算并得到容器的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 如果elementData是空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA，則從size+1的值和默認值10中取最大值
  if (elementData =https://www.cnblogs.com/sbgong/archive/2022/11/14/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  // 如果elementData不為空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA，則回傳size+1
  return minCapacity;
}

// 確保elementData陣列的容量足夠存放新加入的元素，若不夠，要擴容
private void ensureExplicitCapacity(int minCapacity) {
  // moCount是記錄ArrayList被修改次數的，該變數主要是用來實作fail-fast機制
  modCount++;
  // 如果添加元素后的集合最小容量大于當前ArrayList內部陣列的長度，就需要對內部陣列elementData擴容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

// 擴容的實際方法：該方法是用來確保ArrayList至少能存盤minCapacity個元素
private void grow(int minCapacity) {
  // 擴容前的elementData容量
  int oldCapacity = elementData.length;
  // 獲取舊容量的1.5倍賦值給一個新容量變數（oldCapacity右移一位，等于除以二）
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0) // 如果擴容后的新容量比實際需要的容量還小，則以實際需要的容量為準
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新容量超過容器支持的最大容量了，則使用最大容量
    newCapacity = hugeCapacity(minCapacity);
  // 使用 Arrays.copyOf() 方法將原陣列的值拷貝到一個大小為newCapacity的新陣列
  elementData = Arrays.copyOf(elementData, newCapacity);
}

// 計算最大的容量
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // 大小溢位
    throw new OutOfMemoryError();
  // 如果所需最小容量minCapacity大于陣列最大的長度，則取Integer的最大值，否則取陣列最大長度
  return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// 允許分配的最大陣列大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

add(int, E)

// 在集合指定索引 index 位置處插入指定元素 element
public void add(int index, E element) {
  // 檢查是否越界
  rangeCheckForAdd(index);
  // 檢測是否需要擴容
  ensureCapacityInternal(size + 1);
  // 將 index 及其之后的所有元素都向后移一位
  System.arraycopy(elementData, index, elementData, index + 1, size - index);
  // 將新元素插入至index的位置
  elementData[index] = element;
  size++;
}

private void rangeCheckForAdd(int index) {
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

ArrayList 的擴容機制

擴容可分為兩種情況：

第一種情況：當 ArrayList 的容量為 0 時，此時添加元素的話，需要擴容，三種構造方法創建的 ArrayList 在擴容時略有不同

無參構造，創建 ArrayList 后容量為 0，添加第一個元素后，容量變為 10，此后若需要擴容，則正常擴容
傳容量構造，當引數為 0 時，創建 ArrayList 后容量為 0，添加第一個元素后，容量為 1，此時 ArrayList 是滿的，下次添加元素時需正常擴容
傳串列構造，當串列為空時，創建 ArrayList 后容量為 0，添加第一個元素后，容量為 1，此時 ArrayList 是滿的，下次添加元素時需正常擴容

第二種情況：當 ArrayList 的容量大于 0，并且集合是滿的時，此時添加元素的話，進行正常擴容，每次擴容到原來的 1.5 倍

洗掉元素

不同于插入操作，ArrayList 沒有無參洗掉方法，所以其只能洗掉指定位置的元素或洗掉指定元素，這樣就無法避免移動元素（除非從元素序列的尾部洗掉）

remove(int)

// 洗掉指定位置的元素
public E remove(int index) {
  // 檢查是否陣列越界
  rangeCheck(index);
  // moCount是記錄ArrayList被修改次數的，該變數主要是用來實作fail-fast機制
  modCount++;
  // 獲取index索引處的元素
  E oldValue = https://www.cnblogs.com/sbgong/archive/2022/11/14/elementData(index);
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 如果 index 不是最后一位，則將 index + 1 及之后的元素向前移動一位，覆寫被洗掉值
    System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  // 將最后一個元素置空，并將 size 值減 1
  elementData[--size] = null;
  // 回傳舊值
  return oldValue;
}

private void rangeCheck(int index) {
  if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
  return (E) elementData[index];
}

remove(Object)

// 洗掉指定元素：若元素重復，則只洗掉下標最小的元素
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) {
  // moCount是記錄ArrayList被修改次數的，該變數主要是用來實作fail-fast機制
  modCount++;
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 如果 index 不是最后一位，則將 index + 1 及之后的元素向前移動一位，覆寫被洗掉值
    System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  // 將最后一個元素置空，并將 size 值減 1
  elementData[--size] = null;
}

更新元素：set(int, E)

public E set(int index, E element) {
  rangeCheck(index); // 檢查是否陣列越界
  E oldValue = https://www.cnblogs.com/sbgong/archive/2022/11/14/elementData(index); // 獲取index索引處的舊值
  elementData[index] = element; // 將指定索引處的元素替換為 element
  return oldValue; // 回傳舊值
}

查詢元素：get()

// 獲取指定索引處的元素
public E get(int index) {
  rangeCheck(index); // 檢查是否越界
  return elementData(index); // 獲取并回傳index索引處的元素
}

private void rangeCheck(int index) {
  if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
  return (E) elementData[index];
}

本文來自博客園，作者：不二橘子醬，轉載請注明原文鏈接：https://www.cnblogs.com/sbgong/p/16887763.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/532543.html

標籤：其他

上一篇：冷知識：預處理字串運算子

下一篇：計算機等級考試二級C語言程式設計專項訓練題——陣列元素的移動

Java容器之ArrayList原始碼分析