揭開ArrayList的外衣，看本質?

mp.weixin.qq.com圖標

源碼還是比較多的，安安靜靜的讀完確實不易，所以我們讀源碼要有著重點。

  • ArrayList的繼承和實現關係
  • ArrayList的成員
  • ArrayList的構造
  • ArrayList的容量與擴容問題
  • ArrayList的遍歷刪除修改操作

1 繼承和實現

看下ArrayList的定義：

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

ArrayList繼承了 抽象類AbstractList，實現了 List介面，並且實現了RandomAccess, Cloneable, java.io.Serializable這三個標記介面，標記介面中是沒有

聲明任何方法的，沒有方法並不代表沒有用，他們分別表示ArrayList具有可隨機訪問，可克隆及可序列化能力。

我們通過一張UML圖來看可能更直觀：

2 成員

初始化容器常量

/**
* 靜態常量 空數組 用於返回 元素為空的實例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空數組 和 EMPTY_ELEMENTDATA 用於區別，以便在第一個元素添加時知道擴容多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

修改次數

//用來記錄集合結構變動的次數
protected transient int modCount = 0;

默認容量

/**
* 靜態常量 默認容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 包含元素的數量，私有變數只能通過size()方法獲得
*/
private int size;

/**
* 數組的最大長度，一些虛擬機在存儲數組對象時會將一些頭信息存入其中，
* 分配過大的數組空間很可能導致 OOM，數組長度超過VM的限制。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

看到上面的 DEFAULT_CAPACITY，你是不是真的信了，默認容量是10 ？（稍後揭曉）存儲容器

/**
* 聲明一個默認許可權的數組,用以存儲元素,只能在本類或本包中訪問
*/
transient Object[] elementData;

上面這些成員中，主角就是 elementData，這個數組就是我們存儲對象的地方。為什麼使用數組呢？那麼來補補數組的知識。

數組1. 數組 和其他容器之間的區別有三方面：效率，類型和保存基本類型的能力。2. 數組是一種效率最高的的存儲和隨機訪問對象的方式，它是一種簡單的線性序列，這使得元素訪問非常快速，但代價是它的長度是被固定的，在它生命週期中是不可以變更的。3. 訪問數組的唯一方式就是使用數組索引，即我們常說的下標。

內部類及嵌套類

  • SubList

ArrayList的一個子集視圖，為什麼說是視圖呢？因為它展示的就是ArrayList中的部分元素，無論改變它本身還是ArrayList，雙方都會手影響。

  • Itr

迭代器Iterator介面的實現類。

  • ListItr

繼承於Itr，是Itr的功能增強版。

  • ArrayListSpliterator

分割迭代器，可以將迭代器分割一分為二，依次類推。

3 構造方法我們都用過 ArrayList ，但最常用的應該是 new ArrayList() 或者 new ArrayList(10) 吧！其實構造方法有三種，我們依次來看看：

指定容量構造

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

  • 指定初始容量後便創建一個指定大小的數組賦值給elementData
  • 如果指定容量為0，則將elementData指向上面成員常量中的第一個空數組
  • 若指定容量為負數，則拋出異常

無參構造

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

嗨！有沒有發現不對啊？不是說好的默認容量是10嗎？那這句話是嘛意思？這明顯是是賦了一個空數組嘛……其實在之前的1.6版本中確實初始化時是10，你看：

public ArrayList() {
//這裡調用第一個指定容量的構造方法，傳入了10作為初始容量
this(10);
}

指定集合構造

public ArrayList(Collection<? extends E> c) {
//調用集合的toArray()方法將集合轉為數組
elementData = c.toArray();
if ((size = elementData.length) != 0) {

if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

這裡主要是將傳入的集合通過toArray()轉為數組，然後賦值給elementData。4 容量與擴容繼續說說默認容量這回事，如今的版本中數組初始化時的容量確實為0，作者把默認容量從初始化時延遲到了第一次添加元素時。

public boolean add(E e) {
//判斷是否擴容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果當前集合中元素為空，那麼 選取 默認容量和最小容量 中的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

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

// 擴容時機：當容量全部被佔用完時，那麼進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

抓住上面的3個重點：1. 添加元素時都會判斷當前是否需要擴容2. 如果構造集合時指定默認容量，那麼本次擴容到103. 只有當容量全部被佔用時才會擴容（除主動擴容和第2條時）

private void grow(int minCapacity) {
int oldCapacity = elementData.length;

//新容量為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

//如果擴容1.5倍後還不滿足需要的最小容量
// 那麼就直接擴容到所需的最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//複製原來數組元素到一個新長度的數組中
elementData = Arrays.copyOf(elementData, newCapacity);
}

這段代碼展示的是擴容到多大，oldCapacity >> 1 就相當於 oldCapacity/2, 把容量擴大到原來的1.5倍。5 遍歷刪除修改

List<String> list = new ArrayList<>(Arrays.asList("code","code","test","hello"));

錯誤一

for(inti=0;i<list.size();i++){
String a=list.get(i);
if (a.equals("code")) {
list.remove(a);
}
}

為什麼第二個code沒有被刪除？你會發現它刪除的元素之後的一個元素會被遍歷跳過。因為刪除元素後，其右邊的所有元素都往前移動了一位，而你的下標卻一直增加。

錯誤二

for (String s: list) {
if (s.equals("code")){
list.remove(s);
}
}

你將會得到一個ConcurrentModificationException異常。

錯誤三

list.forEach(s -> {
list.remove(s);
});

你同樣得到一個ConcurrentModificationException異常。好吧，這下看出問題了，只要你在遍歷list時調用自身的remove方法，都是不對的。

分析

錯誤二使用的其實是Iterator的方式遍歷的，錯誤三使用的是forEach方法，我們看下源碼都發現了一個共同之處：

int expectedModCount = modCount;
//省略步驟
if (modCount != expectedModCount)
throw new ConcurrentModificationException();

如果再遍歷的過程中，modCount發生了改變(remove,set等)就會導出拋出異常。

正確方式

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer next = iterator.next();
iterator.remove();
}

為什麼這樣可以？因為 iterator.remove()方法在刪除元素後，將下標回撥了一位。6 最後
  • ArrayList 的讀取速度非常快，我想原因你應該知道了，這得益於底層的數組。
  • ArrayList 頻繁擴容將會導致性能下降，因為每次擴容都會複製原來的數組到創建的新數組。
  • ArrayList 插入時會移動數組元素，插入越靠前，移動的元素就越多，效率越差。

源碼閱讀 在GItHub上：

flyhero/JDK8-Note?

github.com

推薦閱讀（點擊標題可跳轉閱讀）

1. 千萬不要這樣使用 Arrays.asList !

2. 八張圖帶你認識Java3. 不同時重寫equals和hashCode又怎樣！

推薦閱讀：
相關文章