ArrayList 源碼分析（JDK1.8）

ArrayList簡介

  ArrayList 是一個數組隊列，相當于 動态數組。與Java中的數組相比，它的容量能動态增長。它繼承于AbstractList，實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

  ArrayList 繼承了AbstractList，實作了List。它是一個數組隊列，提供了相關的添加、删除、修改、周遊等功能。

  ArrayList 實作了RandmoAccess接口，即提供了随機通路功能。RandmoAccess是java中用來被List實作，為List提供快速通路功能的。在ArrayList中，我們即可以通過元素的序号快速擷取元素對象；這就是快速随機通路。稍後，我們會比較List的“快速随機通路”和“通過Iterator疊代器通路”的效率。

  ArrayList 實作了Cloneable接口，即覆寫了函數clone()，能被克隆。

  ArrayList 實作java.io.Serializable接口，這意味着ArrayList支援序列化，能通過序列化去傳輸。

  和Vector不同，ArrayList中的操作不是線程安全的！是以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。

下面讓我們翻開ArrayList的源代碼，看看一些常用的方法屬性，以及一些需要注意的地方。

1

ArrayList屬性

  ArrayList屬性主要就是目前數組長度size，以及存放數組的對象elementData數組，除此之外還有一個經常用到的屬性就是從AbstractList繼承過來的modCount屬性，代表ArrayList集合的修改次數。

public class ArrayList<E> extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

// 序列化id

private static final long serialVersionUID = 8683452581122892189L;

//預設初始容量為：10

private static final int DEFAULT_CAPACITY = 10;

//用于空執行個體的共享空數組執行個體。

private static final Object[] EMPTY_ELEMENTDATA = {};

//一個空對象，如果使用預設構造函數建立，則預設對象内容預設是該值

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//// 目前資料對象存放地方，目前對象不參與序列化

transient Object[] elementData;

// 目前數組長度

private int size;

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Arraylist構造方法詳細資訊

無參構造器：構造一個初始容量為 10 的空清單。

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

注意：此時我們建立的ArrayList對象中的elementData中的長度是1，size是0,當進行第一次add的時候，elementData将會變成預設的長度：10。

有參構造器（int 類型的參數）：構造一個具有指定初始容量的空清單。

如果傳入參數，則代表指定ArrayList的初始數組長度，傳入參數如果是大于等于0，則使用使用者的參數初始化，如果使用者傳入的參數小于0，則抛出異常。源碼如下：

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

參數：initialCapacity - 清單的初始容量

如果指定的初始容量為負，則會抛出： IllegalArgumentException

IllegalArgumentException：表明向方法傳遞了一個不合法或不正确的參數

有參構造器（Collection 類型的參數）：構造一個包含指定 collection 的元素的清單，這些元素是按照該 collection 的疊代器傳回它們的順序排列的。

public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();

