ArrayList源碼分析
注：JDK1.7
首先先來個總體的認識，ArrayList底層是用數組實作的。在插入值時如果超過了目前數組的大小，則會進行擴容操作，每次增加的大小為原來大小的“一半”（偶數一半，奇數減一的一半），并且按照新的大小建立一個相同類型的數組，然後将原數組中的值copy進新的數組，并修改引用。
預設建立ArrayList情況下：
然後了解下ArrayList繼承和實作的類和接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
總體有一個認知後從建立一個ArrayList講起吧。
初始化
首先建立一個ArrayList:
List<String> list = new ArrayList<String>();
相關源代碼
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
//首先會調用構造函數ArrayList()
public ArrayList() {
//調用父類構造函數
super();
//初始化elementData，ArrayList實際用來存儲資訊的數組
this.elementData = EMPTY_ELEMENTDATA;
}
//父類構造函數就略過了，在調用父類構造函數時會初始化modCount 成員變量，
//之後ArrayList就使用該變量來記錄自身經曆的修改次數。
AbstractList.class
protected transient int modCount = ; //修改/操作次數
這樣一個空的ArrayList就建立完畢了，當然，我們還可以自己定義初始數組的大小。之後都以預設建立方式說明。
List<String> list = new ArrayList<String>(20);
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < )
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
add()函數
相關源代碼
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;//記錄目前ArrayList儲存的資料量
private static final int DEFAULT_CAPACITY = ;//預設大小為10
//list.add("1") 調用函數，添加成功時傳回true
public boolean add(E e) {
//檢查數組容量，并進行擴容操作，size此時為0
ensureCapacityInternal(size + ); // Increments modCount!!
elementData[size++] = e;
return true;
}
//檢查數組容量，并在超過容量時擴容
private void ensureCapacityInternal(int minCapacity) {
//目前ArrayList（elementData 數組）為空，
//目前minCapacity = 1 ，DEFAULT_CAPACITY = 10,是以minCapacity = 10
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//現在minCapacity = 10
ensureExplicitCapacity(minCapacity);
}
//當超過容量時擴容數組
private void ensureExplicitCapacity(int minCapacity) {
//記錄一次插入操作
modCount++;
// overflow-conscious code
//超過數組容量，進行擴容，minCapacity = 10 > （elementData.length = 0）
if (minCapacity - elementData.length > )
//擴容操作
grow(minCapacity);
}
//擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//newSize = oldSize + oldSize >> 1 (等價于偶數/2,奇數-1/2)。
//現在elementData = {}，newCapacity = 0
int newCapacity = oldCapacity + (oldCapacity >> );
//newCapacity = 0，minCapacity = 10
if (newCapacity - minCapacity < )
//newCapacity = 10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > )
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//建立一個通類型數組，copy舊值并修改elementData引用
//現在newCapacity = 10
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.class
//即Arrays.copyOf函數，現在elementData = {} 空數組，newLength = 10
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
//因為建立時時ArrayList<String>
//(Object)newType = 'class [Ljava.lang.String;' String數組類
//(Object)Object[].class = 'class [Ljava.lang.Object;' Object數組類
//是以(Object)newType == (Object)Object[].class = false
//執行(String[]) Array.newInstance('class java.lang.String'->String類, newLength)
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//從original的0下标處開始複制Math.min(original.length, newLength)
//個值拷貝給copy，并從copy的0下标處開始指派
System.arraycopy(original, , copy, ,
Math.min(original.length, newLength));
return copy;
}
//即Array.newInstance
//按照提供的類型和大小生成一個該類型的數組
//傳回Object類型，因為數組類是Object類的子類，是以之後強轉成對應的數組類即可
public static Object newInstance(Class<?> componentType, int length)
throws NegativeArraySizeException {
return newArray(componentType, length);
}
讓我們接着之前建立的ArrayList講，運作
list.add("1")
，可以看上面給出的相關源代碼中的注釋，可以看到add如果不涉及擴容的話基本上隻做了modCount++和把值存入elementData數組中，非常簡潔明了，當存入的資訊數大于目前數組容量時會重新計算一個擴容大小，即
newSize = oldSize + (oldSize >> 1)
，然後根據新的大小和類型建立一個新的數組，然後将舊資訊copy到新的數組中，然後修改elementData引用。完成擴容操作後目前的值就能放的進數組了，然後将值存入即可。
這裡會遇到一些有意思的東西，順便回顧下
//泛型，這裡有個T
//第一個T：申明T為一個泛型
//第二個T：傳回一個T類型數組
//第三個T：一個形參為T類型數組
public static <T> T[] copyOf(T[] original ...)
//當然還可以寫成這樣,∠( ᐛ 」∠)_
public static <ᐛ> ᐛ ᐛ(ᐛ ᐛ){
return ᐛ;
}
然後還有一個add函數允許我們在指定位置添加資料
相關源代碼
public void add(int index, E element) {
//檢測指定位置是否合法
rangeCheckForAdd(index);
//和上面講的一樣，判斷是否擴容和增加modCount值
ensureCapacityInternal(size + ); // Increments modCount!!
//上面在copyOf函數中出現過，就是把指定位置處空出來，
//指定位置後的值儲存下标值都向後移動一位，可以看下圖，比較直覺一點
System.arraycopy(elementData, index, elementData, index + ,
size - index);
elementData[index] = element;
size++;
}
Arrays.class
private void rangeCheckForAdd(int index) {
if (index > size || index < )
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
get()函數
相關源代碼
//擷取index下标處的值
public E get(int index) {
//index是否超過數組大小
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//通知編譯器對下面這段代碼的警告保持沉默，即忽略該段代碼的警告
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
總體很簡單，也不多說什麼了。
indexOf()函數
相關源代碼
//傳回o在ArrayList中第一次出現時的下标值，不存在則傳回-1
public int indexOf(Object o) {
//為null時
if (o == null) {
for (int i = ; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = ; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -;
}
//最後出現的位置，和IndexOf原理一樣
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-; i >= ; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-; i >= ; i--)
if (o.equals(elementData[i]))
return i;
}
return -;
}
isEmpty()函數
相關源代碼，因為ArrayList類中有一個size變量用來記錄目前ArrayList包含的記錄數量，是以直接去檢查size是否為0即可
public boolean isEmpty() {
return size == ;
}
remove()函數
相關源代碼
//根據下标值删除
public E remove(int index) {
//判定下标值是否大于數組容量
rangeCheck(index);
//添加修改記錄
modCount++;
//擷取該下标處的值
E oldValue = elementData(index);
int numMoved = size - index - ;
//如果index不是數組的最後一個下标值
if (numMoved > )
//進行拷貝操作，将從index+1下标開始到最後一個的值都往前移動一位
System.arraycopy(elementData, index+, elementData, index,
numMoved);
//将數組大小相應的減小一位，并将減小後的數組的最後一位置為空，、
//以覆寫掉原來在這裡的舊值
elementData[--size] = null; // clear to let GC do its work
//删除成功，傳回該處的值
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//根據值删除
public boolean remove(Object o) {
//周遊查詢是否存在相等的值
if (o == null) {
for (int index = ; index < size; index++)
if (elementData[index] == null) {
//和上面按下标删值的過程一樣
fastRemove(index);
return true;
}
} else {
for (int index = ; index < size; index++)
if (o.equals(elementData[index])) {
//和上面按下标删值的過程一樣
fastRemove(index);
return true;
}
}
return false;
}
//和上面按下标删值的過程一樣
private void fastRemove(int index) {
//修改次數+1
modCount++;
//和上面按下标删值的過程一樣
int numMoved = size - index - ;
if (numMoved > )
System.arraycopy(elementData, index+, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
set()函數
相關源代碼
public E set(int index, E element) {
//前面出現過很多次了，判斷index是否超過數組容量
rangeCheck(index);
//elementData()也出現過很多次了，傳回index下标處的值
E oldValue = elementData(index);
//設定新值
elementData[index] = element;
return oldValue;
}
subList(start,end)函數
相關源代碼
//傳回從fromIndex到toIndex之間的數組
public List<E> subList(int fromIndex, int toIndex) {
//判斷fromIndex，toIndex是否數組越界
subListRangeCheck(fromIndex, toIndex, size);
//傳回fromIndex到toIndex之間的值
return new SubList(this, , fromIndex, toIndex);
}
//判斷fromIndex，toIndex是否數組越界
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < )
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
//因為整個SubList類太長，放上來比較占地方是以就截取了一段，基本和ArrayList相同
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
......
}
Iterator疊代器
//常見用法，周遊
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator iterator = list.iterator();
while(iterator.hasNext()){
String s = (String)iterator.next();
}
相關源代碼
//建立疊代器
public Iterator<E> iterator() {
return new Itr();
}
//截取了用到的一段
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//檢查修改次數是否有異常
checkForComodification();
//下一個傳回值的下标
int i = cursor;
//數組越界
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
//數組中還沒有那麼多值
if (i >= elementData.length)
throw new ConcurrentModificationException();
//修改遊标，進行下一輪查詢時用
cursor = i + ;
//傳回i處的值
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
以上，基本包含了常用的ArrayList相關函數。