ArrayList簡介
ArrayList是一個(gè)實(shí)現(xiàn)了List接口的動(dòng)態(tài)數(shù)組缠犀，其容量能夠動(dòng)態(tài)增長数苫，其允許包括null在內(nèi)的所有元素。它繼承了AbstractList辨液，實(shí)現(xiàn)了List虐急、RandomAccess, Cloneable, java.io.Serializable。
因?yàn)槠浠跀?shù)組實(shí)現(xiàn)的特性滔迈，所以隨機(jī)訪問 get 和 set 效率較高止吁，但是在于添加和刪除操作，由于要移動(dòng)數(shù)據(jù)燎悍，因此效率會(huì)低些敬惦。
需要注意的是，ArrayList中的操作不是線程安全的谈山！如果多線程同時(shí)訪問 ArrayList 俄删，而其中有個(gè)線程對(duì)表結(jié)構(gòu)做了修改，則它可能會(huì)拋出錯(cuò)誤。所以畴椰，建議在單線程中才使用ArrayList举哟，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。下面我們就了解一下ArrayList一些常用的方法屬性迅矛，以及一些需要注意的地方。
本文轉(zhuǎn)自ArrayList源碼分析（基于JDK8）潜叛，本人僅在自己的理解上做了些許的修改秽褒。
ArrayList屬性
屬性中比較重要的兩個(gè)就是用于記錄當(dāng)前數(shù)組長度的 size，以及元素的緩存數(shù)組 elementData威兜，除此之外還有一個(gè)經(jīng)常用到的屬性就是從AbstractList繼承過來的modCount屬性销斟，代表ArrayList集合的修改次數(shù)。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
// 序列化id
private static final long serialVersionUID = 8683452581122892189L;
// 默認(rèn)初始的容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空實(shí)例的共享空數(shù)組實(shí)例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 為默認(rèn)大小的空實(shí)例構(gòu)建的共享空數(shù)組實(shí)例椒舵。
// 和 EMPTY_ELEMENTDATA 區(qū)別在于添加第一個(gè)元素需要膨脹多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 當(dāng)前數(shù)據(jù)對(duì)象存放地方蚂踊，當(dāng)前對(duì)象不參與序列化
transient Object[] elementData;
// 當(dāng)前數(shù)組長度
private int size;
// 數(shù)組最大長度
private static final int MAX_ARRAY_SIZE = 2147483639;
// 省略方法。笔宿。
}
ArrayList 構(gòu)造方法
無參構(gòu)造方法
如果不傳入?yún)?shù)犁钟，則使用默認(rèn)無參構(gòu)建方法創(chuàng)建ArrayList對(duì)象，如下：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
注意：此時(shí)我們創(chuàng)建的ArrayList對(duì)象中的elementData中的長度是1泼橘，size是0,當(dāng)進(jìn)行第一次add的時(shí)候涝动，elementData將會(huì)變成默認(rèn)的長度：10.
帶int類型的構(gòu)造函數(shù)
傳入的參數(shù)用于指定初始數(shù)組長度，若參數(shù)大于等于0炬灭，則給elementData 賦予對(duì)應(yīng)長度的Object數(shù)組醋粟，
若參數(shù)小于0，則拋出IllegalArgumentException異常重归，構(gòu)造方法如下：
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
帶Collection對(duì)象的構(gòu)造函數(shù)
構(gòu)造一個(gè)包含指定 Collection 的元素的列表米愿，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
其內(nèi)部實(shí)現(xiàn)大致為：
- 將 Collection 對(duì)象轉(zhuǎn)為數(shù)組鼻吮，然后將數(shù)組的地址的賦給elementData育苟。
- 更新size的值，同時(shí)判斷size的大小椎木，如果是size等于0宙搬，直接將空對(duì)象EMPTY_ELEMENTDATA的地址賦給elementData
- 如果size的值大于0，且 elementData 的 class 不等于 Object 數(shù)組的 class拓哺，則執(zhí)行Arrays.copyOf方法勇垛，把 Collection對(duì)象的內(nèi)容（可以理解為深拷貝）copy到 elementData 中。
注意：this.elementData = arg0.toArray(); 這里執(zhí)行的簡單賦值時(shí)淺拷貝士鸥，所以要執(zhí)行Arrays,copy 做深拷貝
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
常用方法
add 方法
add(E e) 方法
此方法將指定的元素添加到列表的尾部中闲孤，內(nèi)部實(shí)現(xiàn)邏輯如下：
- 確保數(shù)組已使用長度（size）加1之后足夠存入下一個(gè)數(shù)據(jù)
- 修改次數(shù)modCount 標(biāo)識(shí)自增1，如果當(dāng)前數(shù)組已使用長度（size）加1后的大于當(dāng)前的數(shù)組長度，則調(diào)用grow方法讼积，增長數(shù)組肥照，grow方法會(huì)將當(dāng)前數(shù)組的長度變?yōu)樵瓉砣萘康?.5倍。
- 確保新增的數(shù)據(jù)有地方存儲(chǔ)之后勤众，則將新元素添加到位于size的位置上舆绎，size自增1
- 成功返回 true
添加元素方法入口：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
確保添加的元素有地方存儲(chǔ)：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
將修改次數(shù)（modCount）自增1，判斷是否需要擴(kuò)充數(shù)組長度们颜，判斷條件就是用當(dāng)前所需的數(shù)組最小長度與數(shù)組的長度對(duì)比吕朵，如果大于0，則增長數(shù)組長度窥突。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
如果當(dāng)前的數(shù)組已使用空間（size）加1之后大于數(shù)組長度努溃，則增大數(shù)組容量，擴(kuò)大為原來的1.5倍阻问。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
add(int index, E element) 方法
這個(gè)方法其實(shí)和上面的add類似梧税，該方法可以按照元素的位置，指定位置插入元素称近，其后的元素往后移動(dòng)一位第队，具體的執(zhí)行邏輯如下：
- 越界檢查，否則拋出異常
- 確保數(shù)組已使用長度（size）加1之后足夠存入下一個(gè)數(shù)據(jù)
- 修改次數(shù)（modCount）標(biāo)識(shí)自增1刨秆，如果當(dāng)前數(shù)組已使用長度（size）加1后的大于當(dāng)前的數(shù)組長度斥铺，則調(diào)用grow方法，增長數(shù)組
- grow方法會(huì)將當(dāng)前數(shù)組的長度變?yōu)樵瓉砣萘康?.5倍坛善。
- 確保有足夠的容量之后晾蜘，使用System.arraycopy 將需要插入的位置（index）后面的元素統(tǒng)統(tǒng)往后移動(dòng)一位。
- 將新的數(shù)據(jù)內(nèi)容存放到數(shù)組的指定位置（index）上
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
注意：使用該方法的話將導(dǎo)致指定位置后面的數(shù)組元素全部重新移動(dòng)眠屎，即往后移動(dòng)一位剔交。
get方法
返回此列表中指定位置上的元素
public E get(int index) {
rangeCheck(index); // 若 index >= size，則拋出異常
return elementData(index);
}
set方法
public E set(int index, E element) {
rangeCheck(index); 若 index >= size改衩，則拋出異常
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
contains方法
直接調(diào)用了 indexOf 方法岖常，若返回小于 0 則返回 false。
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 {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
remove方法
根據(jù)索引remove
- 越界檢查，否則拋出異常
- modCount 自增1
- 將指定位置（index）上的元素保存到oldValue
- 將指定位置（index）上的元素都往前移動(dòng)一位
- 將最后面的一個(gè)元素置空橄镜，好讓垃圾回收器回收
- 將原來的值oldValue返回
/**
* 移除此列表中指定位置上的元素偎快。向左移動(dòng)所有后續(xù)元素（將其索引減 1）。
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(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;
}
注意：調(diào)用這個(gè)方法不會(huì)縮減數(shù)組的長度洽胶，只是將最后一個(gè)數(shù)組元素置空而已晒夹。
根據(jù)對(duì)象remove
循環(huán)遍歷所有對(duì)象，得到對(duì)象所在索引位置，然后調(diào)用fastRemove方法丐怯，執(zhí)行remove操作
/**
* 移除此列表中首次出現(xiàn)的指定元素（如果存在）喷好。如果列表不包含此元素，則列表不做改動(dòng)读跷。
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
定位到需要remove的元素索引梗搅，先將index后面的元素往前面移動(dòng)一位（調(diào)用System.arraycooy實(shí)現(xiàn)），然后將最后一個(gè)元素置空效览。
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
}
clear方法
modCount 自增无切，當(dāng)前數(shù)組長度內(nèi)的所有元素賦為 null，并把 size 置 0
/**
* 移除此列表中的所有元素钦铺。此調(diào)用返回后，列表將為空肢预。
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
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);
}
trimToSize方法
- 修改次數(shù)加1
- 將elementData中空余的空間（包括null值）去除抽兆，例如：數(shù)組長度為10，其中只有前三個(gè)元素有值族淮，其他為空辫红，那么調(diào)用該方法之后，數(shù)組的長度變?yōu)?祝辣。Arrays.copyOf返回的是一個(gè)新數(shù)組贴妻，因此達(dá)到了節(jié)省空間的效果
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
iterator方法
interator方法返回的是一個(gè)內(nèi)部類，由于內(nèi)部類的創(chuàng)建默認(rèn)含有外部的this指針蝙斜，所以這個(gè)內(nèi)部類可以調(diào)用到外部類的屬性名惩。
public Iterator<E> iterator() {
return new Itr();
}
Iterator 的 next方法
一般的話，調(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];
}
expectedModCount這個(gè)值是在用戶調(diào)用ArrayList的iterator方法時(shí)候確定的，但是在這之后用戶add，或者remove了ArrayList的元素祠挫，那么modCount就會(huì)改變那槽，那么這個(gè)值就會(huì)不相等，將會(huì)引發(fā)ConcurrentModificationException異常等舔，這個(gè)是在多線程使用情況下骚灸，比較常見的一個(gè)異常。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Iterator 的 remove方法
cursor 記錄了當(dāng)前元素索引慌植，lastRet則記錄了上一元素的索引甚牲，調(diào)用迭代器自帶的remove方法，先調(diào)用了ArrayList的remove方法后蝶柿，
會(huì)把操作次數(shù)modCount賦給expectedModCount丈钙，因此不會(huì)引發(fā)異常。
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
System.arraycopy 方法
| 參數(shù) | 說明 |
|---|---|
| src | 原數(shù)組 |
| srcPos | 原數(shù)組 |
| dest | 目標(biāo)數(shù)組 |
| destPos | 目標(biāo)數(shù)組的起始位置 |
| length | 要復(fù)制的數(shù)組元素的數(shù)目 |
Arrays.copyOf方法
original - 要復(fù)制的數(shù)組
newLength - 要返回的副本的長度
newType - 要返回的副本的類型
其實(shí)Arrays.copyOf方法返回的是一個(gè)全新數(shù)組交汤，其底層也是調(diào)用System.arraycopy實(shí)現(xiàn)的雏赦，源碼如下：
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
小結(jié)
ArrayList總體來說比較簡單，不過ArrayList還有以下一些特點(diǎn)：
- ArrayList自己實(shí)現(xiàn)了序列化和反序列化的方法芙扎，因?yàn)樗约簩?shí)現(xiàn)了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
- ArrayList基于數(shù)組方式實(shí)現(xiàn)星岗，無容量的限制（會(huì)擴(kuò)容）
添加元素時(shí)可能要擴(kuò)容（所以最好預(yù)判一下），刪除元素時(shí)不會(huì)減少容量（若希望減少容量戒洼，trimToSize()）俏橘，刪除元素時(shí)，將刪除掉的位置元素置為null圈浇，下次gc就會(huì)回收這些元素所占的內(nèi)存空間 寥掐。 - 線程不安全
- add(int index, E element)：添加元素到數(shù)組中指定位置的時(shí)候，需要將該位置及其后邊所有的元素都整塊向后復(fù)制一位
- get(int index)：獲取指定位置上的元素時(shí)磷蜀，可以通過索引直接獲炔苷獭（O(1)）
- remove(Object o)需要遍歷數(shù)組
- remove(int index)不需要遍歷數(shù)組，只需判斷index是否符合條件即可蠕搜，效率比remove(Object o)高
- contains(E)需要遍歷數(shù)組
- 使用iterator遍歷可能會(huì)引發(fā)多線程異常