if ((size = elementData.length) != 0) {

// c.toArray might (incorrectly) not return Object[] (see 6260652)

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

// replace with empty array.

說明：

1、這裡，我們将傳入的 collection 對象首先轉換成數組，并且把數組位址值指派給 elementData。

2、然後，根據轉換來的數組擷取數組的長度并且指派給 size 變量，同時判斷 size 的大小，如果 size 的值等于0，直接将空對象 EMPTY_ELEMENTDATA 的位址賦給 elementData。

3、如果 size 的值大于0，則執行Arrays.copy() 方法，把 collection 對象轉換來的内容（可以了解為深拷貝）copy 到elementData。

注意：this.elementData = arg0.toArray(); 這裡執行的簡單指派時淺拷貝，是以要執行 Arrays.copy() 做深拷貝

常用方法詳細資訊

get方法：傳回此清單中指定位置上的元素。

public E get(int index) {

rangeCheck(index);

return elementData(index);

private void rangeCheck(int index) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

1、rangeCheck(index) 方法：用來判斷傳入的索引是否正确，如果索引超出範圍 (index < 0 || index >= size())，該方法則會抛出 IndexOutOfBoundsException： 數組（下标）越界異常

2、如果傳入的索引正确，則會傳回指定索引位置的元素。

set方法：用指定的元素替代此清單中指定位置上的元素。

public E set(int index, E element) {

E oldValue = elementData(index);

elementData[index] = element;

return oldValue;

2、然後，通過索引擷取舊的元素，并且根據索引對清單就行元素更新，最後，傳回舊的元素。

add方法

add的方法有兩個，一個是帶一個參數的，一個是帶兩個參數的，下面我們一個個分析。

我們先來看帶一個參數的：

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

確定添加的元素有地方存儲，當第一次添加元素的時候this.size+1 的值是1，是以第一次添加的時候會将目前elementData數組的長度變為10：

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

//判斷是否是第一次添加元素的，如果是，則會将elementData數組的長度變為10；

//如果不是，則傳回 minCapacity 變量

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

return minCapacity;

将修改次數（modCount）自增1，判斷是否需要擴充數組長度,判斷條件就是用目前所需的數組最小長度與數組的長度對比，如果大于0，則增長數組長度。

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// overflow-conscious code

if (minCapacity - elementData.length > 0)

grow(minCapacity);

如果目前的數組已使用空間（size）加1之後 大于數組長度，則增大數組容量，擴大為原來的1.5倍。

private void grow(int minCapacity) {

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

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

然後，我們看另外一個add方法：

public void add(int index, E element) {

rangeCheckForAdd(index);

System.arraycopy(elementData, index, elementData, index + 1,

size - index);

size++;

//該方法主要判斷傳入的索引是否正确，這裡和 get() 方法中調用的 rangeCheck(index) 方法 一樣的作用，如果索引超出範圍 (index < 0 || index >= size())，該方法則會抛出 IndexOutOfBoundsException： 數組（下标）越界異常。

private void rangeCheckForAdd(int index) {

if (index > size || index < 0)

其中 ensureCapacityInternal（size + 1） 方法，已經在上面介紹，這裡就不作介紹了。

  經過上面的層層判斷，確定有足夠的容量之後，使用System.arraycopy 将需要插入的位置（index）後面的元素統統往後移動一位。并且将新的資料内容存放到數組的指定位置（index）上。

remove方法

其中 remove 方法有兩個，一個是根據索引進行元素移除的，一個是根據元素對象進行移除的：

我們先看其中的一個：

根據索引進行元素移除：

public E remove(int index) {

//判斷索引是否越界，越界則抛出數組越界異常。

//自增長修改次數

//将指定位置（index）上的元素儲存到 oldValue。

//将指定位置（index）上的元素都往前移動一位

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

//将原來的值oldValue傳回

21

注意：調用這個方法不會縮減數組的長度，隻是将最後一個數組元素置空而已。

根據元素對象進行元素移除：

public boolean remove(Object o) {

//首先判斷傳入的對象是否為 null

if (o == null) {

//如果傳入的對象為 null ，我們對 elementData 進行周遊，

for (int index = 0; index < size; index++)

if (elementData[index] == null) {

//循環周遊，找到了第一個為null 的對象，調用fastRemove（index）進行移除，其本質也是根據索引進行元素的移除。

fastRemove(index);

//傳回 true

// 如果傳入的對象不為 null ，則周遊 elementData 數組 并且判斷該對象是否與周遊的元素有相同的，如果有則調用 fastRemove(index) 進行移除，最後傳回 true。

if (o.equals(elementData[index])) {

//如果經過上面的層層判斷，沒有要移除的元素，則傳回 false。

return false;

//定位到需要remove的元素索引，先将index後面的元素往前面移動一位（調用System.arraycooy實作），然後将最後一個元素置空。

private void fastRemove(int index) {

22

23

24

25

26

27

28

29

30

31

32

33

34

clear方法：清空清單

public void clear() {

// clear to let GC do its work

//周遊 elementData ，并且對每個位置上的元素賦上 null 值

for (int i = 0; i < size; i++)

elementData[i] = null;

//然後，将 size 值指派為 0.

size = 0;

ArrayList 自帶的疊代器： listIterator

其疊代器有兩種：一種是有參的，一種是無參的

帶有參數的疊代器：可以根據指定的位置進行向前周遊，以及向後周遊。

public ListIterator<E> listIterator(int index) {

//首先判斷傳入的索引是否正确，如果索引超出範圍 (index < 0 || index >= size())，該方法則會抛出 IndexOutOfBoundsException： 數組（下标）越界異常。

if (index < 0 || index > size)

throw new IndexOutOfBoundsException("Index: "+index);

return new ListItr(index);

ListItr 是 ArrayList 中的内部類：

private class ListItr extends Itr implements ListIterator<E> {

ListItr(int index) {

super();

cursor = index;

//集合反向周遊時，判斷隐式遊标的上一個元素是否存在，存在傳回true,否則傳回false。

public boolean hasPrevious() {

return cursor != 0;

//傳回隐式遊标所指位置下一個元素的索引值。

public int nextIndex() {

return cursor;

//傳回隐式遊标所指上一個位置元素的索引值。

public int previousIndex() {

return cursor - 1;

@SuppressWarnings("unchecked")

public E previous() {

checkForComodification();

int i = cursor - 1;

if (i < 0)

throw new NoSuchElementException();

Object[] elementData = ArrayList.this.elementData;

if (i >= elementData.length)

throw new ConcurrentModificationException();

cursor = i;

return (E) elementData[lastRet = i];

// 從清單中将 next() 或 previous() 傳回的元素替換為e，比如：next() 取出為 a，可以通過set将a 替換為on。

public void set(E e) {

if (lastRet < 0)

throw new IllegalStateException();

try {

ArrayList.this.set(lastRet, e);

} catch (IndexOutOfBoundsException ex) {

// 在集合中插入指定元素，插入位置與最後一個操作next() 或previous()方法有關。

public void add(E e) {

int i = cursor;

ArrayList.this.add(i, e);

cursor = i + 1;

lastRet = -1;

expectedModCount = modCount;

throw new ConcurrentModificationException(http://www.my516.com);

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

總結：

ArrayList 其他特點：

ArrayList自己實作了序列化和反序列化的方法，因為它自己實作了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法

ArrayList基于數組方式實作，無容量的限制（會擴容）

添加元素時可能要擴容（是以最好預判一下），删除元素時不會減少容量（若希望減少容量，trimToSize()），删除元素時，将删除掉的位置元素置為null，下次gc就會回收這些元素所占的記憶體空間。

線程不安全

add(int index, E element)：添加元素到數組中指定位置的時候，需要将該位置及其後邊所有的元素都整塊向後複制一位

get(int index)：擷取指定位置上的元素時，可以通過索引直接擷取（O(1)）

remove(Object o)需要周遊數組

remove(int index)不需要周遊數組，隻需判斷index是否符合條件即可，效率比remove(Object o)高

使用iterator周遊可能會引發多線程異常

---------------------