核心源碼分析

2.1 類聲明

先來看一下類的聲明，有一個繼承（抽象類）和四個接口關(guān)系

public class ArrayList<E> extends AbstractList<E>

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

{

? ? // 源碼具體內(nèi)容...

}

RandomAccess 是一個標志接口（Marker）只要 List 集合實現(xiàn)這個接口，就能支持快速隨機訪問（通過元素序號快速獲取元素對象 —— get(int index)）

Cloneable ：實現(xiàn)它就可以進行克隆（clone()）

java.io.Serializable ：實現(xiàn)它意味著支持序列化，滿足了序列化傳輸?shù)臈l件

2.2 類成員

下面接著看一些成員屬性

// 序列化自動生成的一個碼，用來在正反序列化中驗證版本一致性。

private static final long serialVersionUID = 8683452581122892189L;

/**

* 默認初始容量大小為10

*/

private static final int DEFAULT_CAPACITY = 10;

/**

* 指定 ArrayList 容量為0（空實例）時，返回此空數(shù)組

*/

private static final Object[] EMPTY_ELEMENTDATA = {};

/**

* 與 EMPTY_ELEMENTDATA 的區(qū)別是，它是默認返回的，而前者是用戶指定容量為 0 才返回

*/

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**

* 具體存放元素的數(shù)組

* 保存添加到 ArrayList 中的元素數(shù)據(jù)（第一次添加元素時，會擴容到 DEFAULT_CAPACITY = 10 ）

*/

transient Object[] elementData; // non-private to simplify nested class access

/**

* ArrayList 實際所含元素個數(shù)（大?。?/p>

*/

private int size;

2.4 構(gòu)造方法

/**

* 帶參構(gòu)造函數(shù)，參數(shù)為用戶指定的初始容量

*/

public ArrayList(int initialCapacity) {

? ? if (initialCapacity > 0) {

? ? ? ? // 參數(shù)大于0，創(chuàng)建 initialCapacity 大小的數(shù)組

? ? ? ? this.elementData = new Object[initialCapacity];

? ? } else if (initialCapacity == 0) {

? ? ? ? // 參數(shù)為0，創(chuàng)建空數(shù)組（成員中有定義）

? ? ? ? this.elementData = EMPTY_ELEMENTDATA;

? ? } else {

? ? ? ? // 其他情況，直接拋異常

? ? ? ? throw new IllegalArgumentException("Illegal Capacity: "+

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);

? ? }

}

/**

* 默認無參構(gòu)造函數(shù)，初始值為 0

* 也說明 DEFAULT_CAPACITY = 10 這個容量

* 不是在構(gòu)造函數(shù)初始化的時候設(shè)定的（而是在添加第一個元素的時候）

*/

public ArrayList() {

? ? this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

/**

* 構(gòu)造一個包含指定 collection 的元素的列表

* 這些元素是按照該 collection 的迭代器返回它們的順序排列的。

*/

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

? ? // 將給定的集合轉(zhuǎn)成數(shù)組

? ? elementData = c.toArray();

? ? // 如果數(shù)組長度不為 0

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

? ? ? ? // elementData 如果不是 Object 類型的數(shù)據(jù)，返回的就不是 Object 類型的數(shù)組

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

? ? ? ? ? ? // 將不是 Object 類型的 elementData 數(shù)組，賦值給一個新的 Object 類型的數(shù)組

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

? ? } else {

? ? ? ? // 數(shù)組長度為 0 ，用空數(shù)組代替

? ? ? ? this.elementData = EMPTY_ELEMENTDATA;

? ? }

}

2.5 最小化實例容量方法

/**

* 最小化實例容量方法，可以根據(jù)實際元素個數(shù)，將數(shù)組容量優(yōu)化，防止浪費

*/

public void trimToSize() {

? ? modCount++;

? ? // 數(shù)組容量大于實際元素個數(shù)（例如10個元素，卻有15個容量）

? ? if (size < elementData.length) {

? ? ? ? // 根據(jù)元素實際個數(shù)，重新最小化實例容量

? ? ? ? elementData = (size == 0)

? ? ? ? ? ? ? EMPTY_ELEMENTDATA

? ? ? ? ? ? : Arrays.copyOf(elementData, size);

? ? }

}

2.5 擴容方法

這里只是按照順序介紹，后面還會專門針對擴容進行一個分析

/**

* 增加ArrayList實例的容量，如果有必要，確保它至少可以保存由最小容量參數(shù)指定的元素數(shù)量。

*/

public void ensureCapacity(int minCapacity) {

? ? //如果元素數(shù)組不為默認的空，則 minExpand 的值為0，反之值為10

? ? int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

? ? ? ? // any size if not default element table

? ? ? ? ? 0

? ? ? ? // larger than default for default empty table. It's already

? ? ? ? // supposed to be at default size.

? ? ? ? : DEFAULT_CAPACITY;

? ? // 如果最小容量大于已有的最大容量

? ? if (minCapacity > minExpand) {

? ? ? ? ensureExplicitCapacity(minCapacity);

? ? }

}

/**

* 計算最小擴容量（被調(diào)用）

*/

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

? ? // 如果元素數(shù)組為默認的空

? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

