深入ArrayList源碼分析（JDK1.8）
Java 集合系列源碼分析文章：
ArrayList源碼分析（基于JDK8）
數(shù)據(jù)結(jié)構(gòu)中有兩種存儲結(jié)構(gòu)，分別是：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。在 Java 中，對于這四種結(jié)構(gòu)分別進(jìn)行實現(xiàn)的類有：
- 順序存儲結(jié)構(gòu)：ArrayList、Stack
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)：LinkedList、Queue
這里只對 ArrayList 的源碼進(jìn)行分析，ArrayList 是一個數(shù)組隊列，相當(dāng)于 動態(tài)數(shù)組 。與Java 中的數(shù)組相比，它的容量能動態(tài)增長。
特點
- 基本的
ArrayList常用于隨機訪問元素，但是在 List 中間插入和移除元素較慢； -
ArrayList中的操作不是線程安全的。所以建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList，建議使用CopyOnWriteArrayList。
繼承關(guān)系
上面可以看到，ArrayList 實現(xiàn)來四個接口一個抽象類。它繼承類 AbstracList 抽象類，實現(xiàn)了 List 、 RandomAccess （隨機訪問）、 Cloneable （可克?。?、 Serializable （序列化）四個接口
-
ArrayList繼承于AbstractList，實現(xiàn)了List。它是一個數(shù)組隊列，提供了相關(guān)的添加、刪除、修改、遍歷等功能； -
ArrayList實現(xiàn)了RandmoAccess接口，即提供了隨機訪問功能； -
ArrayList實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能被克?。?/li> -
ArrayList實現(xiàn)了java.io.Serializable接口，這意味著ArrayList支持序列化，能通過序列化去傳輸。
成員變量
在 ArrayList 的源碼中，主要成員變量如下：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
...
// 默認(rèn)數(shù)組的長度
private static final int DEFAULT_CAPACITY = 10;
// 默認(rèn)的空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默認(rèn)的空數(shù)組，與上面的區(qū)別，在不同的構(gòu)造函數(shù)中用到
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正用于存放數(shù)據(jù)的數(shù)組
transient Object[] elementData;
// 數(shù)組元素個數(shù)
private int size;
// 要分配的數(shù)組的最大大小，嘗試分配更大的陣列可能會導(dǎo)致 OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
}
ArrayList 的底層實現(xiàn)是數(shù)組，默認(rèn)的數(shù)組大小是 10。
構(gòu)造函數(shù)
- ArrayList()：構(gòu)造一個初始容量為10的空列表
- ArrayList(Collection<?extend E> c)：構(gòu)造一個包含指定元素的列表
- ArrayList( int initialCapcity )：構(gòu)造一個具有初始容量值得空列表
// 第一種，調(diào)用ArrayList(10) 默認(rèn)初始化一個大小為10的Object數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 第二種
public ArrayList(int initialCapacity) {
// 如果用戶初始化大小大于0，則新建一個用戶初始化值大小的Objec數(shù)組
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 等于0，則賦值為變量EMPTY_ELEMENTDATA，默認(rèn)的空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 小于0，則拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 第三種：將容器數(shù)組化處理并將這個數(shù)組值賦給Object數(shù)組
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 當(dāng)c.toArray 返回的不是 Object 類型的數(shù)組時，進(jìn)行下面的轉(zhuǎn)化
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
增刪改查操作
對于增刪改查的基本操作，在這里只給出一些比較重要的源代碼進(jìn)行解析。
增加操作
- add(E e)：添加一個元素到列表的末尾。
- add( int index, E element ) :在指定的位置添加元素
- addAll( Collection<? extends E> c )：添加一個集合到元素的末尾.以上返回類型是boolean
- ensureCapcity（int minCapcity）：確保列表中含有minCapcity的最小容量
ArrayList默認(rèn)的插入是插在數(shù)組的末尾，在不需要擴容時是一個時間復(fù)雜度O(1)的操作，需要擴容時復(fù)雜度為O(n)，所以如果預(yù)先能判斷數(shù)據(jù)量的大小，可以指定初始化數(shù)組的大小，避免過多的擴容操作。下面代碼看一些第一個增加元素的方法實現(xiàn)：
// 第一步：
public boolean add(E e) {
// 加入元素前檢查數(shù)組的容量是否足夠
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 第二步：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果添加元素后大于當(dāng)前數(shù)組的長度，則進(jìn)行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 第三步：擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 將數(shù)組的長度增加原來數(shù)組的一半，也就是1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴充一半后仍然不夠，則 newCapacity = minCapacity；minCapacity實際元素的個數(shù)
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果擴充后的容量超過最大值變量MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 將elementData持有的元素復(fù)制到新的數(shù)組對象，最后將elementData的引用指向新的數(shù)組對象
// 原有的數(shù)組對象因為沒有了引用，一段時間后將被回收。
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
ArrayList還支持在指定索引處插入。在指定索引處插入時，需要將指定索引及其之后的元素向后推一個位置，所以是一個復(fù)雜度O(n)的操作。源碼如下：
// 第一步：
public void add(int index, E element) {
// 檢查index的值是否在0到size之間，可以為size.
rangeCheckForAdd(index);
// 看 elementData 的長度是否足夠，不夠擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將 elementData 從 index 開始后面的元素往后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 第二步：
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 第三步：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
刪除操作
- remove(Object o)：刪除列表中第一個出現(xiàn)O的元素
- remove( int index)：刪除列表中指定位置的元素
- removeAll（Collection<?> c）：刪除列表中包含C的所有元素
- removeIf（Predictcate<? super E> filter）：刪除列表中給定謂詞的所有元素
- removeRange( int from,int to )：刪除從from到to的所有元素
- clear（）：清除所有的元素。返回類型為void
ArrayList 刪除元素時，需要將所刪元素之后位置的元素都向前推一個位置，復(fù)雜度也是O(n)。所以ArrayList不適合需要頻繁在指定位置插入元素及刪除的應(yīng)用場景，看代碼實現(xiàn)：
public E remove(int index) {
// 第一步：如果index >= size，則拋出異常
rangeCheck(index);
modCount++;
// 第二步：獲取刪除元素的值
E oldValue = elementData(index);
// 第三步：將 index 后面所有的元素往前移一位
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
// 第四步：返回要刪除的值
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);
eturn true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
更改操作
- retainAll( Collection<?> c )：僅僅保留列表中和C相同的元素，相當(dāng)于&運算
- set（int index,E element）：用element替換index位置上的元素。
- size()：返回此列表的元素數(shù)
- sort(Comparator<? super E> c)：按照指定的排序規(guī)則排序
- subList( int from , int to )：返回從from到to之間的列表
- toArray()：將列表轉(zhuǎn)化為數(shù)組
- trimToSize( )：修改當(dāng)前實例的容量是列表的當(dāng)前大小。
set方法
確保set的位置小于當(dāng)前數(shù)組的長度（size）并且大于0，獲取指定位置（index）元素，然后放到oldValue存放，將需要設(shè)置的元素放到指定的位置（index）上，然后將原來位置上的元素oldValue返回給用戶。
// 第一步：
public E set(int index, E element) {
// 檢查index是否大于size，如果是則拋出異常
rangeCheck(index);
E oldValue = elementData(index);
// 覆蓋ArrayList中index上的元素
elementData[index] = element;
// 返回被覆蓋的元素
return oldValue;
}
// 第二步；
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
subList方法
我們看到代碼中是創(chuàng)建了一個ArrayList 類里面的一個內(nèi)部類SubList對象，傳入的值中第一個參數(shù)時this參數(shù)，其實可以理解為返回當(dāng)前l(fā)ist的部分視圖，真實指向的存放數(shù)據(jù)內(nèi)容的地方還是同一個地方，如果修改了sublist返回的內(nèi)容的話，那么原來的list也會變動。
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
謹(jǐn)慎使用 ArrayList 中的 subList 方法
- ArrayList 的 subList 結(jié)果不可強轉(zhuǎn)成 ArrayList，否則會拋出 ClassCastException 異常，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 說明：subList 返回的是 ArrayList 的內(nèi)部類 SubList，并不是 ArrayList ，而是 ArrayList 的一個視圖，對于 SubList 子列表的所有操作最終會反映到原列表上。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
ArrayList<String> strings = (ArrayList)list.subList(0, 1);
運行結(jié)果：Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList at com.nuih.List.ArrayListTest.main(ArrayListTest.java:29)
- 在 subList 場景中，高度注意對原集合元素個數(shù)的修改，會導(dǎo)致子列表的遍歷、增加、 刪除均會產(chǎn) ConcurrentModificationException 異常。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 對原 List 增加一個值
list.add("10");
subList.add("11"); // 這一行會報 java.util.ConcurrentModificationException
trimToSize方法
public void trimToSize() {
// 修改次數(shù)加1
modCount++;
// 如果當(dāng)前元素小于數(shù)組容量，則將elementData中空余的空間（包括null值）去除
// 例如：數(shù)組長度為10，其中只有前三個元素有值，其他為空，那么調(diào)用該方法后，數(shù)組的長度變?yōu)?
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
toArray方法
第一個，Object[] toArray()方法。該方法有可能會拋出java.lang.ClassCastException異常，如果直接用向下轉(zhuǎn)型的方法，將整個ArrayList集合轉(zhuǎn)變?yōu)橹付愋偷腁rray數(shù)組，便會拋出該異常，而如果轉(zhuǎn)化為Array數(shù)組時不向下轉(zhuǎn)型，而是將每個元素向下轉(zhuǎn)型，則不會拋出該異常，顯然對數(shù)組中的元素一個個進(jìn)行向下轉(zhuǎn)型，效率不高，且不太方便。
第二個， T[] toArray(T[] a)方法。該方法可以直接將ArrayList轉(zhuǎn)換得到的Array進(jìn)行整體向下轉(zhuǎn)型（轉(zhuǎn)型其實是在該方法的源碼中實現(xiàn)的），且從該方法的源碼中可以看出，參數(shù)a的大小不足時，內(nèi)部會調(diào)用Arrays.copyOf方法，該方法內(nèi)部創(chuàng)建一個新的數(shù)組返回，因此對該方法的常用形式如下：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
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());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// 第一種方式（最常用）
Integer[] integer = arrayList.toArray(new Integer[0]);
// 第二種方式（容易理解）
Integer[] integer1 = new Integer[arrayList.size()];
arrayList.toArray(integer1);
// 拋出異常，java不支持向下轉(zhuǎn)型
// Integer[] integer2 = new Integer[arrayList.size()];
// integer2 = arrayList.toArray();
查操作
- contains（Object o）：如果包含元素o,則返回為true
- get（int index）:返回指定索引的元素
- indexOf( Object o )：返回此列表中指定元素的第一次出現(xiàn)的索引，如果列表不包含此元素，返回-1
- lastindexOf( Object o ):返回此列表中指定元素的最后一次出現(xiàn)的索引，如果列表不包含此元素，返回-1
- isEmpty（）：如果列表為空，返回true
- iterator()：返回列表中元素的迭代器
- listIterator（）：返回列表的列表迭代器（按適當(dāng)?shù)捻樞颍?/li>
- listIterator(int index)：從適當(dāng)?shù)奈恢梅祷亓斜淼牧斜淼鳎ò凑照_的順序）
get 方法
返回指定位置上的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
contains方法
調(diào)用indexOf方法，遍歷數(shù)組中的每一個元素作對比，如果找到對于的元素，則返回true，沒有找到則返回false。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
iterator方法
interator方法返回的是一個內(nèi)部類，由于內(nèi)部類的創(chuàng)建默認(rèn)含有外部的this指針，所以這個內(nèi)部類可以調(diào)用到外部類的屬性。
public Iterator<E> iterator() {
return new Itr();
}
一般的話，調(diào)用完iterator之后，我們會使用iterator做遍歷，這里使用next做遍歷的時候有個需要注意的地方，就是調(diào)用next的時候，可能會引發(fā)ConcurrentModificationException，當(dāng)修改次數(shù)，與期望的修改次數(shù)（調(diào)用iterator方法時候的修改次數(shù)）不一致的時候，會發(fā)生該異常，詳細(xì)我們看一下代碼實現(xiàn)：
@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 + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
expectedModCount這個值是在用戶調(diào)用ArrayList的iterator方法時候確定的，但是在這之后用戶add，或者remove了ArrayList的元素，那么modCount就會改變，那么這個值就會不相等，將會引發(fā)ConcurrentModificationException異常，這個是在多線程使用情況下，比較常見的一個異常。
遍歷
ArrayList 遍歷的四種方式
- 第1種，普通for循環(huán)隨機訪問，通過索引值去遍歷。
// 隨機訪問
List<String> list = new ArrayList<>();
int size = list.size();
for (int i = 0; i < size; i++) {
value = list.get(i);
}
- 第2種，通過迭代器遍歷。即通過Iterator去遍歷。
// 迭代器遍歷
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
value = iter.next();
}
- 第3種，for-each。
// 增強for循環(huán)
for (String s : list) {
value = s;
}
- 第4種 forEach + lambda 循環(huán)遍歷
list.forEach(p -> {
p.hashCode();
});
性能對比
既然有 4 種遍歷，那我們看看哪種遍歷效率下面我們通過一個實驗來看下這四種循環(huán)的耗時吧：測試代碼
package com.nuih.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.UUID;
public class ArrayListTest {
public static void main(String[] args) {
// 數(shù)據(jù)預(yù)熱
List<String> testList = createTestList(10);
testForEach(testList);
testFor(testList);
testRandFor(10, testList);
List<Integer> integers = Arrays.asList(10, 50, 100, 500, 1000, 10000, 50000, 100000, 5000000, 10000000, 30000000);
for (Integer i : integers) {
testRand(i);
}
}
private static void testRand(int size) {
System.out.println("-----------次數(shù):" + size + "------------");
List<String> list = createTestList(size);
// 隨機訪問通過索引值去遍歷。
long time1 = System.nanoTime();
testRandFor(size, list);
long time2 = System.nanoTime();
// 增強 for 循環(huán)
testFor(list);
long time3 = System.nanoTime();
// 迭代器遍歷
testIterator(list);
long time4 = System.nanoTime();
// forEach + lambda
testForEach(list);
long time5 = System.nanoTime();
System.out.println("隨機訪問\t\t" + (time2 - time1) / 1000 + " ms");
System.out.println("增強 for 遍歷\t\t" + (time3 - time2) / 1000 + " ms");
System.out.println("迭代器遍歷\t\t" + (time4 - time3) / 1000 + " ms");
System.out.println("forEach 遍歷\t\t" + (time5 - time4) / 1000 + " ms");
System.out.println();
}
private static void testRandFor(int size, List<String> list) {
for (int i = 0; i < size; i++) {
list.get(i).hashCode();
}
}
private static void testFor(List<String> list) {
for (String s : list) {
s.hashCode();
}
}
private static void testIterator(List<String> list) {
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
iter.next().hashCode();
}
}
private static void testForEach(List<String> list) {
list.forEach(p -> {
p.hashCode();
});
}
public static List<String> createTestList(int size) {
List<String> list = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
list.add(UUID.randomUUID().toString());
}
return list;
}
}
測試結(jié)果：
結(jié)論：如果數(shù)據(jù)量比較少的話貌似四種循環(huán)耗時都差不多，但是隨著數(shù)據(jù)量的增長會發(fā)現(xiàn) foreach 的效率是最好的。但是從上面我們會發(fā)現(xiàn)一個奇怪的現(xiàn)象，第一次循環(huán)的時候forEach 遍歷的時間是最長的盡管數(shù)據(jù)量非常少也會這樣。但是后面的耗時就正常了。如果放開測試?yán)锩娴念A(yù)熱代碼，每次跑出來的耗時也是正常的。
-----------次數(shù):10------------
隨機訪問 15 ms
增強 for 遍歷 8 ms
迭代器遍歷 6 ms
forEach 遍歷 65728 ms
-----------次數(shù):50------------
隨機訪問 16 ms
增強 for 遍歷 21 ms
迭代器遍歷 13 ms
forEach 遍歷 10 ms
-----------次數(shù):100------------
隨機訪問 7 ms
增強 for 遍歷 23 ms
迭代器遍歷 34 ms
forEach 遍歷 19 ms
-----------次數(shù):500------------
隨機訪問 64 ms
增強 for 遍歷 47 ms
迭代器遍歷 39 ms
forEach 遍歷 105 ms
-----------次數(shù):1000------------
隨機訪問 129 ms
增強 for 遍歷 99 ms
迭代器遍歷 81 ms
forEach 遍歷 58 ms
-----------次數(shù):10000------------
隨機訪問 1748 ms
增強 for 遍歷 1921 ms
迭代器遍歷 1270 ms
forEach 遍歷 2212 ms
-----------次數(shù):50000------------
隨機訪問 4013 ms
增強 for 遍歷 2739 ms
迭代器遍歷 3628 ms
forEach 遍歷 2368 ms
-----------次數(shù):100000------------
隨機訪問 9874 ms
增強 for 遍歷 4500 ms
迭代器遍歷 5159 ms
forEach 遍歷 6232 ms
-----------次數(shù):5000000------------
隨機訪問 215933 ms
增強 for 遍歷 27000 ms
迭代器遍歷 26586 ms
forEach 遍歷 22105 ms
-----------次數(shù):10000000------------
隨機訪問 379588 ms
增強 for 遍歷 57104 ms
迭代器遍歷 42973 ms
forEach 遍歷 40539 ms
-----------次數(shù):30000000------------
隨機訪問 1090531 ms
增強 for 遍歷 195013 ms
迭代器遍歷 185519 ms
forEach 遍歷 151925 ms
ArrayList 刪除數(shù)據(jù)
雖然有四種遍歷方式，但是能夠正確刪除數(shù)據(jù)的方式只有兩種
- 第 1 種通過迭代器進(jìn)行刪除。這種方式的話，也是《阿里代碼規(guī)約》所推薦的。
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
iter.next().hashCode();
iter.remove();
}
- 第 2 種倒序循環(huán)刪除
for(int i = list.size()-1;i>=0;i--) {
list.remove(i);
}
下面再演示下錯誤的刪除操作
- 普通 for 循環(huán)正序刪除，刪除過程中元素向左移動，不能刪除重復(fù)的元素
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
for(int i=0;i<list.size();i++){
list.remove(i);
}
System.out.println(String.join(",",list));
結(jié)果輸出：1
- 增強 for 循環(huán)刪除會拋出 java.util.ConcurrentModificationException
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
for (String s : list) {
list.remove(s);
}
System.out.println(String.join(",",list));
ArrayList ConcurrentModificationException
ConcurrentModificationException 出現(xiàn)在使用 ForEach遍歷，迭代器遍歷的同時，進(jìn)行刪除，增加出現(xiàn)的異常。平常使用的ArrayList, HashMap都有可能拋出這種異常，粗心的話，很容易犯這種錯誤，導(dǎo)致線上事故！
下面總結(jié)下ArrayList的一些使用場景，來討論是否會拋出ConcurrentModificationException
For..i 遍歷
這個遍歷的意思，是指 for(int i = 0 ; i <list.size(); i++)這種使用下標(biāo)進(jìn)行遍歷的方式。
這種情形下，增加都不會有 ConcurrentModificationException。但是也可能導(dǎo)致另外的一些問題，比如下面這段代碼，會死循環(huán)
List<Integer> list = new Arraylist<>();
list.add(1);
list.add(2);
list.add(3);
for(int i = 0;i<list.size();i++){
list.add(i);
}
遍歷刪除的情況下，不會有ConcurrentModificationException，但是要注意代碼，防止數(shù)組越界異常。下面這種形式的代碼會拋出數(shù)組越界異常。
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
int length = list.size();
for(int i = 0;i<length;i++){
list.remove(i);
}
ForEach 遍歷
ForEach 遍歷就是 For(Object o : List<Object>) 這種遍歷方式，眾所周知，F(xiàn)orEach循環(huán)只是JAVA的一個語法糖，在字節(jié)碼層面上，等同于迭代器循環(huán)遍歷。在這種情形下，增加元素一定會拋出ConcurrentModificationException，
而刪除元素在大多數(shù)情況下，會拋出ConcurrentModificationException（小知識，當(dāng)且僅當(dāng)刪除小標(biāo)為 size()-2，也就是倒數(shù)第二個元素的時候，不會拋出異常）。
這種情況下，會有異常拋出
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (Integer i : list) {
if(i == 1){
list.remove(i);
}
}
可以修改上面的判斷語句， i == 1 修改為 i == 2 則不會拋出異常。
subList
在 subList 場景中，高度注意對原集合元素個數(shù)的修改，會導(dǎo)致子列表的遍歷、增加、 刪除均會產(chǎn) ConcurrentModificationException 異常。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 對原 List 增加一個值
list.add("10");
subList.add("11"); // 這一行會報 java.util.ConcurrentModificationException
如何避免ConcurrentModificationException
- 需要遍歷新增時，最好new一個和老List相同的臨時List，遍歷老的List，然后在臨時List上進(jìn)行元素的增加
- 需要進(jìn)行刪除時，使用迭代器刪除(iterator.remove())，而不是直接調(diào)用 list.remove()
3.小心，謹(jǐn)慎
總結(jié)
ArrayList底層采用數(shù)組實現(xiàn)，是一個用于持有元素的有序、元素可重復(fù)的容器。適用于需要查找指定索引處元素的場景。當(dāng)需要頻繁插入、刪除元素，或者查找指定元素時，其復(fù)雜度為O(n)。
- 初始化 List 的時候盡量指定它的容量大小。(盡量減少擴容次數(shù))
- 當(dāng)使用無參數(shù)構(gòu)造函數(shù)創(chuàng)建ArrayList對象時，ArrayList對象中的數(shù)組初始長度為0（是一個空數(shù)組）。
- ArrayList的擴容策略是每次都增加當(dāng)前數(shù)組長度的一半（非固定分配）。
- ArrayList的擴容方式是直接創(chuàng)建一個新的數(shù)組，并將數(shù)據(jù)拷貝到新數(shù)組中。
