深入ArrayList源碼分析（JDK1.8）
Java 集合系列源碼分析文章：
ArrayList源碼分析（基于JDK8）
數(shù)據(jù)結(jié)構(gòu)中有兩種存儲(chǔ)結(jié)構(gòu)废岂，分別是：順序存儲(chǔ)結(jié)構(gòu)邻吭、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)胃榕。在 Java 中喇勋，對(duì)于這四種結(jié)構(gòu)分別進(jìn)行實(shí)現(xiàn)的類有：
- 順序存儲(chǔ)結(jié)構(gòu)：ArrayList、Stack
- 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：LinkedList别凤、Queue
這里只對(duì) ArrayList 的源碼進(jìn)行分析饰序，ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于 動(dòng)態(tài)數(shù)組 规哪。與Java 中的數(shù)組相比求豫，它的容量能動(dòng)態(tài)增長(zhǎng)。
特點(diǎn)
- 基本的
ArrayList常用于隨機(jī)訪問元素，但是在 List 中間插入和移除元素較慢蝠嘉； -
ArrayList中的操作不是線程安全的最疆。所以建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList蚤告，建議使用CopyOnWriteArrayList努酸。
繼承關(guān)系
上面可以看到，ArrayList 實(shí)現(xiàn)來四個(gè)接口一個(gè)抽象類杜恰。它繼承類 AbstracList 抽象類获诈，實(shí)現(xiàn)了 List 、 RandomAccess （隨機(jī)訪問）心褐、 Cloneable （可克绿蛳选）、 Serializable （序列化）四個(gè)接口
-
ArrayList繼承于AbstractList逗爹，實(shí)現(xiàn)了List亡嫌。它是一個(gè)數(shù)組隊(duì)列，提供了相關(guān)的添加掘而、刪除挟冠、修改、遍歷等功能袍睡； -
ArrayList實(shí)現(xiàn)了RandmoAccess接口知染，即提供了隨機(jī)訪問功能； -
ArrayList實(shí)現(xiàn)了Cloneable接口女蜈，即覆蓋了函數(shù)clone()，能被克律瘛伪窖； -
ArrayList實(shí)現(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ù)組的長(zhǎng)度
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ù)組元素個(gè)數(shù)
private int size;
// 要分配的數(shù)組的最大大小，嘗試分配更大的陣列可能會(huì)導(dǎo)致 OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
}
ArrayList 的底層實(shí)現(xiàn)是數(shù)組吧享，默認(rèn)的數(shù)組大小是 10魏割。
構(gòu)造函數(shù)
- ArrayList()：構(gòu)造一個(gè)初始容量為10的空列表
- ArrayList(Collection<?extend E> c)：構(gòu)造一個(gè)包含指定元素的列表
- ArrayList( int initialCapcity )：構(gòu)造一個(gè)具有初始容量值得空列表
// 第一種，調(diào)用ArrayList(10) 默認(rèn)初始化一個(gè)大小為10的Object數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 第二種
public ArrayList(int initialCapacity) {
// 如果用戶初始化大小大于0钢颂，則新建一個(gè)用戶初始化值大小的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ù)組化處理并將這個(gè)數(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ù)組時(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;
}
}
增刪改查操作
對(duì)于增刪改查的基本操作尼桶，在這里只給出一些比較重要的源代碼進(jìn)行解析。
增加操作
- add(E e)：添加一個(gè)元素到列表的末尾锯仪。
- add( int index, E element ) :在指定的位置添加元素
- addAll( Collection<? extends E> c )：添加一個(gè)集合到元素的末尾.以上返回類型是boolean
- ensureCapcity（int minCapcity）：確保列表中含有minCapcity的最小容量
ArrayList默認(rèn)的插入是插在數(shù)組的末尾泵督，在不需要擴(kuò)容時(shí)是一個(gè)時(shí)間復(fù)雜度O(1)的操作，需要擴(kuò)容時(shí)復(fù)雜度為O(n)庶喜，所以如果預(yù)先能判斷數(shù)據(jù)量的大小小腊，可以指定初始化數(shù)組的大小，避免過多的擴(kuò)容操作溃卡。下面代碼看一些第一個(gè)增加元素的方法實(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ù)組的長(zhǎng)度溢豆，則進(jìn)行擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 第三步：擴(kuò)容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 將數(shù)組的長(zhǎng)度增加原來數(shù)組的一半，也就是1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴(kuò)充一半后仍然不夠瘸羡，則 newCapacity = minCapacity漩仙；minCapacity實(shí)際元素的個(gè)數(shù)
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果擴(kuò)充后的容量超過最大值變量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ù)組對(duì)象，最后將elementData的引用指向新的數(shù)組對(duì)象
// 原有的數(shù)組對(duì)象因?yàn)闆]有了引用犹赖，一段時(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還支持在指定索引處插入。在指定索引處插入時(shí)峻村，需要將指定索引及其之后的元素向后推一個(gè)位置麸折，所以是一個(gè)復(fù)雜度O(n)的操作。源碼如下：
// 第一步：
public void add(int index, E element) {
// 檢查index的值是否在0到size之間粘昨，可以為size.
rangeCheckForAdd(index);
// 看 elementData 的長(zhǎng)度是否足夠垢啼，不夠擴(kuò)容
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)：刪除列表中第一個(gè)出現(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 刪除元素時(shí)张肾，需要將所刪元素之后位置的元素都向前推一個(gè)位置芭析，復(fù)雜度也是O(n)。所以ArrayList不適合需要頻繁在指定位置插入元素及刪除的應(yīng)用場(chǎng)景吞瞪，看代碼實(shí)現(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
// 第四步：返回要?jiǎng)h除的值
return oldValue;
}
再看一個(gè)其它的實(shí)現(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)于&運(yùn)算
- set（int index,E element）：用element替換index位置上的元素芍秆。
- size()：返回此列表的元素?cái)?shù)
- sort(Comparator<? super E> c)：按照指定的排序規(guī)則排序
- subList( int from , int to )：返回從from到to之間的列表
- toArray()：將列表轉(zhuǎn)化為數(shù)組
- trimToSize( )：修改當(dāng)前實(shí)例的容量是列表的當(dāng)前大小惯疙。
set方法
確保set的位置小于當(dāng)前數(shù)組的長(zhǎng)度（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)建了一個(gè)ArrayList 類里面的一個(gè)內(nèi)部類SubList對(duì)象，傳入的值中第一個(gè)參數(shù)時(shí)this參數(shù)酥郭，其實(shí)可以理解為返回當(dāng)前l(fā)ist的部分視圖华坦，真實(shí)指向的存放數(shù)據(jù)內(nèi)容的地方還是同一個(gè)地方，如果修改了sublist返回的內(nèi)容的話不从，那么原來的list也會(huì)變動(dòng)惜姐。
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é)果不可強(qiáng)轉(zhuǎn)成 ArrayList，否則會(huì)拋出 ClassCastException 異常椿息，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 說明：subList 返回的是 ArrayList 的內(nèi)部類 SubList歹袁，并不是 ArrayList ，而是 ArrayList 的一個(gè)視圖寝优，對(duì)于 SubList 子列表的所有操作最終會(huì)反映到原列表上条舔。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
ArrayList<String> strings = (ArrayList)list.subList(0, 1);
運(yùn)行結(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 場(chǎng)景中，高度注意對(duì)原集合元素個(gè)數(shù)的修改乏矾，會(huì)導(dǎo)致子列表的遍歷孟抗、增加、 刪除均會(huì)產(chǎn) ConcurrentModificationException 異常钻心。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 對(duì)原 List 增加一個(gè)值
list.add("10");
subList.add("11"); // 這一行會(huì)報(bào) java.util.ConcurrentModificationException
trimToSize方法
public void trimToSize() {
// 修改次數(shù)加1
modCount++;
// 如果當(dāng)前元素小于數(shù)組容量凄硼，則將elementData中空余的空間（包括null值）去除
// 例如：數(shù)組長(zhǎng)度為10，其中只有前三個(gè)元素有值捷沸，其他為空摊沉，那么調(diào)用該方法后，數(shù)組的長(zhǎng)度變?yōu)?
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
toArray方法
第一個(gè)痒给，Object[] toArray()方法说墨。該方法有可能會(huì)拋出java.lang.ClassCastException異常，如果直接用向下轉(zhuǎn)型的方法苍柏，將整個(gè)ArrayList集合轉(zhuǎn)變?yōu)橹付愋偷腁rray數(shù)組尼斧，便會(huì)拋出該異常，而如果轉(zhuǎn)化為Array數(shù)組時(shí)不向下轉(zhuǎn)型序仙，而是將每個(gè)元素向下轉(zhuǎn)型突颊，則不會(huì)拋出該異常鲁豪，顯然對(duì)數(shù)組中的元素一個(gè)個(gè)進(jìn)行向下轉(zhuǎn)型潘悼，效率不高，且不太方便爬橡。
第二個(gè)治唤， T[] toArray(T[] a)方法。該方法可以直接將ArrayList轉(zhuǎn)換得到的Array進(jìn)行整體向下轉(zhuǎn)型（轉(zhuǎn)型其實(shí)是在該方法的源碼中實(shí)現(xiàn)的）糙申，且從該方法的源碼中可以看出宾添，參數(shù)a的大小不足時(shí)，內(nèi)部會(huì)調(diào)用Arrays.copyOf方法，該方法內(nèi)部創(chuàng)建一個(gè)新的數(shù)組返回缕陕，因此對(duì)該方法的常用形式如下：
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ù)組中的每一個(gè)元素作對(duì)比，如果找到對(duì)于的元素沥阳，則返回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方法返回的是一個(gè)內(nèi)部類桐罕，由于內(nèi)部類的創(chuàng)建默認(rèn)含有外部的this指針脉让，所以這個(gè)內(nèi)部類可以調(diào)用到外部類的屬性。
public Iterator<E> iterator() {
return new Itr();
}
一般的話冈绊，調(diào)用完iterator之后侠鳄，我們會(huì)使用iterator做遍歷，這里使用next做遍歷的時(shí)候有個(gè)需要注意的地方死宣，就是調(diào)用next的時(shí)候伟恶，可能會(huì)引發(fā)ConcurrentModificationException，當(dāng)修改次數(shù)毅该，與期望的修改次數(shù)（調(diào)用iterator方法時(shí)候的修改次數(shù)）不一致的時(shí)候博秫，會(huì)發(fā)生該異常，詳細(xì)我們看一下代碼實(shí)現(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這個(gè)值是在用戶調(diào)用ArrayList的iterator方法時(shí)候確定的眶掌，但是在這之后用戶add挡育，或者remove了ArrayList的元素，那么modCount就會(huì)改變朴爬，那么這個(gè)值就會(huì)不相等即寒，將會(huì)引發(fā)ConcurrentModificationException異常，這個(gè)是在多線程使用情況下召噩，比較常見的一個(gè)異常母赵。
遍歷
ArrayList 遍歷的四種方式
- 第1種，普通for循環(huán)隨機(jī)訪問具滴，通過索引值去遍歷凹嘲。
// 隨機(jī)訪問
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。
// 增強(qiáng)for循環(huán)
for (String s : list) {
value = s;
}
- 第4種 forEach + lambda 循環(huán)遍歷
list.forEach(p -> {
p.hashCode();
});
性能對(duì)比
既然有 4 種遍歷凶朗，那我們看看哪種遍歷效率下面我們通過一個(gè)實(shí)驗(yàn)來看下這四種循環(huán)的耗時(shí)吧：測(cè)試代碼
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);
// 隨機(jī)訪問通過索引值去遍歷瓷胧。
long time1 = System.nanoTime();
testRandFor(size, list);
long time2 = System.nanoTime();
// 增強(qiáng) 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("隨機(jī)訪問\t\t" + (time2 - time1) / 1000 + " ms");
System.out.println("增強(qiáng) 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;
}
}
測(cè)試結(jié)果：
結(jié)論：如果數(shù)據(jù)量比較少的話貌似四種循環(huán)耗時(shí)都差不多，但是隨著數(shù)據(jù)量的增長(zhǎng)會(huì)發(fā)現(xiàn) foreach 的效率是最好的棚愤。但是從上面我們會(huì)發(fā)現(xiàn)一個(gè)奇怪的現(xiàn)象抖单，第一次循環(huán)的時(shí)候forEach 遍歷的時(shí)間是最長(zhǎng)的盡管數(shù)據(jù)量非常少也會(huì)這樣。但是后面的耗時(shí)就正常了遇八。如果放開測(cè)試?yán)锩娴念A(yù)熱代碼矛绘，每次跑出來的耗時(shí)也是正常的。
-----------次數(shù):10------------
隨機(jī)訪問 15 ms
增強(qiáng) for 遍歷 8 ms
迭代器遍歷 6 ms
forEach 遍歷 65728 ms
-----------次數(shù):50------------
隨機(jī)訪問 16 ms
增強(qiáng) for 遍歷 21 ms
迭代器遍歷 13 ms
forEach 遍歷 10 ms
-----------次數(shù):100------------
隨機(jī)訪問 7 ms
增強(qiáng) for 遍歷 23 ms
迭代器遍歷 34 ms
forEach 遍歷 19 ms
-----------次數(shù):500------------
隨機(jī)訪問 64 ms
增強(qiáng) for 遍歷 47 ms
迭代器遍歷 39 ms
forEach 遍歷 105 ms
-----------次數(shù):1000------------
隨機(jī)訪問 129 ms
增強(qiáng) for 遍歷 99 ms
迭代器遍歷 81 ms
forEach 遍歷 58 ms
-----------次數(shù):10000------------
隨機(jī)訪問 1748 ms
增強(qiáng) for 遍歷 1921 ms
迭代器遍歷 1270 ms
forEach 遍歷 2212 ms
-----------次數(shù):50000------------
隨機(jī)訪問 4013 ms
增強(qiáng) for 遍歷 2739 ms
迭代器遍歷 3628 ms
forEach 遍歷 2368 ms
-----------次數(shù):100000------------
隨機(jī)訪問 9874 ms
增強(qiáng) for 遍歷 4500 ms
迭代器遍歷 5159 ms
forEach 遍歷 6232 ms
-----------次數(shù):5000000------------
隨機(jī)訪問 215933 ms
增強(qiáng) for 遍歷 27000 ms
迭代器遍歷 26586 ms
forEach 遍歷 22105 ms
-----------次數(shù):10000000------------
隨機(jī)訪問 379588 ms
增強(qiáng) for 遍歷 57104 ms
迭代器遍歷 42973 ms
forEach 遍歷 40539 ms
-----------次數(shù):30000000------------
隨機(jī)訪問 1090531 ms
增強(qiáng) 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);
}
下面再演示下錯(cuò)誤的刪除操作
- 普通 for 循環(huán)正序刪除囚玫，刪除過程中元素向左移動(dòng)，不能刪除重復(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
- 增強(qiáng) for 循環(huán)刪除會(huì)拋出 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遍歷读规，迭代器遍歷的同時(shí)抓督，進(jìn)行刪除，增加出現(xiàn)的異常束亏。平常使用的ArrayList, HashMap都有可能拋出這種異常铃在，粗心的話，很容易犯這種錯(cuò)誤碍遍，導(dǎo)致線上事故定铜！
下面總結(jié)下ArrayList的一些使用場(chǎng)景，來討論是否會(huì)拋出ConcurrentModificationException
For..i 遍歷
這個(gè)遍歷的意思怕敬，是指 for(int i = 0 ; i <list.size(); i++)這種使用下標(biāo)進(jìn)行遍歷的方式揣炕。
這種情形下，增加都不會(huì)有 ConcurrentModificationException东跪。但是也可能導(dǎo)致另外的一些問題畸陡，比如下面這段代碼，會(huì)死循環(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);
}
遍歷刪除的情況下虽填，不會(huì)有ConcurrentModificationException丁恭，但是要注意代碼，防止數(shù)組越界異常卤唉。下面這種形式的代碼會(huì)拋出數(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的一個(gè)語法糖竭恬，在字節(jié)碼層面上，等同于迭代器循環(huán)遍歷熬的。在這種情形下痊硕，增加元素一定會(huì)拋出ConcurrentModificationException，
而刪除元素在大多數(shù)情況下押框，會(huì)拋出ConcurrentModificationException（小知識(shí)岔绸，當(dāng)且僅當(dāng)刪除小標(biāo)為 size()-2，也就是倒數(shù)第二個(gè)元素的時(shí)候橡伞，不會(huì)拋出異常）盒揉。
這種情況下，會(huì)有異常拋出
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 則不會(huì)拋出異常刚盈。
subList
在 subList 場(chǎng)景中，高度注意對(duì)原集合元素個(gè)數(shù)的修改挂脑，會(huì)導(dǎo)致子列表的遍歷藕漱、增加、 刪除均會(huì)產(chǎn) ConcurrentModificationException 異常崭闲。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 對(duì)原 List 增加一個(gè)值
list.add("10");
subList.add("11"); // 這一行會(huì)報(bào) java.util.ConcurrentModificationException
如何避免ConcurrentModificationException
- 需要遍歷新增時(shí)肋联，最好new一個(gè)和老List相同的臨時(shí)List，遍歷老的List刁俭，然后在臨時(shí)List上進(jìn)行元素的增加
- 需要進(jìn)行刪除時(shí)橄仍，使用迭代器刪除(iterator.remove())，而不是直接調(diào)用 list.remove()
3.小心牍戚，謹(jǐn)慎
總結(jié)
ArrayList底層采用數(shù)組實(shí)現(xiàn)沙兰，是一個(gè)用于持有元素的有序、元素可重復(fù)的容器翘魄。適用于需要查找指定索引處元素的場(chǎng)景鼎天。當(dāng)需要頻繁插入、刪除元素暑竟，或者查找指定元素時(shí)斋射，其復(fù)雜度為O(n)。
- 初始化 List 的時(shí)候盡量指定它的容量大小但荤。(盡量減少擴(kuò)容次數(shù))
- 當(dāng)使用無參數(shù)構(gòu)造函數(shù)創(chuàng)建ArrayList對(duì)象時(shí)罗岖，ArrayList對(duì)象中的數(shù)組初始長(zhǎng)度為0（是一個(gè)空數(shù)組）。
- ArrayList的擴(kuò)容策略是每次都增加當(dāng)前數(shù)組長(zhǎng)度的一半（非固定分配）腹躁。
- ArrayList的擴(kuò)容方式是直接創(chuàng)建一個(gè)新的數(shù)組桑包，并將數(shù)據(jù)拷貝到新數(shù)組中。
