核心源碼分析

2.1 類聲明

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

public class ArrayList<E> extends AbstractList<E>

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

{

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

}

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

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

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

2.2 類成員

下面接著看一些成員屬性

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

private static final long serialVersionUID = 8683452581122892189L;

/**

* 默認(rèn)初始容量大小為10

*/

private static final int DEFAULT_CAPACITY = 10;

/**

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

*/

private static final Object[] EMPTY_ELEMENTDATA = {};

/**

* 與 EMPTY_ELEMENTDATA 的區(qū)別是怒医，它是默認(rèn)返回的炉抒，而前者是用戶指定容量為 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ù)（大兄商尽）

*/

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

? ? }

}

/**

* 默認(rèn)無參構(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 擴容方法

這里只是按照順序介紹刹孔，后面還會專門針對擴容進(jìn)行一個分析

/**

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

*/

public void ensureCapacity(int minCapacity) {

? ? //如果元素數(shù)組不為默認(rèn)的空卦睹，則 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ù)組為默認(rèn)的空

? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

? ? ? ? // 獲取“默認(rèn)的容量”和“傳入?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方法進(jìn)行擴容

? ? ? ? grow(minCapacity);

}

/**

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

*/

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

/**

* ArrayList 擴容的核心方法

*/

private void grow(int minCapacity) {

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

? ? int oldCapacity = elementData.length;

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

? ? // oldCapacity >> 1 為按位右移一位方库，相當(dāng)于 oldCapacity 除以2的1次冪

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

? ? // 然后檢查新容量是否大于最小需要容量结序，若還小，就把最小需要容量當(dāng)作數(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) {

? ? // 確認(rèn) 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 進(jìn)行范圍檢查

? ? rangeCheckForAdd(index);

// 保證容量足夠

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

? ? // 自己復(fù)制自己，然后達(dá)到 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 進(jìn)行范圍檢查

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

? ? // 確認(rèn) list 容量，嘗試容量加上 numNew震束，看看有無必要擴容

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

? ? // 利用 arraycopy 指定數(shù)組a的元素追加到當(dāng)前數(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) {

? ? // 下標(biāo)越界就直接拋異常

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

? ? // 下一個要訪問的元素下標(biāo)

? ? int cursor;

? ? // 上一個要訪問的元素下標(biāo)

? ? int lastRet = -1;

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

? ? int expectedModCount = modCount;

? ? Itr() {}

? ? // 下標(biāo)如果

? ? 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，然后把此下標(biāo)處的元素返回

? ? ? ? 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 方法刪除下標(biāo)為 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) {

? ? // 確認(rèn) list 容量秦驯，嘗試容量加 1，看看有無必要擴容

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

? ? // 賦值

? ? elementData[size++] = e;

? ? return true;

}

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

3.1.2.2 ensureCapacityInternal()

追蹤進(jìn)去

/**

* 得到最小擴容量

*/

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ù)組為默認(rèn)的空

? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

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

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

? ? }

? ? return minCapacity;

}

也很簡單，就是為了計算出一個最小擴容量洛心，當(dāng)元素為初次初始化時固耘，數(shù)組還沒進(jìn)過擴容，是一個空數(shù)組词身，所以會走 if 這個判斷厅目，而且當(dāng)時傳入的 size + 1 也就是 minCapacity 的值為 0 + 1 = 1 ，經(jīng)過一個取大值的操作偿枕，與默認(rèn)的 DEFAULT_CAPACITY 進(jìn)行比對璧瞬，自然返回的就是 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方法進(jìn)行擴容

? ? ? ? grow(minCapacity);

}

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

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

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

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

add 第 11 個元素的時候涡相，minCapacity 變成了 11哲泊，比 10 還要大，所以又一次進(jìn)去擴容了

3.1.2.5 grow()

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

/**

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

*/

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

/**

* ArrayList 擴容的核心方法

*/

private void grow(int minCapacity) {

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

? ? int oldCapacity = elementData.length;

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

? ? // oldCapacity >> 1 為按位右移一位催蝗，相當(dāng)于 oldCapacity 除以2的1次冪

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

? ? // 然后檢查新容量是否大于最小需要容量切威，若還小，就把最小需要容量當(dāng)作數(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 倍先朦，而且其中使用了移位運算，這里從計算的角度上來看犬缨，相當(dāng)于 oldCapacity 除以 2 的 1 次冪（偶數(shù)除以 2 剛好除盡喳魏，奇數(shù)丟掉小數(shù)部分）。使用按位右移怀薛，效率會高很多

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

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

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

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

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

add 第 11 個元素的時候，oldCapacity 為 10象踊，newCapacity = 10 + 10/2 = 15温亲，大于 minCapacity = 11，第一個判斷不會進(jìn)入杯矩，同時它肯定也沒有大于數(shù)組最大 size栈虚，不會進(jìn)入 。數(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 進(jìn)行范圍檢查

? ? rangeCheckForAdd(index);

// 保證容量足夠

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

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

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

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

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

? ? elementData[index] = element;

? ? size++;

}

arraycopy 是 System類 中的一個方法

/**

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

* src - 源數(shù)組咙轩。

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

* dest - 目標(biāo)數(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));

? ? // 指定下標(biāo)后向后挪動一位

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

? ? // 指定下標(biāo)處替換元素

? ? 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 中的一個指定下標(biāo)插入操作（不考慮擴容）

回到頂部

3.2.2 Arrays.copyOf()

所以量愧，可以簡單的認(rèn)為钾菊，這個方法的目的只要是為了給原數(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ù)組指定位置下標(biāo)的數(shù)據(jù)的時候，就將 elementData[r] 位置的數(shù)據(jù)覆蓋掉 elementData[w++] 位置的數(shù)據(jù)沛慢，r 根據(jù)循環(huán)++自增赡若，w 根據(jù)變量 w++ 自增祟敛，若 if 表達(dá)式不成立則腿宰，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ù)前移默伍。（這步的處理尤為重要！）

接下來進(jìn)入 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 之后沒處理過的給刪掉斗搞，這樣就可以達(dá)到目的了指攒。

例如上面表格的例子，最后 w = 6僻焚，也就是 [1, 2, 4, 6, 7, 9, 7, 8, 9] 中從下標(biāo)為 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或者迭代器遍歷集合的時候狞山，如果對集合進(jìn)行 list的 remove 和 add 操作全闷，會出現(xiàn) ConcurrentModificationException 并發(fā)修改異常的問題。

回到頂部

3.4.1 原因解釋：

當(dāng)我們對集合進(jìn)行遍歷的時候萍启，我們會獲取當(dāng)前集合的迭代對象

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

Iterator it = list.iterator();

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

詳細(xì)解釋：

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

當(dāng)突然 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() 可以使用的原因都是因為询枚，方法進(jìn)行了添加刪除操作后，都會執(zhí)行 expectedModCount = modCount 這樣的賦值操作浙巫，相當(dāng)于告訴迭代器我進(jìn)行了修改操作哩盲。

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