? ? ? ? // 獲取“默認的容量”和“傳入?yún)?shù) minCapacity ”兩者之間的最大值

? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);

? ? }

? ? return minCapacity;

}

/**

* 得到最小擴容量

*/

private void ensureCapacityInternal(int minCapacity) {

? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

/**

* 判斷是否需要擴容

*/

private void ensureExplicitCapacity(int minCapacity) {

? ? modCount++;

? ? // overflow-conscious code

? ? // 如果最小容量比數(shù)組的長度還大

? ? if (minCapacity - elementData.length > 0)

? ? ? ? // 就調(diào)用grow方法進行擴容

? ? ? ? grow(minCapacity);

}

/**

* 要分配的最大數(shù)組大小

*/

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

* ArrayList 擴容的核心方法

*/

private void grow(int minCapacity) {

? ? // 將當前元素數(shù)組長度定義為 oldCapacity 舊容量

? ? int oldCapacity = elementData.length;

? ? // 新容量更新為舊容量的1.5倍

? ? // oldCapacity >> 1 為按位右移一位，相當于 oldCapacity 除以2的1次冪

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

? ? // 然后檢查新容量是否大于最小需要容量，若還小，就把最小需要容量當作數(shù)組的新容量

? ? if (newCapacity - minCapacity < 0)

? ? ? ? newCapacity = minCapacity;

? ? // 再檢查新容量是否超出了ArrayList 所定義的最大容量

? ? if (newCapacity - MAX_ARRAY_SIZE > 0)

? ? ? ? // 若超出，則調(diào)用hugeCapacity()

? ? ? ? newCapacity = hugeCapacity(minCapacity);

? ? elementData = Arrays.copyOf(elementData, newCapacity);

}

/**

* 比較minCapacity和 MAX_ARRAY_SIZE

*/

private static int hugeCapacity(int minCapacity) {

? ? if (minCapacity < 0) // overflow

? ? ? ? throw new OutOfMemoryError();

? ? return (minCapacity > MAX_ARRAY_SIZE) ?

? ? ? ? Integer.MAX_VALUE :

? ? MAX_ARRAY_SIZE;

}

2.6 常規(guī)方法

/**

* 返回元素數(shù)量

*/

public int size() {

? ? return size;

}

/**

* 此列表元素數(shù)量為 0 則返回 true

*/

public boolean isEmpty() {

? ? return size == 0;

}

/**

* 此列表含有指定元素，則返回true

*/

public boolean contains(Object o) {

? ? return indexOf(o) >= 0;

}

/**

* 返回此列表中元素首次出現(xiàn)位置的索引

* 若不包含此元素，則返回 -1

*/

public int indexOf(Object o) {

? ? if (o == null) {

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

? ? ? ? ? ? if (elementData[i]==null)

? ? ? ? ? ? ? ? return i;

? ? } else {

? ? ? ? // 本質(zhì)就是循環(huán) equals 比對

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

? ? ? ? ? ? if (o.equals(elementData[i]))

? ? ? ? ? ? ? ? return i;

? ? }

? ? return -1;

}

/**

* 返回此列表中指定元素的最后一次出現(xiàn)的索引

* 如果此列表不包含元素，則返回 -1

*/

public int lastIndexOf(Object o) {

? ? if (o == null) {

? ? ? ? for (int i = size-1; i >= 0; i--)

? ? ? ? ? ? if (elementData[i]==null)

? ? ? ? ? ? ? ? return i;

? ? } else {

? ? ? ? // 逆向循環(huán) equals 比對

? ? ? ? for (int i = size-1; i >= 0; i--)

? ? ? ? ? ? if (o.equals(elementData[i]))

? ? ? ? ? ? ? ? return i;

? ? }

? ? return -1;

}

/**

* 返回 ArrayList 實例的淺拷貝

*/

public Object clone() {

? ? try {

? ? ? ? ArrayList<?> v = (ArrayList<?>) super.clone();

? ? ? ? // 實現(xiàn)數(shù)組的復(fù)制，參數(shù)為被復(fù)制者的參數(shù)

? ? ? ? v.elementData = Arrays.copyOf(elementData, size);

? ? ? ? v.modCount = 0;

? ? ? ? return v;

? ? } catch (CloneNotSupportedException e) {

? ? ? ? // this shouldn't happen, since we are Cloneable

? ? ? ? throw new InternalError(e);

? ? }

}

/**

* 返回一個包含此列表中所有元素的數(shù)組（理解為將集合轉(zhuǎn)為數(shù)組即可）

*/

public Object[] toArray() {

? ? return Arrays.copyOf(elementData, size);

}

/**

* 將list轉(zhuǎn)化為你所需要類型的數(shù)組，然后返回

*/

@SuppressWarnings("unchecked")

public <T> T[] toArray(T[] a) {

? ? if (a.length < size)

? ? ? ? // Make a new array of a's runtime type, but my contents:

? ? ? ? return (T[]) Arrays.copyOf(elementData, size, a.getClass());

? ? // 復(fù)制用法，下面專題會講解此內(nèi)容

? ? System.arraycopy(elementData, 0, a, 0, size);

? ? if (a.length > size)

? ? ? ? a[size] = null;

? ? return a;

}

// Positional Access Operations

@SuppressWarnings("unchecked")

E elementData(int index) {

? ? return (E) elementData[index];

}

/**

* 返回此列表中指定位置的元素。

*/

public E get(int index) {

? ? // index 范圍檢查

? ? rangeCheck(index);

? ? return elementData(index);

}

/**

* 用指定的元素替換此列表中指定位置的元素。

*/

public E set(int index, E element) {

? ? // index 范圍檢查

? ? rangeCheck(index);

// 根據(jù) index 找到想替換的舊元素

? ? E oldValue = elementData(index);

? ? // 替換元素

? ? elementData[index] = element;

? ? return oldValue;

}

/**

* 將指定的元素追加到此列表的末尾。

*/

public boolean add(E e) {

? ? // 確認 list 容量，嘗試容量加 1，看看有無必要擴容

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

? ? // 賦值

? ? elementData[size++] = e;

? ? return true;

}

/**

* 在此列表中的指定位置插入指定的元素

* 再將從index開始之后的所有成員后移一個位置；將element插入index位置；最后size加1。

*/

public void add(int index, E element) {

? ? // 調(diào)用 rangeCheckForAdd 對 index 進行范圍檢查

? ? rangeCheckForAdd(index);

// 保證容量足夠

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

? ? // 自己復(fù)制自己，然后達到 index 之后全部元素向后挪一位的效果

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

? ? ? ? ? ? ? ? ? ? size - index);

? ? // 然后將 index 賦值為指定的元素

? ? elementData[index] = element;

? ? size++;

}

