ArrayList數組主要方法純源碼分析：
- 1.add(E e)方法和newCapacity()方法:
-
- 1.1.add(E e)方法：
- 1.2.擴容方法newCapacity(int minCapacity) ：
- 1.2.1.首先是擴容時機：
- 1.2.2.擴容函數：
- 1.2.3.擴容函數的執行順序：
- 1.2.4.void add(int index, E element)方法:
- 2.構造方法：
-
- 2.1.有參構造方法1：
- 2.2.無參構造方法：
- 2.3.有參構造方法2：
- 3.Get()方法：
- 4.remove()方法：
-
- 4.1.remove(int index)方法：
- 4.2.remove(Object o)方法：
- 4.3.removeRange(int fromIndex, int toIndex)方法：
- 4.4.removeAll(Collection<?> c)方法：
- 5.set(int index, E element)方法：
- 6.Clear()方法：
ArrayList數組主要方法純源碼分析：
)
1.add(E e)方法和newCapacity()方法:
1.1.add(E e)方法：
一.由于第一次添加時擴容的特殊性，是以先以第一次添加元素觀察第一種add()方法（
add(E e)
）和擴容函數以及複制函數，可謂一箭三雕。需要注意的是：size代表現在數組中元素個數,minCapacity代表當插入資料後數組元素個數。
斷點Debug強制進入函數進入，
進入add()方法，s就是size，
建立對象時未傳參，預設長度大小為0，進入grow()方法，傳回值為新數組，
minCapacity變為1（代表當插入資料後數組元素個數），再進入另一個grow()方法，傳回值為新數組,
進入Arrays.copyof()方法，該方法傳回值為新數組,
進入newCapacity()方法，傳回新數組長度（擴容後）
新數組長度=舊數組長度+擴容長度（算法）
判斷擴容後的數組長度是否大于添加元素後總元素個數，但值得注意的是：第一次擴容經過擴容算法後新數組長度依舊為0，這是個特例，故第一次擴容後新數組長度為10,
執行完newCapacity()方法後遞歸回Arrays.copyof()方法，該方法的操作：舊數組長度計算新數組長度（newCapacity()方法）和複制舊數組資料到新數組，是以要傳舊數組。傳回值為新數組（包含原來資料）。
下圖為進入Arrays.copyof()的第一個copyof()方法，第一個copyof()方法有newLenght，說明先執行了newCapacity()方法，由第一個進入第二個copyof()方法，該方法利用原數組和newCapacity()得到的新數組長度得到新數組（包含原來資料，不包含新資料）。
第一次擴容新數組長度為10的來源：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
下面都是遞歸傳回了，
這裡特别注意：grow()方法後得到一個新數組（包含原數組資料），然後再添加新資料到新數組中，新數組現有總元素個數加1，
1.2.擴容方法newCapacity(int minCapacity) ：
二.大家其實不難發現，此次add值數組進行了擴容，那麼大家就會糾結到底什麼時候數組會進行擴容，如何擴容？這就關系到一下幾行代碼：
1.2.1.首先是擴容時機：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
每次進入add()方法裡面都會有一個目前數組元素個數和目前數組長度的比較（也就是說在即将添加元素之前看看數組是不是已經滿了），如果為真，就進入grow()方法進行擴容，這就是擴容時機：
if (s == elementData.length)
elementData = grow();
1.2.2.擴容函數：
/**
* Returns a capacity at least as large as the given minimum capacity.
* Returns the current capacity increased by 50% if that suffices.
* Will not return a capacity greater than MAX_ARRAY_SIZE unless
* the given minimum capacity is greater than MAX_ARRAY_SIZE.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? 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;
}
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
很明顯擴容後新數組總長度=舊數組長度+擴容量
對于oldCapacity >> 1 可能會有小白不明白：
首先，<<為左移，>>為右移（簡單記法：箭頭向左為左移，箭頭向右為右移），對于右移，例如01110010，可以把01110010看成計算機網絡裡發送視窗裡的的位元組，每位代表一個位元組，隻是這裡有些特别：隻能顯示視窗中的數字，并且視窗左右兩邊的都是0。當右移1位時，相當于把這串二進制往右挪1位，最右邊的0在視窗外了，同時視窗左邊的外部的0進入到視窗，即01110010>>1結果為00111001，同理01110010>>2的結果為00011100,01110010>>3的結果為00001110…….就是這樣的規律，左移規律一樣，讀者可以自行嘗試。
同時：右移1位整體數值就變為原來的1/2（也就是原數值除以2^1）。
也就是說右移N為，整體數值就除以2^N。
1.2.3.擴容函數的執行順序：
- 先按照擴容算法擴容。
- 判斷擴容後新數組長度是否滿足添加元素後數組長度要求。根據擴容時機
if (s == elementData.length) elementData = grow();
if (newCapacity - minCapacity <= 0)
if (newCapacity - minCapacity <= 0)
- 判斷即将添加資料後數組總長度是否大于
MAX_ARRAY_SIZE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
@Native public static final int MAX_VALUE = 0x7fffffff;
-
舉個擴容例子：
通過擴容函數不難看出，第一次擴容為10（當然，這是相對于當初建立ArrayList對象時執行無參構造方法的預設數組長度），即執行
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
後newCapacity為0，
然後執行到
if (newCapacity - minCapacity <= 0)
符合條件進入，
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
傳回10。
第二次擴容：執行
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
後，
即
int newCapacity = oldCapacity + (oldCapacity >> 1);
翻譯為 15=10+10/2，
第三次擴容：22.5=15+7.5，
第四次擴容：33.75=22.5+111.25……
不難發現從第二次擴容開始，每次擴容都是上一次的1.5倍（包括第二次擴容）。
1.2.4.void add(int index, E element)方法:
将元素插入到數組相應index位置。這個跟第一個add()方法有幾點不同：
1.增加了index合法檢查的函數。進入
rangeCheckForAdd(index);
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.當需要擴容時有一次建立新數組，一次對新數組index後的元素移動操作：
先擴容：
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
跟第一個add()一樣，就是根據擴容算法算出新數組長度，根據新數組長度建立新數組，将原來數組中的資料複制上去，傳回新數組（不需要擴容時直接跳過這一步到下面的移動數組）。
再移位，不用猜也肯定知道，既然要指定數組index插入資料，必然要将index後的元素向後移動，但這裡注意的是，它這次的操作的源數組和目标數組都是同一個數組，都是擴容後的新數組。
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
解析一下：将新數組的index位置開始的元素複制到的index+1的位置上，s-index，就是index開始後面的所有元素，也就是說将index後的元素整體向後挪一個位置。
最後留下指定index的空位，插入指定元素。
2.構造方法：
2.1.有參構造方法1：
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
對于函數裡面幾個關鍵的數組定義需要了解一下：
NO.1
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
NO.2
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
NO.3
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
是以說當
initialCapacity == 0
時（也就是指定容量為0時），使用
private static final Object[] EMPTY_ELEMENTDATA = {};
将空數組
EMPTY_ELEMENTDATA
賦給存儲資料的數組。
2.2.無參構造方法：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
由有參構造方法中的N0.1可知，使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
将空數組
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
賦給存儲資料的數組
elementData
。
2.3.有參構造方法2：
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
1.
ArrayList(Collection<? extends E> c)：
構造一個包含指定 collection 的元素的清單，這些元素是按照該 collection 的疊代器傳回它們的順序排列的。該有參構造方法構造時賦的值是它的父類對象Collection（可以了解為父類引用指向子類對象）。
2.将collection對象轉換成數組，然後将數組的位址的賦給elementData。
3.如果數組的實際大小等于0（c中沒有元素），根據上面的NO.2将空數組
EMPTY_ELEMENTDATA
指派給
elementData
（因為它畢竟也是有參構造函數，不是預設的）
4.如果size的值大于0（說明collection中有值），則執行
Arrays.copy()
方法，把collection對象的内容（可以了解為深拷貝）copy到elementData中。
3.Get()方法：
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
分析：
Objects.checkIndex(index, size);
檢查index的合法性，具體檢查規則：
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
4.remove()方法：
4.1.remove(int index)方法：
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
分析：跟get()方法一樣，都有檢查index的合法性。關鍵是
fastRemove(es, index);
方法。該方法裡的
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
的了解：首先明白要麼是擴容（複制原數組内容到新數組）要麼是對同一個數組進行元素移動，兩者差別在于
System.arraycopy(es, i + 1, es, i, newSize - i);
的源數組和目标數組是否相同。顯而易見，這明顯是對同一個數組進行元素移動（根據數組删除非末尾元素後該元素後面的元素都要向前移動也能判斷）。既然說是删除非末尾元素元素才進行移動，那麼删除末尾元素就不用移動了，也就是說
if ((newSize = size - 1) > i)
判斷待删除元素的index是否是末尾元素，如果是就不用執行
System.arraycopy(es, i + 1, es, i, newSize - i);
，直接執行
es[size = newSize] = null;
将待删除index中元素的值賦為null；
4.2.remove(Object o)方法：
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) { //對象的指向為空
for (; i < size; i++)
if (es[i] == null)//周遊找出這樣的對象
break found;//找到跳出循環執行fastRemove(es, i);删除
} else {//對象的指向不為空
for (; i < size; i++)
if (o.equals(es[i]))//周遊找出對象内容跟傳入對象内容一樣的
break found; //找到跳出循環執行fastRemove(es, i); ;删除
}
return false;
}
fastRemove(es, i);
return true;
}
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
4.3.removeRange(int fromIndex, int toIndex)方法：
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
/** Erases the gap from lo to hi, by sliding down following elements. */
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
分析：此方法删除lo到hi之間的全部元素，
System.arraycopy(es, hi, es, lo, size - hi);
将源數組的hi後面的元素移動到目标數組以lo開始的index。根據
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
可知複制後原來存在的且沒有被覆寫的資料資料并沒有消失，要置為null。
4.4.removeAll(Collection<?> c)方法：
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" >optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" >optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
上面這個版本比較難看，下面的比較容易看：
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//官方的注釋是為了保持和AbstractCollection的相容性
//我的了解是上面c.contains抛出了異常，導緻for循環終止，那麼必然會導緻r != size
//是以0-w之間是需要保留的資料，同時從w索引開始将剩下沒有循環的資料(也就是從r開始的)拷貝回來，也保留
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//for循環完畢，檢測了所有的元素
//0-w之間儲存了需要留下的資料，w開始以及後面的資料全部清空
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;
}
核心思想都在下面這個代碼裡：
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
簡單說一下這部分代碼的思想：
初始值：w和r都是0，complement==false
規律：
1.r值不斷自增，w并不是每輪都增加。
2.每次覆寫的時候elementData[w]必定集合c包含的值。
3.由于跳出循環後w=w+1，此刻最後一次elementData[w]不是集合c包含的值。
4.跳出循環後w所指index後的所有原數組的元素都已經有序前移了。是以有了後面這段代碼。
核心思想：每輪都找不屬于集合c的elementData[r] 去覆寫 elementData[w]，原因：w遲早h會走到集合c包含的元素的位置，并且w每走一個位置都會停下，直到找到一個不屬于集合c的elementData[r]去覆寫 elementData[w]（也就是說w所經過的位置的值都會用一個不屬于集合c的elementData[r]去覆寫）。
for (int i = w; i < size; i++)
elementData[i] = null;
将w後面的所有元素的值賦為null。
思想參考：核心思想領悟自
5.set(int index, E element)方法：
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
分析：這是更新相應index位置的元素。
6.Clear()方法：
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
分析：清空數組。