ArrayList 實現(xiàn)原理

1. ArrayList 概述

ArrayList 是 List 接口的可變數(shù)組的實現(xiàn)。實現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實現(xiàn)List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小。

每個ArrayList 實例都有一個容量，該容量是指用來存儲列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向ArrayList 中不斷添加元素，其容量也自動增長。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此，如果可預知數(shù)據(jù)量的多少，可在構造ArrayList 時指定其容量。在添加大量元素前，應用程序也可以使用ensureCapacity 操作來增加 ArrayList實例的容量，這可以減少遞增式再分配的數(shù)量。

注意，此實現(xiàn)不是同步的。如果多個線程同時訪問一個ArrayList 實例，而其中至少一個線程從結構上修改了列表，那么它必須保持外部同步。

2. ArrayList 的實現(xiàn)

對于 ArrayList 而言，它實現(xiàn) List 接口、底層使用數(shù)組保存所有元素。其操作基本上是對數(shù)組的操作。下面我們來分析ArrayList 的源代碼：

1) 底層使用數(shù)組實現(xiàn)

? ? ? private transient Object[] elementData；

2) 構造方法

ArrayList 提供了三種方式的構造器，可以構造一個默認初始容量為 10 的空列表、構造一個指定初始容量的空列表以及構造一個包含指定collection 的元素的列表，這些元素按照該collection 的迭代器返回它們的順序排列的。

3) 存儲：

ArrayList 提供了 set(int index, E element)、 add(E e)、 add(int index, E element)、

addAll(Collection<? extends E> c)、 addAll(int index, Collection<? extends E> c)這些添加

元素的方法。

下面我們一一講解：

4) 讀取

5) 刪除

ArrayList 提供了根據(jù)下標或者指定對象兩種方式的刪除功能。如下：

注意：從數(shù)組中移除元素的操作，也會導致被移除的元素以后的所有元素的向左移動一個位置。

6) 調(diào)整數(shù)組容量

從上面介紹的向 ArrayList 中存儲元素的代碼中，我們看到，每當向數(shù)組中添加元素時，都要去檢查添加后元素的個數(shù)是否會超出當前數(shù)組的長度，如果超出，數(shù)組將會進行擴容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實現(xiàn)。在實際添加大量元素前，我也可以使用ensureCapacity 來手動增加 ArrayList 實例的容量，以減少遞增式再分配的數(shù)量。

從上述代碼中可以看出，數(shù)組進行擴容時，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長大約是其原容量的1.5 倍。這種操作的代價是很高的，因此在實際使用時，我們應該盡量避免數(shù)組容量的擴張。當我們可預知要保存的元素的多少時，要在構造 ArrayList 實例時，就指定其容量，以避免數(shù)組擴容的發(fā)生?；蛘吒鶕?jù)實際需求，通過調(diào)用ensureCapacity 方法來手動增加 ArrayList 實例的容量。ArrayList 還給我們提供了將底層數(shù)組的容量調(diào)整為當前列表保存的實際元素的大小的功能。它可以通過trimToSize 方法來實現(xiàn)。

代碼如下：

7) Fail-Fast 機制

ArrayList 也采用了快速失敗的機制，通過記錄 modCount 參數(shù)來實現(xiàn)。在面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風險。具體介紹請參考我之前的文章深入Java 集合學習系列： HashMap 的實現(xiàn)原理 中的Fail-Fast 機制。