/**

* 移除該列表中指定位置的元素。 將任何后續(xù)元素移動到左側(cè)（從其索引中減去一個元素）。

*/

public E remove(int index) {

? ? // 調(diào)用 rangeCheckForAdd 對 index 進行范圍檢查

? ? rangeCheck(index);

? ? modCount++;

? ? // 找到待移除的值

? ? E oldValue = elementData(index);

// 計算出需要移動元素的數(shù)量

? ? int numMoved = size - index - 1;

? ? if (numMoved > 0)

? ? ? ? // 同樣復(fù)制自己，使得被移除元素右側(cè)的元素整體向左移動

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

? ? ? ? ? ? ? ? ? ? ? ? numMoved);

? ? elementData[--size] = null; // clear to let GC do its work

? ? return oldValue;

}

/**

* 從集合中移除第一次出現(xiàn)的指定元素

*/

public boolean remove(Object o) {

? ? if (o == null) {

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

? ? ? ? ? ? if (elementData[index] == null) {

? ? ? ? ? ? ? ? fastRemove(index);

? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? }

? ? } else {

? ? ? ? // 也很簡單，就是一個循環(huán) equals 判斷，然后移除

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

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

? ? ? ? ? ? ? ? fastRemove(index);

? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? }

? ? }

? ? return false;

}

/*

* 跳過范圍檢查的刪除方式，與remove(Object o)相同

*/

private void fastRemove(int index) {

? ? modCount++;

? ? 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

}

/**

* 從列表中刪除所有元素。

*/

public void clear() {

modCount++;

? ? // clear to let GC do its work

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

? ? ? ? // 元素全部設(shè)為 null

? ? ? ? elementData[i] = null;

? ? // 長度設(shè)為 0

? ? size = 0;

}

/**

* 按指定集合的Iterator返回的順序

* 將指定集合中的所有元素追加到此列表的末尾。

*/

public boolean addAll(Collection<? extends E> c) {

? ? // 轉(zhuǎn)為數(shù)組

? ? Object[] a = c.toArray();

? ? // 拿到待添加指定數(shù)組的長度

? ? int numNew = a.length;

? ? // 確認 list 容量，嘗試容量加上 numNew，看看有無必要擴容

? ? ensureCapacityInternal(size + numNew);? // Increments modCount

? ? // 利用 arraycopy 指定數(shù)組a的元素追加到當前數(shù)組 elementData 后

? ? System.arraycopy(a, 0, elementData, size, numNew);

? ? size += numNew;

? ? return numNew != 0;

}

/**

* 按指定集合的Iterator返回的順序

* 將指定集合中的所有元素添加到此列表中，從指定位置開始

*

*/

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)

? ? ? ? // 實現(xiàn)元素指定位置的插入，本質(zhì)還是 arraycopy 自身

? ? ? ? System.arraycopy(elementData, index, elementData, index + numNew,

? ? ? ? ? ? ? ? ? ? ? ? numMoved);

? ? System.arraycopy(a, 0, elementData, index, numNew);

? ? size += numNew;

? ? return numNew != 0;

}

/**

* 刪除指定索引范圍內(nèi)的元素（fromIndex - toIndex）

* 將任何后續(xù)元素移動到左側(cè)（減少其索引）。

*/

protected void removeRange(int fromIndex, int toIndex) {

? ? modCount++;

? ? int numMoved = size - toIndex;

? ? System.arraycopy(elementData, toIndex, elementData, fromIndex,

? ? ? ? ? ? ? ? ? ? numMoved);

? ? // clear to let GC do its work

? ? int newSize = size - (toIndex-fromIndex);

? ? for (int i = newSize; i < size; i++) {

? ? ? ? elementData[i] = null;

? ? }

? ? size = newSize;

}

