ArrayList原始碼深度剖析，從最基本的擴容原理，到魔幻的迭代器和fast-fail機制，你想要的這都有！！！
2022-07-08 06:01:19
ArrayList原始碼深度剖析
本篇文章主要跟大家分析一下ArrayList的原始碼。閱讀本文你首先得對ArrayList有一些基本的瞭解，至少使用過它。如果你對ArrayList的一些基本使用還不太熟悉或者在閱讀本文的時候感覺有點困難，你可以先閱讀這篇文章ArrayList設計與實現，自己動手寫ArrayList。
ArrayList繼承體系分析
RandomAccess，這個介面的含義表示可以隨機存取ArrayList當中的資料，拿什麼是隨機存取呢？隨機存取就是表示我們可以在常數時間複雜度記憶體取資料，也就是時間複雜度是O(1)。因為在ArrayList當中我們使用的最基本的資料型別是陣列，而陣列是可以隨機存取的，比如像下面這樣。
public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < 10; i++)
data[i] = i;
System.out.println("data[5] = " + data[5]);
}
而連結串列是不可以隨機存取的，比如說我們想通過下標存取連結串列當中的某個資料，需要從頭結點或者尾節點開始遍歷，直到遍歷到下標對應的資料，比如下圖中的單連結串列找到第3個資料，需要從頭開始遍歷，而這個時間複雜度為O(n)。
Serializable，這個介面主要用於序列化，所謂序列化就是能將物件寫入磁碟，反序列化就是能夠將物件從磁碟當中讀取出來，如果想序列化和反序列化ArrayList的範例物件就必須實現這個介面，如果沒有實現這個介面，在範例化的時候程式執行會報錯，比如下面就是一個序列化的例子。
import java.io.*;
import java.util.Objects;
class TestPerson implements Serializable{
String name;
Integer age;
private static final long serialVersionUID = 9999L;
@Override
public String toString() {
return "TestPerson{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TestPerson that = (TestPerson) o;
return that.age.equals(this.age) && that.name.equals(this.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
public TestPerson(String name, Integer age) {
this.name = name;
this.age = age;
}
}
public class SerialTest {
public static void main(String[] args) throws IOException, ClassNotFoundException {
TestPerson leHung = new TestPerson("LeHung", 18);
FileOutputStream os = new FileOutputStream("objtest");
ObjectOutputStream outputStream = new ObjectOutputStream(os);
// 序列化資料
outputStream.writeObject(leHung);
FileInputStream is = new FileInputStream("objtest");
ObjectInputStream stream = new ObjectInputStream(is);
// 反序列化資料
TestPerson object = (TestPerson) stream.readObject();
System.out.println(object);
System.out.println(object == leHung);
System.out.println(object.equals(leHung));
}
}
如果上面程式當中的TestPerson沒有implements Serializable，則上述程式碼會報異常java.io.NotSerializableException:。
-
Cloneable，實現Cloneable介面那麼實現Cloneable的類就能夠呼叫clone這個方法，如果沒有實現Cloneable介面就呼叫方法，則會丟擲異常java.lang.CloneNotSupportedException。 -
List，這個介面主要定義了一些集合常用的方法讓ArrayList進行實現，比如add，addAll，contains，remove，set，size，indexOf等等方法。 -
AbstractList，這個抽象類也實現了List介面裡面的方法，並且為其提供了預設程式碼實現，比如說AbstractList中對indexOf的實現如下：
// 這個方法的作用就是返回物件 o 在容器當中的下標
public int indexOf(Object o) {
// 通過迭代器去遍歷資料
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
// 返回資料 o 的下標
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
// 返回資料 o 的下標
return it.previousIndex();
}
return -1;
}
集合的addAll方法實現如下：
// 這個函數的作用就是在 index 的位置插入集合 c 當中所有的元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
ArrayList關鍵欄位分析
在ArrayList當中主要有以下這些欄位：
// ArrayList 當中預設初始化容量，也就是初始化陣列的大小
private static final int DEFAULT_CAPACITY = 10;
// 存放具體資料的陣列 ArrayList 底層就是使用陣列進行儲存的
transient Object[] elementData;
// size 表示容器當中資料的個數 注意和容器的長度區分開來
private int size;
// 當容器當中沒有元素的時候將 elementData 賦值為以下資料（不同情況不一樣）
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 下面兩個函數是 ArrayList 的建構函式，從下面兩個函數當中
// 我們可以看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 使用區別
// EMPTY_ELEMENTDATA 是容器當中沒有元素時使用，DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 是預設構造的時候使用
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList主要方法分析
add方法，這個方法用於往容器的末尾增加資料，也是ArrayList當中最核心的方法。他的主要工作流程如下圖所示：
他首先呼叫函數ensureCapacityInternal確保ArrayList當中的陣列長度能夠滿足需求，不然陣列會報陣列下標越界異常，add函數呼叫過程當中所涉及到的函數如下。
public boolean add(E e) {
// 這個函數的主要目的是確保 elementData 的容量有 size + 1
// 否則儲存資料的時候陣列就會越界
ensureCapacityInternal(size + 1);
// size 表示容器當中資料的個數 注意和容器的長度區分開來
// 加入資料之後 容器當中資料的個數也要 + 1
elementData[size++] = e;
return true;
}
// minCapacity 表示 ArrayList 中的陣列最小的長度
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(
// 這個函數計算陣列的最小長度
calculateCapacity(elementData, minCapacity)
);
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是無參構造的話，取預設長度和需求長度 minCapacity 中比較大的值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 這個表示容器發生改變的次數，我們在後續分析迭代器的時候進行分析
// 它跟容器擴容沒關係，現在可以不用管他
modCount++;
// 如果最小的需求容量 minCapacity 大於現在容器當中陣列的長度，則需要進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新陣列的長度為原陣列的長度的1.5倍，右移一位相當於除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新陣列的長度，小於需要的最小的容量，則更新陣列的長度為 minCapacity
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 = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
上述程式碼的呼叫流程如下：
get函數，獲取對應下標的資料。
public E get(int index) {
// 進行陣列下標的檢查，如果下標超過 ArrayList 中資料的個數，則丟擲異常
// 注意這裡是容器當中資料的個數 不是陣列的長度
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
// 返回對應下標的資料
return (E) elementData[index];
}
remove函數，刪除ArrayList當中的資料。
// 通過下標刪除資料，這個函數的意義是刪除下標為 index 的資料
public E remove(int index) {
// 首先檢查下標是否合法，如果不合法，丟擲下標越界異常
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 因為刪除某個資料，需要將該資料後面的資料往陣列前面移動
// 這裡需要計算需要移動的資料的個數
int numMoved = size - index - 1;
if (numMoved > 0)
// 通過拷貝行動資料
// 這個函數的意義是將 index + 1和其之後的資料整體移動到 index
// 的位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 因為最後一個資料已經拷貝到前一個位置了，所以可以設定為 null
// 可以做垃圾回收了
elementData[--size] = null;
return oldValue;
}
// 這個函數的意義是刪除容器當中的第一個等於 o 的資料
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;
}
// 這個方法和第一個 remove 方法原理一致
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
}
set方法，這個方法主要是用於設定指定下標的資料，這個方法比較簡單。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
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);
}
}
這個方法我們在前面已經提到過了，不知道大家有沒有觀察到他的存取修飾符是public，為什麼要設定為public呢？這個意思很明顯，我們可以在使用ArrayList的時候自己呼叫這個方法，防止當我們在往容器中加入資料的時候頻繁因為陣列長度不夠重新申請記憶體，而原來的陣列需要從新釋放，這會給垃圾回收器造成壓力。我們在ArrayList設計與實現，自己動手寫ArrayList這篇文章當中寫過一段測試程式去測試這個方法，感興趣的同學可以去看看！！！
toString方法
我們首先來看一下下面程式碼的輸出
public class CodeTest {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
System.out.println(list);
}
}
// 輸出結果：
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
執行上面一段程式碼我們可以在控制檯看見對應的輸出，我們知道最終列印在螢幕上的是一個字串，那這個字串怎麼來的呢，我們列印的是一個物件，它是怎麼得到字串的呢？我們可以檢視System.out.println的原始碼：
public void println(Object x) {
String s = String.valueOf(x);
synchronized (this) {
print(s);
newLine();
}
}
從上述程式碼當中我們可以看見通過String s = String.valueOf(x);這行程式碼得到了一個字串，然後進行列印，我們在進入String.valueOf方法看看是如何得到字串的：
public static String valueOf(Object obj) {
return (obj == null) ? "null" : obj.toString();
}
我們可以看到如果物件不為 null 最終是呼叫物件的toString方法得到的字串。因此當列印一個物件的時候，最終會列印這個物件的toString方法返回的字串。
toString方法沒有直接在ArrayList當中實現，而是在它繼承的類AbstractList當中實現的，toString的原始碼如下所示：
public String toString() {
// 得到 ArrayList 的迭代器 這個迭代器我們稍後細說
Iterator<E> it = iterator();
// 如果容器當中沒有資料則返回空
if (! it.hasNext())
return "[]";
// 額，寫這個程式碼的工程師應該不懂中文 哈哈哈
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
// 將物件加入到 StringBuilder 當中，這裡加入的也是一個物件
// 但是在 append 原始碼當中會同樣會使用 String.ValueOf
// 得到物件的 toString 方法的結果
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
上述程式碼的整個過程還是比較清晰的，大致過程如下：
- 如果容器當中沒有資料，直接返回[]。
- 如果容器當中有資料的話，那麼通過迭代每個資料，呼叫
StringBuilder的append方法，將資料加入到輸出的StringBuilder物件當中，下面是append的原始碼。
// StringBuilder 的 append 方法
@Override
public StringBuilder append(Object obj) {
return append(String.valueOf(obj));
}
// StringBuilder 的 append 方法的過載方法
@Override
public StringBuilder append(String str) {
super.append(str);
return this;
}
// String 類中的 valueOf方法
public static String valueOf(Object obj) {
return (obj == null) ? "null" : obj.toString();
}
我們可以發現最終append到StringBuilder當中的字串仍然是ArrayList當中資料物件的toString方法返回的資料。
equals方法
在ArrayList當中的equals方法和toString方法一樣，equlas方法也是在類AbstractCollection當中實現的，其原始碼如下：
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
上面程式碼的主要流程：
- 首先判斷
o和this是否是同一個物件，如果是則返回true，比如下面這種情況：
ArrayList<Object> list = new ArrayList<>();
list.equals(ArrayList);
- 如果物件沒有實現
List介面返回false。 - 逐個判斷連結串列裡面的物件是否相等（呼叫連結串列當中儲存的物件的
equals方法），如果兩個連結串列當中節點數目一樣而且都相等則返回true否則返回false。
通過上面的分析我們可以發現ArrayList方法並沒有讓比較的物件是ArrayList物件，只需要實現List介面並且資料數目和內容都相同，這樣equals方法返回的結果就是true，比如下面程式碼就驗證的這個結果：
LinkedList<Integer> list = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
arrayList.add(i);
}
System.out.println(arrayList.equals(list)); // 結果為 true
clone方法
ArrayList的方法比較簡單，就是拷貝了原ArrayList當中的陣列中的資料。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
整個拷貝過程如下如所示：
雖然發生了陣列的拷貝，但是拷貝之後的陣列中資料的指向並沒有發生變化，也就是說兩個陣列指向的內容是一樣的，如果一個陣列改變了所指向的資料，另外一個陣列當中的資料也會發生變化。比如下面的程式碼：
package makeyourowncontainer.test;
import java.util.ArrayList;
class Person {
String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
'}';
}
}
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Person> o1 = new ArrayList<>();
Person person = new Person();
person.setName("一無是處的研究僧");
o1.add(person);
Object o2 = o1.clone();
System.out.println("o1 = " + o1);
System.out.println("o2 = " + o2);
((ArrayList<Person>) o2).get(0).setName("LeHung");
System.out.println("改變資料之後");
System.out.println("o1 = " + o1);
System.out.println("o2 = " + o2);
}
}
// 輸出結果
o1 = [Person{name='一無是處的研究僧'}]
o2 = [Person{name='一無是處的研究僧'}]
改變資料之後
o1 = [Person{name='LeHung'}]
o2 = [Person{name='LeHung'}]
神祕的迭代器Iterator
Iterator介紹
我們在分析toString方法的時候，有下面這樣一行程式碼：
Iterator<E> it = iterator();
然後不斷通過迭代器的hasNext和next方法對資料進行迭代，比如下面這個例子：
public void testArrayList() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++)
list.add(i);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
// iterator 方法返回的物件
public Iterator<E> iterator() {
return new Itr();
}
Iterator欄位分析
Itr類是ArrayList的內部類，接下來我們仔細分析Itr類的實現。
在Itr類當中主要有一下幾個欄位：
int cursor; // 下一個元素的下標 當我們 new 這個物件的時候這個值預設初始化為0
// 我們使用的時候也是0這個值，因此不用顯示初始化
int lastRet = -1; // 上一個通過 next 方法返回的元素的下標
int expectedModCount = modCount;
// modCount 表示陣列當中資料改變的次數 modCount 是
// ArrayList 當中的類變數 expectedModCount 是 ArrayList
// 內部類 Itr 中的類變數 然後將這個變數儲存到 expectedModCount當中
// 使用 expectedModCount 主要用於 fast-fail 機制這個我們後面會分析
我們現在來花點時間好好談一下modCount（英文全稱為：modifications count，修改次數）這個欄位。當ArrayList當中發生一次結構修改(Structural modifications)時，modCount就++。所謂結構修改就是那些讓ArrayList當中陣列的資料個數size發生變化的操作，比如說add、remove方法，因為這兩個方法一個是增加資料，一個是刪除資料，都會導致容器當中資料個數發生變化。而set方法就不會是的modCount發生變化，因為沒有改變容器當中資料的個數。
Iterator的初始化方法：
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
}
在初始化方法當中，沒有任何操作也就印證了我們前面在分析欄位的時候說的 cursor的初始化的值為0。
Iterator重要方法
接下來分析迭代器當中比較重要的兩個方法next和hasNext。
public boolean hasNext() {
// 這個 size 是外部類 ArrayList 當中的 size 表示的是 ArrayList
// 當中資料元素的個數，cursor 的初始值為 0 每呼叫一個 next cursor
// 的值就+1，當等於 size 是容器當中的資料已經遍歷完成了 hasNext 就返回 false 了
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 這個方法主要是用於檢測在資料迭代的過程當中 ArrayList 是否發生 `結構修改`
// 如果發生結構修改就丟擲 ConcurrentModificationException 異常
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 更改 cursor 的值 並將其設定為下一個返回元素的下標 這一點我們在
// 欄位分析的時候已經談到過了
cursor = i + 1;
// 返回資料 表示式 lastRet = i 的返回值為 i
// 這個表示式不僅將 lastRet 的值賦值為 i 同時返回 i
// 因此可以返回下標為 i 的資料
return (E) elementData[lastRet = i];
}
// 這個方法主要是用於檢測在資料迭代的過程當中 ArrayList 是否發生 `結構修改`
// 如果發生結構修改就丟擲 ConcurrentModificationException 異常
final void checkForComodification() {
// 如果發生 `結構修改` 那麼 modCount 的值會++ 那麼就和 expectedModCount 不相等了
// expectedModCount 初始化的時候令其等於 expectedModCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
為什麼要丟擲ConcurrentModificationException異常呢，我們先想想是什麼導致modCount發生變化。肯定迭代器在進行遍歷的同時，修改了modCount的值，通常這種現象的發生出現在並行的情況下，因此丟擲ConcurrentModificationException異常。像這種通過迭代器遍歷過程進行檢查並且當發生不符合條件的情況下丟擲異常的現象就稱作Fast-fail。
其實我們也可以在不使用並行的情況讓迭代器丟擲這個異常，我們只需要在迭代器迭代的時候我們對ArrayList進行add和remove操作即可。比如像下面這樣就會丟擲ConcurrentModificationException：
public void testArrayList() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++)
list.add(i);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
list.add(55);
}
}
Iterator中的remove方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 進行合法性檢查，看是否需要丟擲異常
checkForComodification();
try {
// 呼叫 ArrayList 的remove方法實現
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 因為 remove 會改變 modCount 的值，因此需要將 expectedModCount 重新賦值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
ArrayList雜談
時間複雜度分析
- 因為
ArrayList是隨機存取的，因此我們通過下標查詢資料的時間複雜度是O(1)。 - 插入資料的時間複雜度是
O(n)。
擴容機制
還記的我們在ArrayList設計與實現，自己動手寫ArrayList當中自己實現ArrayList使用的擴容機制嗎？我們自己的擴容機制為擴容為原來長度的兩倍，而ArrayList當中的擴容機制為擴容為原來的1.5倍。
假設我們在使用ArrayList的時候沒有指定初始化的時候陣列的長度，也就是說初始長度為ArrayList的預設長度也就是10。那麼當我們不停地往容器當中增加資料，擴容導致的陣列長度的變化如上圖所示，橫軸表示擴容次數，縱軸表示陣列長度，藍色的擴容為原陣列長度的1.5倍，另外一條是2倍。我們很清晰的發現擴容為原來的2倍在後期的陣列長度將會遠大於擴容1.5倍。這很可能會導致我們會浪費很大的陣列空間，比如說剛好加入最後一個資料的時候導致ArrayList進行擴容操作，這可能是ArrayList在設計時候的考量。
本篇文章我們仔細分析介紹了ArrayList的原始碼，希望大家有所收穫，我是LeHung，我們下期再見！！！
關注公眾號：一無是處的研究僧，瞭解更多計算機知識。
