文章目錄
-
- （一）、ArrayList概述
- （二）、類名
- （三）、屬性
- （四）、構造方法
- （五）、Add方法（擴容操作）
- （六）、Remove方法（删除元素）
- （七）、序列化
- （八）、trimToSize()方法
- （九）、indexOf()方法
- （十）、toArray()方法
- （十一）、batchRemove()方法（批量删除）
- （十二）、其他一些簡單方法
- （十三）、System.arraycopy() 和 Arrays.copyOf()之間的對比
- （十四）、ModCount字段的作用
更多Java容器源碼分析可以參考：Java容器源碼分析系列（持續更新中！）
（一）、ArrayList概述
- ArrayList是一個動态數組，基于數組實作，其容量能自動增長。
- ArrayList實作了RandomAccess接口，支援快速随機通路，實作了Serializable接口，是以它支援序列化，能夠實作序列化和反序列化，實作了Cloneable接口，能被克隆。
（二）、類名
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
分析：ArrayList是繼承自AbstractList，同時實作了List接口、RandomAccess接口，Clonable接口、Seriealzable接口。
- AbstractList：同樣也繼承了List接口，并且實作了List接口中的方法。
- 可能大家會有一個疑問就是為什麼ArrayList不直接去實作List接口，而是要通過AbstractList實作List接口之後，再去繼承。這裡主要是涉及了設計模式中的知識。當AbstractList已經實作了List接口之後，就已經實作了大部分需要的功能了。ArrayList隻需要完成一些想要的拓展功能即可。減少了代碼的重複。
- 還有一點比較奇怪的就是。為什麼AbstractList已經實作了List接口，ArrayList還要再次實作一次List接口。據ArrayList的作者說，這主要是當時自己的錯誤造成的，原本以為是為了以後拓展功能做鋪墊，實際并沒有什麼作用。
//AbstractList的源碼
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
- RandomAccess：RandomAccss實際是一個空接口，隻是起到辨別作用。
//RandomAcces接口的源碼
public interface RandomAccess {
}
- 主要起到辨別的作用。隻要實作了這個接口就支援随機通路。我們可以看一下Collections類中的binarySearch方法，方法中判斷了List是否實作了RandomAccess方法，如果實作了，那麼就使用indexedBinarySearch（普通for循環進行周遊）。反之沒有實作RandomAccess接口的話，則使用iteratorBinarySearch（疊代器進行周遊）
- 如果有興趣的朋友可以更進一步檢視兩種周遊的源碼，并進行測試。會發現，ArrayList使用普通for循環進行周遊效率更高，LinkedList使用疊代器進行周遊效率更高。想更深入了解的朋友可以看一下這篇文章：ArrayList集合實作RandomAccess接口有何作用？為何LinkedList集合卻沒實作這接口？
#Collections類中的binarySearch方法
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
#判斷是否實作了RandomAccess
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
- Cloneable：實作了Cloneable接口，就可以實作克隆功能
- Serializable：實作了Serializable接口，就可以實作序列化和反序列化功能
（三）、屬性
//序列化版本号
private static final long serialVersionUID = 8683452581122892189L;
/**
* 預設的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 當設定ArrayList長度為0時的空數組
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 初始化時未指定ArrayList的長度時的空數組
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* transient代表不能被序列化。這個數組用于儲存資料
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList中實際的數組長度
*
* @serial
*/
private int size;
- DEFAULT_CAPACITY：預設的初始化容量為10。
- EMPTY_ELEMENTDATA：當設定ArrayList長度為0時的空數組。
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA：初始化時未指定ArrayList的長度時的空數組。
- elementData：transient代表不能被序列化。這個數組用于儲存資料。
- size：數組的實際長度。
（四）、構造方法
/**
* 一個參數的構造方法，指定初始化容量
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果指定的容量大于0，則建立一個指定長度的數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果指定的容量為0，就建立一個空的數組
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果指定的容量小于0，則抛出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 無參構造方法，建立一個空數組，自動初始化容量為10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 以Collection作為參數的構造方法，主要是實作複制功能
*/
public ArrayList(Collection<? extends E> c) {
//首先将Collection轉換為數組并指派
elementData = c.toArray();
//判斷數組的長度是否等于0
if ((size = elementData.length) != 0) {
// 判斷是否為Object類型，如果不是的話，就是進行轉換
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 長度等于0，則指派為空數組
this.elementData = EMPTY_ELEMENTDATA;
}
}
- ArrayList()：無參構造方法，建立一個空數組，自動初始化容量為10
- ArrayList(int initialCapacity)：一個參數的構造方法，指定初始化容量
- ArrayList(Collection<? extends E> c)：以Collection作為參數的構造方法，主要是實作複制功能
（五）、Add方法（擴容操作）
/**
* 在ArrayList的末尾添加上元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 在指定的位置添加上元素
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 将另一個Collection對象添加到目前ArrayList中
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 在指定位置，将另一個Collection對象添加到目前ArrayList中
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
- Add（）方法主要涉及的是擴容操作，需要涉及很多個成員方法，但是基本操作大緻上都一樣，看懂一個，其他三個方法也能很容易明白。這裡就用add(int index, E element)方法進行舉例。
- 我們先來看add(int index, E element)的源碼，這個方法主要的功能是在指定位置插入元素。
public void add(int index, E element) {
//檢查要插入的位置是否合法
rangeCheckForAdd(index);
//確定數組的容量夠，如果不夠，進行擴容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index+1位置到末尾的元素全部往後移動一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在index位置上插入元素
elementData[index] = element;
//ArrayList的實際容量增加1
size++;
}
- 我們進入 rangeCheckForAdd(index)方法中，方法的實作很簡單，判斷index是否合法，如果不合法就抛出異常。
/**
* 檢視插入位置是否合法
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
//如果位置不合法就抛出異常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 接着我們就回到add()方法中，然後進入到ensureCapacityInternal(size + 1)方法中，因為是插入一個元素，是以就是最少需要的容量=實際容量size+1。進入方法後，首先要判斷是否是空數組，如果是空數組的話，要設定初始化容量為10。然後調用ensureExplicitCapacity(minCapacity);
/**
* 判斷是否是空數組，如果是空數組的話，要設定初始化容量為10
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//判斷是否是空數組，如果是空數組的話，要設定初始化容量為10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//調用方法。
ensureExplicitCapacity(minCapacity);
}
- 然後我們進入到ensureExplicitCapacity(int minCapacity)方法中。modCount要先加1，這個屬性是在AbstractList中的，主要用來記錄修改操作，用來識别快速失敗(fast-fail機制)，有興趣可以了解一下。然後判斷最小容量是否大于目前數組的長度，如果大于就調用grow()方法進行擴容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判斷最小容量是否大于目前數組的長度，如果大于就調用grow()方法進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- 在grow()方法中，首先将原數組的容量指派給oldCapacity。然後将oldCapacity容量擴大為1.5倍指派給newCapacity。如果新的容量newCapacity還是小于最小容量，那麼就把最小容量指派給newCapacity。如果newCapacity超過了數組的最大容量就要調用hugeCapacity()方法進行擴容。最後就是利用Arrays.copyOf(elementData, newCapacity)建立一個新數組指派給elementData，完成擴容。
private void grow(int minCapacity) {
// 将原數組的容量指派給oldCapacity
int oldCapacity = elementData.length;
//進行移位運算，将oldCapacity容量擴大為1.5倍指派給newCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新的容量newCapacity還是小于最小容量，那麼就把最小容量指派給newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果newCapacity超過了數組的最大容量就要調用hugeCapacity()方法進行擴容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 利用Arrays.copyOf(elementData, newCapacity)建立一個新數組指派給elementData，完成擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 上一步中調用了hugeCapacity(minCapacity)方法，這個方法使用了三元表達式，如果最小容量大于最大數組長度，就傳回整數的最大值，否則傳回數組最大長度。
private static int hugeCapacity(int minCapacity) {
//範圍不合法
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//使用了三元表達式，如果最小容量大于最大數組長度，就傳回整數的最大值，否則傳回數組最大長度
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
（六）、Remove方法（删除元素）
/**
* 删除指定位置上的元素
*/
public E remove(int index) {
//首先判斷範圍是否合法
rangeCheck(index);
//修改次數+1，前面已經提到過了
modCount++;
//擷取index位置上的舊值
E oldValue = elementData(index);
//計算删除該位置的元素，需要移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
//将index+1後面的元素全部向前移動1位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将size-1位置的值設定為null，便于垃圾收集
elementData[--size] = null; // clear to let GC do its work
//傳回被删除的元素
return oldValue;
}
/**
* 删除指定對象的元素
*/
public boolean remove(Object o) {
//如果對象為null對象
if (o == null) {
//周遊數組
for (int index = 0; index < size; index++)
//如果發現有值為null，調用fastRemove()方法删除元素
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//周遊數組
for (int index = 0; index < size; index++)
//如果發現有值為o，調用fastRemove()方法删除元素
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
//沒有該元素，傳回false
return false;
}
- remove(int index)方法：删除指定位置上的元素，步驟如下：
- 首先判斷範圍是否合法
- 修改次數+1，前面已經提到過了
- 擷取index位置上的舊值
- 計算删除該位置的元素，需要移動元素的個數
- 将index+1後面的元素全部向前移動1位
- 将size-1位置的值設定為null，便于垃圾收集
- 傳回被删除的元素
- remove(Object o)方法：删除指定位置上的元素，步驟如下：
- 判斷對象是否為null對象
- 如果為null，周遊數組，進行删除
- 如果不為null，也周遊數組，進行删除
private void fastRemove(int index) {
//修改次數+1
modCount++;
//計算移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
//向前移動一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最後一位設定位null，利于垃圾收集
elementData[--size] = null; // clear to let GC do its work
}
删除過程中調用了fastRemove(int index)方法，這個方法其實就是将index位置後的元素全部向前移動1位，實作元素删除。
（七）、序列化
ArrayList中與序列化相關的方法主要有兩個， 分别是readObject()以及writeObject()
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
- writeObject()主要完成的是序列化操作
- 首先要判斷期望的ModCount和實際的ModCount是否相等，如果不相等說明發生了fast-fail（快速失敗）
- 利用for循環逐一将元素寫入到輸出流中
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
- readObject()主要完成的是反序列化操作
- 首先要判斷實際容量是否大于0，如果大于0，調整容量，根據實際大小來配置設定空間，而不是根據容量來配置設定空間。
- 利用for循環從流中寫入資料
（八）、trimToSize()方法
/**
* 将ArrayList的容量縮容為實際大小
*/
public void trimToSize() {
//修改次數+1
modCount++;
//如果實際大小小于容量
if (size < elementData.length) {
//三元表達式進行縮容
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
因為ArrayList的元素數目可能不等于數組的容量，是以有時為了節省空間，會對ArrayList進行縮容操作，将實際大小=數組容量。
（九）、indexOf()方法
/**
* 擷取某個元素的位置
*/
public int indexOf(Object o) {
//如果為null
if (o == null) {
//for循環進周遊，如果存在就傳回該位置
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//不為null，for循環進周遊，如果存在就傳回該位置
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//不存在傳回-1
return -1;
}
/**
* 逆序獲得指定元素的位置
*/
public int lastIndexOf(Object o) {
//如果為null
if (o == null) {
//for循環進周遊，如果存在就傳回該位置
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
//不為null，for循環進周遊，如果存在就傳回該位置
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
//不存在傳回-1
return -1;
}
- indexOf()和lastIndexOf()分别傳回指定元素在清單中正序和逆序的位置，實作較為簡單，代碼中有詳細注釋，很容易了解。
（十）、toArray()方法
/**
* 直接調用Arrays.copyOf(elementData, size)傳回一個新數組
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 這個是一個類型轉換的方法，将數組轉換為指定類型
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 傳回一個T類型的新數組
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//複制元素
System.arraycopy(elementData, 0, a, 0, size);
//辨別作用
if (a.length > size)
a[size] = null;
return a;
}
- toArray()方法主要用于清單的轉換，實作也較為容易，代碼中有詳細注釋
- toArray(T[] a)其中存在一些坑，詳細可見這篇文章：集合轉數組的toArray()和toArray(T[] a)方法
（十一）、batchRemove()方法（批量删除）
/**
* 用于批量删除
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
//擷取原數組中的元素
final Object[] elementData = this.elementData;
//設定兩個指針，初始值為0
int r = 0, w = 0;
//設定标志值modified，初始值為false
boolean modified = false;
try {
//删除操作
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//如果删除完成後，還有剩的，就補齊到原數組中
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果删除後，新數組的長度小于原數組的長度，将後面的值置位null，便于垃圾收集
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
- batchRemove(Collection<?> c, boolean complement)用于批量删除，complement參數取true的時候就不删除c中的元素，如果為false就删除c中的元素
- 如果删除完成後，還有剩的，就補齊到原數組中
- 如果删除後，新數組的長度小于原數組的長度，将後面的值置位null，便于垃圾收集
（十二）、其他一些簡單方法
/**
* 傳回實際大小
*/
public int size() {
return size;
}
/**
* 判斷是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 判斷是否包含該元素
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 重寫Object的克隆方法
*/
public Object clone() {
try {
//調用父類的克隆方法
ArrayList<?> v = (ArrayList<?>) super.clone();
//複制元素
v.elementData = Arrays.copyOf(elementData, size);
//mouCount重置
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
/**
* 擷取指定位置的元素
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 設定指定位置的元素值
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* 清空ArrayList()
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
- size()：傳回實際大小
- isEmpty()：判斷是否為空
- contains(Object o)：判斷是否包含該元素
- clone()：重寫Object的克隆方法
- get(int index)：擷取指定位置的元素
- set(int index, E element)：設定指定位置的元素值
- clear()：清空ArrayList()
（十三）、System.arraycopy() 和 Arrays.copyOf()之間的對比
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
- 首先來看System.arraycopy()方法，這個方法标為native，我們是看不到源碼的，說明不是使用java語言實作的。主要功能就是System.arraycopy() 僅拷貝數組的内容，不會建立新數組。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
- 然後是Arrays.copyOf()方法，我們可以看到他首先是根據newLength建立一個新的Object數組，然後同樣調用System.arraycopy()，複制到新數組中，并傳回新數組。
（十四）、ModCount字段的作用
- ModCount字段是主要是為了防止在多線程環境中，使用疊代器過程中，多個線程對集合進行修改操作，造成錯誤。
- 具體疊代器造成的這個坑，可以參見這篇文章：Java中的增強for循環的底層實作原理與坑
![九、設計模式以及查找、排序算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)