/**

* 檢查給定的索引是否在范圍內(nèi)。

*/

private void rangeCheck(int index) {

? ? // 下標越界就直接拋異常

? ? if (index >= size)

? ? ? ? throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

* 另一個版本，針對add 和 addAll使用

*/

private void rangeCheckForAdd(int index) {

? ? if (index > size || index < 0)

? ? ? ? throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

* 與上面套娃使用

*/

private String outOfBoundsMsg(int index) {

? ? return "Index: "+index+", Size: "+size;

}

/**

* 從此列表中刪除指定集合中包含的所有元素。

*/

public boolean removeAll(Collection<?> c) {

? ? Objects.requireNonNull(c);

? ? return batchRemove(c, false);

}

/**

* 僅保留此列表中包含在指定集合中的元素。即刪掉沒有的部分

*/

public boolean retainAll(Collection<?> c) {

? ? Objects.requireNonNull(c);

? ? return batchRemove(c, 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++)

? ? ? ? ? ? // 通過循環(huán)判斷數(shù)組中有沒有指定數(shù)組中的每一個值，complement 是參數(shù)傳遞的

? ? ? ? ? ? if (c.contains(elementData[r]) == complement)

? ? ? ? ? ? ? ? // 就將原數(shù)組的r位置的數(shù)據(jù)覆蓋掉w位置的數(shù)據(jù)

? ? ? ? ? ? ? ? // r位置的數(shù)據(jù)不變，并其w自增，r自增

? ? ? ? ? ? ? ? // 否則，r自增，w不自增

? ? ? ? ? ? ? ? // 本質(zhì)：把需要移除的數(shù)據(jù)都替換掉，不需要移除的數(shù)據(jù)前移

? ? ? ? ? ? ? ? elementData[w++] = elementData[r];

? ? } finally {

? ? ? ? // Preserve behavioral compatibility with AbstractCollection,

? ? ? ? // even if c.contains() throws.

? ? ? ? if (r != size) {

? ? ? ? ? ? System.arraycopy(elementData, r,

? ? ? ? ? ? ? ? ? ? ? ? ? ? elementData, w,

? ? ? ? ? ? ? ? ? ? ? ? ? ? size - r);

? ? ? ? ? ? w += size - r;

? ? ? ? }

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

}

// writeObject readObject 序列化相關(guān)的省略

/**

* 列表迭代器：List集合特有的迭代器

*/

public ListIterator<E> listIterator(int index) {

? ? if (index < 0 || index > size)

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

? ? return new ListItr(index);

}

public ListIterator<E> listIterator() {

? ? return new ListItr(0);

}

// foreach 遍歷等同于 iterator

public Iterator<E> iterator() {

? ? return new Itr();

}

private class Itr implements Iterator<E> {

? ? // 下一個要訪問的元素下標

? ? int cursor;

? ? // 上一個要訪問的元素下標

? ? int lastRet = -1;

? ? // 代表對 ArrayList 修改次數(shù)的期望值，初始值為 modCount

? ? int expectedModCount = modCount;

? ? Itr() {}

? ? // 下標如果

? ? public boolean hasNext() {

? ? ? ? return cursor != size;

? ? }

? ? /**

? ? * 剛開始cursor = 0，lastRet = -1

? ? * 整個過程結(jié)束 cursor 和 lastRet 都會自增 1

? ? */

? ? @SuppressWarnings("unchecked")

? ? public E next() {

? ? ? ? // 跳轉(zhuǎn)本質(zhì)是判斷 modCount 是否等于 expectedModCount

? ? ? ? checkForComodification();

? ? ? ? int i = cursor;

? ? ? // 判斷 cursor 是否超過集合大小和數(shù)組長度

? ? ? ? if (i >= size)

? ? ? ? ? ? throw new NoSuchElementException();

? ? ? ? Object[] elementData = ArrayList.this.elementData;

? ? ? ? if (i >= elementData.length)

? ? ? ? ? ? throw new ConcurrentModificationException();

? ? ? ? cursor = i + 1;

? ? ? ? // 將 cursor 賦值給 lastRet，然后把此下標處的元素返回

? ? ? ? return (E) elementData[lastRet = i];

? ? }

? ? public void remove() {

? ? ? ? // 先判斷 lastRet 的值是否小于 0

? ? ? ? if (lastRet < 0)

? ? ? ? ? ? throw new IllegalStateException();

? ? ? ? // 跳轉(zhuǎn)本質(zhì)是判斷 modCount 是否等于 expectedModCount

? ? ? ? checkForComodification();

? ? ? ? try {

? ? ? ? ? ? // 直接調(diào)用 ArrayList 的 remove 方法刪除下標為 lastRet 的元素

? ? ? ? ? ? ArrayList.this.remove(lastRet);

? ? ? ? ? ? cursor = lastRet;

? ? ? ? ? ? lastRet = -1;

? ? ? ? ? ? expectedModCount = modCount;

? ? ? ? } catch (IndexOutOfBoundsException ex) {

? ? ? ? ? ? throw new ConcurrentModificationException();

? ? ? ? }

? ? }

? ? // forEachRemaining 略

? ? final void checkForComodification() {

? ? ? ? if (modCount != expectedModCount)

? ? ? ? ? ? throw new ConcurrentModificationException();

? ? }

}

3. 重點內(nèi)容分析

3.1 擴容機制再分析

回到頂部

3.1.1 ArrayList 是如何被初始化的

ArrayList 提供了 1 個無參構(gòu)造和 2 個帶參構(gòu)造來初始化 ArrayList ，我們在創(chuàng)建 ArrayList 時，經(jīng)常使用無參構(gòu)造的方式，其本質(zhì)就是初始化了一個空數(shù)組，直到向數(shù)組內(nèi)真的添加元素的時候才會真的去分配容量。例如：向數(shù)組中添加第一個元素，數(shù)組容量擴充為 10

補充：JDK7 無參構(gòu)造 初始化 ArrayList 對象時，直接創(chuàng)建了長度是 10 的 Object[] 數(shù)組elementData

回到頂部

3.1.2 擴容機制流程分析（無參構(gòu)造為例）

3.1.2.1 add()

一般來說，都是通過 add 方法觸發(fā)擴容機制，我們拿最簡單的尾部追加的 add() 方法舉例

/**

* 將指定的元素追加到此列表的末尾。

*/

public boolean add(E e) {

? ? // 確認 list 容量，嘗試容量加 1，看看有無必要擴容

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

? ? // 賦值

? ? elementData[size++] = e;

? ? return true;

}

核心要點就這一句 ensureCapacityInternal(size + 1);

3.1.2.2 ensureCapacityInternal()

追蹤進去

/**

* 得到最小擴容量

*/

private void ensureCapacityInternal(int minCapacity) {

? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

方法內(nèi)調(diào)用了 ensureExplicitCapacity() 方法，參數(shù)是 calculateCapacity(elementData, minCapacity)

先來分析一下這個參數(shù)的結(jié)果是什么，聚焦到 calculateCapacity() 方法中去

3.1.2.3 calculateCapacity()

/**

* 計算最小擴容量（被調(diào)用）

*/

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

? ? // 如果元素數(shù)組為默認的空

? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

? ? ? ? // 獲取“默認的容量”和“傳入?yún)?shù) minCapacity ”兩者之間的最大值

? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);

? ? }

? ? return minCapacity;

}

也很簡單，就是為了計算出一個最小擴容量，當元素為初次初始化時，數(shù)組還沒進過擴容，是一個空數(shù)組，所以會走 if 這個判斷，而且當時傳入的 size + 1 也就是 minCapacity 的值為 0 + 1 = 1 ，經(jīng)過一個取大值的操作，與默認的 DEFAULT_CAPACITY 進行比對，自然返回的就是 10。

如果數(shù)組已經(jīng)不是為空了，就直接返回一個 minCapacity （size + 1）就可以了

3.1.2.4 ensureExplicitCapacity

ensureCapacityInternal 方法內(nèi)調(diào)用了 ensureExplicitCapacity(參數(shù)已經(jīng)計算出來了) 方法

繼續(xù)去看它

/**

* 判斷是否需要擴容

*/

private void ensureExplicitCapacity(int minCapacity) {

? ? modCount++;

? ? // overflow-conscious code

? ? // 如果最小容量比數(shù)組的長度還大

? ? if (minCapacity - elementData.length > 0)

? ? ? ? // 就調(diào)用grow方法進行擴容

? ? ? ? grow(minCapacity);

}

此方法的核心就是 if 判斷這個數(shù)組需不需要擴容，可以分為三種情況

add 第 1 個元素時：此時數(shù)組還只是一個被初始化過的空數(shù)組，minCapacity 經(jīng)過 calculateCapacity 計算會返回 DEFAULT_CAPACITY 的默認值 10，而 elementData.length 也自然是 0，所以 minCapacity - elementData.length > 0 是成立的，直接進入 grow(minCapacity); 開始擴容。

add 第 2 到 10 個元素的時候（以 2 舉例）：此時 minCapacity = size + 1 = 1 + 1 = 2 ，而 elementData.length 已經(jīng)在添加第 1 個元素后等于 10 了。所以 minCapacity - elementData.length > 0 就不成立了，所以不會進入 grow(minCapacity); ，也不會擴容

添加第 3 ... 10 個元素的時候，都是一樣的。

add 第 11 個元素的時候，minCapacity 變成了 11，比 10 還要大，所以又一次進去擴容了

3.1.2.5 grow()

這里是真正去執(zhí)行擴容邏輯的代碼

/**

* 要分配的最大數(shù)組大小

*/

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

* ArrayList 擴容的核心方法

*/

private void grow(int minCapacity) {

? ? // 將當前元素數(shù)組長度定義為 oldCapacity 舊容量

? ? int oldCapacity = elementData.length;

? ? // 新容量更新為舊容量的1.5倍

? ? // oldCapacity >> 1 為按位右移一位，相當于 oldCapacity 除以2的1次冪

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

? ? // 然后檢查新容量是否大于最小需要容量，若還小，就把最小需要容量當作數(shù)組的新容量

? ? if (newCapacity - minCapacity < 0)

? ? ? ? newCapacity = minCapacity;

? ? // 再檢查新容量是否超出了ArrayList 所定義的最大容量

? ? if (newCapacity - MAX_ARRAY_SIZE > 0)

? ? ? ? // 若超出，則調(diào)用hugeCapacity()

? ? ? ? newCapacity = hugeCapacity(minCapacity);

? ? elementData = Arrays.copyOf(elementData, newCapacity);

}

擴容的核心就是這句：int

newCapacity = oldCapacity + (oldCapacity >> 1);

本質(zhì)就是擴容 1.5 倍，而且其中使用了移位運算，這里從計算的角度上來看，相當于 oldCapacity 除以 2 的 1 次冪（偶數(shù)除以 2 剛好除盡，奇數(shù)丟掉小數(shù)部分）。使用按位右移，效率會高很多

>> 按位右移運算符：最高位為 0，左邊補齊 0，最高位是 1，左邊補齊 1

快速計算：把 >> 左邊的數(shù)據(jù) 除以 2 的移動次冪：例如 -24 >> 2 即：-24 / 2 ^ 2 = -6

—— 此項目 【001-Java基礎(chǔ)知識】 章節(jié)中有具體介紹

擴容后，需要對這個新容量的范圍進行一個判斷，不能小于最小需要容量，也不能大于定義的最大容量，分情況細細看一下（以 1 和 11 舉例，是因為這兩種都是剛好需要擴容的）

add 第 1 個元素的時候，數(shù)組還為空，所以無論是 oldCapacity 還是 newCapacity 都是 0，經(jīng)過第一次判斷后，newCapacity = minCapacity 執(zhí)行了，此時 newCapacity 為 10，第二個判斷不會進入，它不可能大于數(shù)組的最大容量。

add 第 11 個元素的時候，oldCapacity 為 10，newCapacity = 10 + 10/2 = 15，大于 minCapacity = 11，第一個判斷不會進入，同時它肯定也沒有大于數(shù)組最大 size，不會進入 。數(shù)組容量此時就擴為 15，add 方法中會返回一個 true，size 也增加成 11。

后面都是同樣的道理 ...

3.1.2.6 hugeCapacity()

這個方法就是在 newCapacity 大于 MAX_ARRAY_SIZE 的時候，開始判斷 minCapacity 和 MAX_ARRAY_SIZE 誰大，然后賦予不同的值。

/**

* 比較minCapacity和 MAX_ARRAY_SIZE

*/

private static int hugeCapacity(int minCapacity) {

? ? if (minCapacity < 0) // overflow

? ? ? ? throw new OutOfMemoryError();

? ? return (minCapacity > MAX_ARRAY_SIZE) ?

? ? ? ? Integer.MAX_VALUE :

? ? MAX_ARRAY_SIZE;

}

3.2 System.arraycopy() 和 Arrays.copyOf() 復(fù)制方法

在前面的方法中，大量的用到了這兩個方法，基本但凡涉及到元素移動的都會用到。

回到頂部

3.2.1 System.arraycopy()

拿 add 方法中的舉例

/**

* 在此列表中的指定位置插入指定的元素

* 再將從index開始之后的所有成員后移一個位置；將element插入index位置；最后size加1。

*/

public void add(int index, E element) {

? ? // 調(diào)用 rangeCheckForAdd 對 index 進行范圍檢查

? ? rangeCheckForAdd(index);

// 保證容量足夠

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

? ? // 自己復(fù)制自己，然后達到 index 之后全部元素向后挪一位的效果

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

? ? ? ? ? ? ? ? ? ? size - index);

? ? // 然后將 index 賦值為指定的元素

? ? elementData[index] = element;

? ? size++;

}

arraycopy 是 System類 中的一個方法

/**

* 數(shù)組復(fù)制

* src - 源數(shù)組。

* srcPos - 源數(shù)組中的起始位置。

* dest - 目標數(shù)組。

* destPos - 目的地數(shù)據(jù)中的起始位置。

* length - 要復(fù)制的數(shù)組元素的數(shù)量。

*/

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

舉例：

public static void main(String[] args) {

? ? int[] arr = new int[10];

? ? arr[0] = 11;

? ? arr[1] = 22;

? ? arr[2] = 33;

? ? arr[3] = 44;

? ? arr[4] = 55;

? ? System.out.println("前：" + Arrays.toString(arr));

? ? // 指定下標后向后挪動一位

? ? System.arraycopy(arr, 1, arr, 2, 4);

? ? // 指定下標處替換元素

? ? arr[1] = 666;

? ? System.out.println("后：" + Arrays.toString(arr));

}

運行結(jié)果：

前：[11, 22, 33, 44, 55, 0, 0, 0, 0, 0]

后：[11, 666, 22, 33, 44, 55, 0, 0, 0, 0]

這樣就實現(xiàn)了 add 中的一個指定下標插入操作（不考慮擴容）

回到頂部

3.2.2 Arrays.copyOf()

所以，可以簡單的認為，這個方法的目的只要是為了給原數(shù)組擴容。

public static void main(String[] args) {

? ? int[] arr1 = {1, 2, 3, 4, 5};

? ? int[] arr2 = Arrays.copyOf(arr1, 5);

? ? int[] arr3 = Arrays.copyOf(arr1, 10);

? ? System.out.println(Arrays.toString(arr1));

? ? System.out.println(Arrays.toString(arr2));

? ? System.out.println(Arrays.toString(arr3));

}

運行結(jié)果：

[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]

3.3 removeAll() 和 retainAll() 中的 batchRemove() 方法

在 removeAll() 和 retainAll() 方法中，都調(diào)用了 batchRemove()方法，區(qū)別只是傳參不同，就能實現(xiàn)兩種不同的正反刪除效果

/**

* 從此列表中刪除指定集合中包含的所有元素。

*/

public boolean removeAll(Collection<?> c) {

? ? Objects.requireNonNull(c);

? ? return batchRemove(c, false);

}

/**

* 僅保留此列表中包含在指定集合中的元素。即刪掉沒有的部分

*/

public boolean retainAll(Collection<?> c) {

? ? Objects.requireNonNull(c);

? ? return batchRemove(c, 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 {

? ? ? ? if (r != size) {

? ? ? ? ? ? System.arraycopy(elementData, r,

? ? ? ? ? ? ? ? ? ? ? ? ? ? elementData, w,

? ? ? ? ? ? ? ? ? ? ? ? ? ? size - r);

? ? ? ? ? ? w += size - r;

? ? ? ? }

? ? ? ? if (w != size) {

? ? ? ? ? ? for (int i = w; i < size; i++)

? ? ? ? ? ? ? ? elementData[i] = null;

? ? ? ? ? ? modCount += size - w;

? ? ? ? ? ? size = w;

? ? ? ? ? ? modified = true;

? ? ? ? }

? ? }

? ? return modified;

}

解釋一下剛開始的那些字段

size ：原數(shù)組長度

elementData： 原數(shù)組

modCount ： 從父類繼承過來的變量，作用是記錄著集合的修改次數(shù)。

來看第一個關(guān)鍵代碼

for (; r < size; r++)

if (c.contains(elementData[r]) == complement)

elementData[w++] = elementData[r];

我們以 removeAll() 為例，意圖從此列表中刪除指定集合中包含的所有元素。即，有的就刪，沒有的就不刪。

所以 complement 經(jīng)過參數(shù)傳遞過來自然是 false，所以參數(shù)指定數(shù)組中不含有原數(shù)組指定位置下標的數(shù)據(jù)的時候，就將 elementData[r] 位置的數(shù)據(jù)覆蓋掉 elementData[w++] 位置的數(shù)據(jù)，r 根據(jù)循環(huán)++自增，w 根據(jù)變量 w++ 自增，若 if 表達式不成立則，r 自增，w 不自增。

舉例：原數(shù)組：[1, 2, 3, 4, 5, 6, 7, 8, 9] ，指定參數(shù)數(shù)組： [a, b, c, 3, 5, 8, f]（例子參考自）重新排版

循環(huán)次數(shù) r w 布爾值 賦值語句 替換后的數(shù)組值 說明

1 0 0 true elementData[0]=elementData[0] [1, 2, 3, 4, 5, 6, 7, 8, 9] 1 替換 1，r++ ，w++

2 1 1 true elementData[1]=elementData[1] [1, 2, 3, 4, 5, 6, 7, 8, 9] 2 替換 2，r++ ，w++

3 2 2 false [1, 2, 3, 4, 5, 6, 7, 8, 9]

4 3 2 true elementData[2]=elementData[3] [1, 2, 4, 4, 5, 6, 7, 8, 9] 4 替換 3，r++ ，w++

5 4 3 false [1, 2, 4, 4, 5, 6, 7, 8, 9]

6 5 3 true elementData[3]=elementData[5] [1, 2, 4, 6, 5, 6, 7, 8, 9] 6 替換 4，r++ ，w++

7 6 4 true elementData[4]=elementData[6] [1, 2, 4, 6, 7, 6, 7, 8, 9] 7 替換 5，r++ ，w++

8 7 5 false [1, 2, 4, 6, 7, 6, 7, 8, 9]

9 8 5 true elementData[5]=elementData[8] [1, 2, 4, 6, 7, 9, 7, 8, 9] 9 替換 6，r++ ，w++

9 6

自己走一遍上面的邏輯，就能深刻的感受得到

這步的作用：把需要移除的數(shù)據(jù)都替換掉，不需要移除的數(shù)據(jù)前移。（這步的處理尤為重要?。?/p>

接下來進入 finally 中，這一段是最終肯定會執(zhí)行的

if (r != size) {

? ? System.arraycopy(elementData, r,elementData, w,size - r);

? ? w += size - r;

}

if (w != size) {

? ? for (int i = w; i < size; i++)

? ? ? ? elementData[i] = null;

? ? modCount += size - w;

? ? size = w;

? ? modified = true;

}

首先判斷 r 是否等于 size，如果上面的循環(huán)正常執(zhí)行結(jié)束，r 和 size 應(yīng)該是相同的，所以肯定不會走上面，第一個 if 判斷的目的就是為了解決某種異常情況下（異常，并發(fā)修改）導(dǎo)致的 for 循環(huán)未結(jié)束，此時 r != size 所以通過 arraycopy 將添加的元素追加到w索引后面。

而第二個 if ，主要是為了把 w 之后沒處理過的給刪掉，這樣就可以達到目的了。

例如上面表格的例子，最后 w = 6，也就是 [1, 2, 4, 6, 7, 9, 7, 8, 9] 中從下標為 6 的元素 7 開始刪除，將 7，8，9 賦值為 null 后面會被 GC 清理掉。最后得到的結(jié)果 [1, 2, 4, 6, 7, 9] 就是清除過的了 。

3.4 并發(fā)修改異常問題探索

public static void main(String[] args) {

? ? // 創(chuàng)建集合對象

? ? List list = new ArrayList();

? ? // 存儲元素

? ? list.add("I");

? ? list.add("love");

? ? list.add("you");

? ? Iterator it = list.iterator();

? ? while (it.hasNext()) {

? ? ? ? String s = (String) it.next();

? ? ? ? if ("love".equals(s)) {

? ? ? ? ? ? list.add("?");

? ? ? ? }

? ? ? ? System.out.println(s);

? ? }

}

//運行結(jié)果(節(jié)選)

Exception in thread "main" java.util.ConcurrentModificationException

使用增強for或者迭代器遍歷集合的時候，如果對集合進行 list的 remove 和 add 操作，會出現(xiàn) ConcurrentModificationException 并發(fā)修改異常的問題。

回到頂部

3.4.1 原因解釋：

當我們對集合進行遍歷的時候，我們會獲取當前集合的迭代對象

//List為例，獲取集合的迭代對象

Iterator it = list.iterator();

這個迭代對象中，封裝了迭代器的方法與集合本身的一些方法，當我們在迭代中使用集合本身的add / remove方法的時候，就產(chǎn)生了ConcurrentModificationException異常，通俗的說就是，在判斷 equals 成功后，執(zhí)行了 list 的 add / remove 方法， 操作集合中元素或者刪除增加了，但是迭代器不清楚，所以就報錯，如果迭代器中含有這一種方法（假設(shè)），我們是用迭代器添加元素就不會有問題了。

詳細解釋：

開始時，cursor 指向下標為 0 的元素，lastRet 指向下標為 -1 的元素，每次調(diào)用 next 方法，cursor 和 lastRet 會分別自增 1。

當突然 ArrayList 的 remove 方法被調(diào)用（不是 Itr 的 remove），會導(dǎo)致被刪除元素后面的所有元素都會往前移動一位，且 modCount 這個修改次數(shù)會增加，繼續(xù)循環(huán)，去執(zhí)行 next 方法，而 next 方法中首先判斷的就是 modCount 和 expectedModCount 是否相等，很明顯由于 ArrayList 的操作，導(dǎo)致 modCount 變化，兩者現(xiàn)在已經(jīng)不等了，所以出現(xiàn)異常

final void checkForComodification() {

? ? if (modCount != expectedModCount)

? ? ? ? throw new ConcurrentModificationException();

}

針對這個問題，我們給出兩個解決方案

回到頂部

3.4.2 解決方案：

3.4.2.1 方式1：迭代器迭代元素，迭代器修改元素

我們假想如果Iterator迭代器中有添加或者刪除等功能就好了，但很遺憾并沒有，但是它的子接口 ListIterator 卻擁有 add 這個功能（ListIterator 擁有 add、set、remove 方法，Iterator 擁有 remove 方法，這里只演示 add 方法，remove 方法就用原來的 Iterator .remove() ）

ListIterator 的 add()和 Iterator 的 remove() 可以使用的原因都是因為，方法進行了添加刪除操作后，都會執(zhí)行 expectedModCount = modCount 這樣的賦值操作，相當于告訴迭代器我進行了修改操作。

public static void main(String[] args) {

? ? // 創(chuàng)建集合對象

? ? List list = new ArrayList();

? ? // 存儲元素

? ? list.add("I");

? ? list.add("love");

? ? list.add("you");

? ? ListIterator lit = list.listIterator();

? ? while (lit.hasNext()) {

? ? ? ? String s = (String) lit.next();

? ? ? ? if ("love".equals(s)) {

? ? ? ? ? ? // add 、remove 都是可以的

? ? ? ? ? ? lit.add("?");

? ? ? ? }

? ? ? ? System.out.print(s + " ");

? ? }

? ? System.out.println();

? ? for (Object l : list){

? ? System.out.print(l + " ");

? ? }

}

//運行結(jié)果

I love you

I love ? you

3.4.2.1 方式2：集合遍歷元素，集合修改元素（普通for）

import java.util.ArrayList;

import java.util.List;

import java.util.ListIterator;

public class Demo2 {

? ? public static void main(String[] args) {

? ? ? ? //創(chuàng)建集合對象

? ? ? ? List list = new ArrayList();

? ? ? ? //存儲元素

? ? ? ? list.add("I");

? ? ? ? list.add("love");

? ? ? ? list.add("you");

? ? ? ? for (int x = 0; x < list.size(); x++){

? ? ? ? ? ? String s = (String)list.get(x);

? ? ? ? ? ? if ("love".equals(s)){

? ? ? ? ? ? ? ? list.add("?");

? ? ? ? ? ? }

? ? ? ? ? ? System.out.print(s + " ");

? ? ? ? }

? ? }

}

//運行結(jié)果

I love you ?

USB Microphone https://www.soft-voice.com/

Wooden Speakers? https://www.zeshuiplatform.com/

亞馬遜測評 www.yisuping.cn

深圳網(wǎng)站建設(shè)www.sz886.com