定義
除了實(shí)現(xiàn)了List接口聋伦，還實(shí)現(xiàn)了RandomAccess还绘，Cloneable, java.io.Serializable接口
transient Object[] elementData; // non-private to simplify nested class access
transient 關(guān)鍵字使得進(jìn)行序列化時(shí)會(huì)忽略此對(duì)象數(shù)組痹兜，主要考慮elementData在序列化時(shí)沒(méi)有被占滿奔害，如果對(duì)elementData進(jìn)行序列化時(shí)將造成空間和時(shí)間上的浪費(fèi)拓售，所以在序列化時(shí)是遍歷數(shù)組非空元素兽肤。
3種構(gòu)造函數(shù)
- 無(wú)參構(gòu)造函數(shù)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} //0個(gè)元素的Object數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//默認(rèn)初始化，沒(méi)有分配堆內(nèi)存空間
}
構(gòu)造時(shí)是將空數(shù)組賦值給elementData 另假，但是在隨后的第一個(gè)add元素的時(shí)候，會(huì)先新創(chuàng)建一個(gè)容量為10的初始數(shù)組怕犁。
- 初始容量構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];//分配指定初始容量的堆內(nèi)存空間
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- 初始集合構(gòu)造函數(shù)
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//集合轉(zhuǎn)換成數(shù)組對(duì)象边篮，并將引用直接賦值給緩沖數(shù)組
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); //拷貝并進(jìn)行類型轉(zhuǎn)換
} else { //如果集合長(zhǎng)度為0，則將緩沖數(shù)組設(shè)置為0元素的空數(shù)組奏甫，沒(méi)有分配堆內(nèi)存空間
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
add
在尾部添加不需要通過(guò)復(fù)制來(lái)移動(dòng)元素
在指定位置上添加元素戈轿，需要通過(guò)原生方法System.arraycopy()復(fù)制來(lái)實(shí)現(xiàn)數(shù)組元素的移動(dòng)
System.arraycopy()是一個(gè)原生的方法，效率較高阵子，但注意的是這里的復(fù)制是淺復(fù)制思杯，即只復(fù)制引用，對(duì)堆中始終只有一份元素對(duì)象挠进。
- Array.copyOf()方法通過(guò)方法簽名來(lái)區(qū)別對(duì)待對(duì)象類型數(shù)組和基本類型數(shù)組色乾，基本數(shù)據(jù)類型數(shù)組又是通過(guò)方法的重載來(lái)匹配不同基本數(shù)據(jù)類型。
- 在對(duì)象類型數(shù)組復(fù)制中领突，也會(huì)對(duì)對(duì)象類型進(jìn)行判斷暖璧，如果確認(rèn)是Object類型則先創(chuàng)建Object數(shù)組，然后轉(zhuǎn)型為指定類型T[]君旦，然后將舊數(shù)組元素復(fù)制到新創(chuàng)建的數(shù)組中澎办；如果不是對(duì)象類型的數(shù)組，則通過(guò)Array.newInstance()反射創(chuàng)建基本類型的數(shù)組
remove
元素移動(dòng)見(jiàn)下圖 index == 2
0 1 2 3 4
0 1 3 4 4
0 1 3 4
刪除指定位置上的元素金砍，時(shí)間復(fù)雜度為O(1)
刪除第一個(gè)和指定對(duì)象相等的元素局蚀，會(huì)遍歷整個(gè)數(shù)組，時(shí)間復(fù)雜度為O(n)
擴(kuò)容函數(shù)
public void ensureCapacity(int minCapacity) {
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) { // 當(dāng)指定的最小容量大于最小拓展容量時(shí)才會(huì)進(jìn)行擴(kuò)容
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 每一次擴(kuò)容都要增加修改計(jì)數(shù)
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 溢出檢查
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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) // 如果新容量大于數(shù)組的最大長(zhǎng)度則返回超大容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// overflow 小于0恕稠，可能是容量本身為負(fù)琅绅，或者整數(shù)超大導(dǎo)致二進(jìn)制溢出符號(hào)位變1，出現(xiàn)負(fù)值谱俭，反正都是溢出（上下溢出）
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? // 判斷最小容量是否大于最大數(shù)組長(zhǎng)度
Integer.MAX_VALUE : // 大于則將整數(shù)的最大值作為新容量的大小
MAX_ARRAY_SIZE; // 否則把數(shù)組的最大長(zhǎng)度作為新容量的大小
}
- 容量的理論最大值為Integer.MAX_VALUE奉件，當(dāng)數(shù)組長(zhǎng)度超過(guò)MAX_ARRAY_SIZE時(shí)宵蛀，會(huì)將數(shù)組擴(kuò)容到理論最大值，見(jiàn) hugeCapacity() 方法
- MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;是因?yàn)橛行┨摂M機(jī)會(huì)在數(shù)組類型數(shù)據(jù)堆中保留head Word字段會(huì)占用空間县貌，所以可分配的數(shù)組長(zhǎng)度達(dá)不到整數(shù)的最大值术陶，-8 是一個(gè)保險(xiǎn)值（32位JVM需要32位head word，64位JVM需要64位head word煤痕，即最多8字節(jié)）梧宫，確保不會(huì)因?yàn)閔ead word的空間占用而拋出OutOfMemoryError
序列化
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
私有設(shè)計(jì)迭代器
public Iterator<E> iterator() { // 返回的是Itr向上轉(zhuǎn)型的Iterator接口
return new Itr();
}
private class Itr implements Iterator<E> // 基于緩沖數(shù)組elementData進(jìn)行設(shè)計(jì)的迭代器 私有內(nèi)部類
public ListIterator<E> listIterator() { // 返回的是ListItr向上轉(zhuǎn)型的ListIterator接口
return new ListItr(0);
}
private class ListItr extends Itr implements ListIterator<E> // 拓展了關(guān)于List的迭代器接口
私有迭代器，主要實(shí)現(xiàn)了范圍檢查以及配合游標(biāo)的移動(dòng)摆碉，實(shí)現(xiàn)了fail-fast機(jī)制（在遍歷過(guò)程中如果modCount與expectedModCount不相等塘匣，則拋出ConcurrentModificationException異常），源碼比較簡(jiǎn)單（思路和AbstractList.Itr巷帝、AbstractLsit.List.Itr一樣）忌卤，不在贅述。
iterator()方法對(duì)私有內(nèi)部類進(jìn)行了向上類型轉(zhuǎn)換楞泼，而且將內(nèi)部私有類也轉(zhuǎn)換成了公有Iterator接口驰徊，可在類外獲取此迭代器，同理ListIterator()
子列表的實(shí)現(xiàn)
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex); // this 多態(tài)堕阔，方法動(dòng)態(tài)綁定
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent; // 通過(guò)持有父類對(duì)象實(shí)例棍厂，實(shí)現(xiàn)對(duì)實(shí)例方法的包裝， 裝飾器模式
private final int parentOffset;
private final int offset;
int size;
...
}
返回指定范圍的子列表超陆，同樣是將私有內(nèi)部實(shí)現(xiàn)轉(zhuǎn)換成公有接口牺弹，完成面向接口的編程，將內(nèi)部實(shí)現(xiàn)和公有接口進(jìn)行分離时呀。
子列表對(duì)象的通過(guò)裝飾器模式和對(duì)象的多態(tài)（方法動(dòng)態(tài)綁定）张漂，復(fù)用了ArrayList的代碼實(shí)現(xiàn)，并實(shí)現(xiàn)了RandomAccess接口退唠。
需要注意的是在子列表上的操作（如add鹃锈、remove等）都會(huì)反映到原來(lái)的ArrayList上面（共用elementData），即子列表只是提供一種在原列表上的一種視圖瞧预。
排序
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c); // 通過(guò)Array.sort排序
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
java8 并行迭代 Spliterator接口
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
static final class ArrayListSpliterator<E> implements Spliterator<E> {
private final ArrayList<E> list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index 最后一個(gè)元素的為位置屎债，集合邊界
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
if ((hi = fence) < 0) { // fence邊界還沒(méi)有初始化，則進(jìn)行初始化邊界
if ((lst = list) == null) // 列表為空引用垢油，則初始邊界及上邊界為 0
hi = fence = 0;
else { // 列表不為null盆驹，則將集合的size作為邊界和上邊界的值
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi; // 返回上邊界
}
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
// 只有l(wèi)ow = index和hi相差為0或1時(shí)，才會(huì)發(fā)生條件為true的情況滩愁，此時(shí)可分割的范圍太小躯喇，則不進(jìn)行分割
return (lo >= mid) ? null : // divide range in half unless too small
// 將本身的集合迭代器邊界設(shè)置為[mid,hi)，并返回新的集合迭代器，范圍為[lo,mid)廉丽，實(shí)現(xiàn)遍歷二分
new ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) { // 當(dāng)當(dāng)前索引小于邊界（elementData 索引范圍為[0,hi = size)）
index = i + 1;
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e); // 對(duì)下一個(gè)剩余元素執(zhí)行操作
if (list.modCount != expectedModCount) // fail-fast機(jī)制
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
//當(dāng)集合引用不為null倦微，且集合的緩沖數(shù)組不為null
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) { //當(dāng)fence邊界沒(méi)有初始化則將集合的size作為邊界
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) { // 遍歷執(zhí)行
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc) // fail-fast機(jī)制
return;
}
}
throw new ConcurrentModificationException(); // fail-fast機(jī)制
}
}
Spliterator 是Java8 引入的新接口，顧名思義正压，Spliterator可以理解為Iterator的Split版本欣福，對(duì)于Java的流API，進(jìn)行并行分割迭代計(jì)算焦履，充分利用多核CPU的優(yōu)勢(shì)拓劝，并行計(jì)算具有極大的輔助作用。在使用Iterator的時(shí)候嘉裤，我們一般都是單線程地去順序遍歷集合的元素郑临，但是使用Spliterator可以將集合元素分割成多份，使用多個(gè)線程 同時(shí)進(jìn)行迭代屑宠，大大地提高了執(zhí)行效率厢洞。
// 判斷時(shí)候還有元素，如果有則對(duì)下一個(gè)剩余的元素執(zhí)行action操作典奉，
// 如果沒(méi)有下一個(gè)剩余的元素可以被執(zhí)行則返回false犀变，否則返回true
boolean tryAdvance(Consumer<? super T> action);
// 對(duì)每一個(gè)剩余的元素都執(zhí)行action操作
default void forEachRemaining(Consumer<? super T> action) {
do { } while (tryAdvance(action)); // 通過(guò)調(diào)用tryAdvance實(shí)現(xiàn)
}
// 如果集合可以分割，則對(duì)集合進(jìn)行分割秋柄，并返回Spliterator
Spliterator<T> trySplit();
...
3 種訪問(wèn)元素訪問(wèn)
- 隨機(jī)訪問(wèn)
String value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (String )list.get(i);
}
此方法是直接在緩沖數(shù)組上的通過(guò)索引訪問(wèn)的，速度最快
- foreach訪問(wèn)
String value = null;
for(String a : list){
value = a;
}
foreach訪問(wèn)也比隨機(jī)訪問(wèn)要慢蠢正，但是要快于迭代器的方式（foreach是一種語(yǔ)法糖骇笔，在編譯期間需要進(jìn)行語(yǔ)法解析，插入額外的輔助訪問(wèn)的代碼嚣崭，會(huì)有一定的消耗）
- 迭代器訪問(wèn)
String value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (String )iter.next();
}
速度最慢笨触，由于要保存迭代器的狀態(tài)，所以性能受到損耗
總結(jié)
- 當(dāng)新增元素時(shí)通過(guò)ensureCapacityInternal來(lái)擴(kuò)大elementData的指定新增的容量雹舀，刪除元素時(shí)芦劣，只是將elementData的指定位置引用賦值為null，方便GC回收说榆，重新復(fù)制數(shù)組減少容量虚吟；而且無(wú)參構(gòu)造函數(shù)只有第一次添加元素時(shí)才會(huì)分配存儲(chǔ)空間。
- ArrayList是通過(guò)緩沖數(shù)組elementData來(lái)保存數(shù)據(jù)的签财，當(dāng)容量不夠時(shí)串慰，對(duì)element進(jìn)行擴(kuò)容（** int newCapacity = oldCapacity + (oldCapacity >> 1);即增加原來(lái)容量的一半**），所有的查詢和修改都是通過(guò)數(shù)組的索引來(lái)操作elementData數(shù)組的
- ArrayList有三種構(gòu)造函數(shù)唱蒸，一種是指定初始容量的邦鲫，會(huì)創(chuàng)建一個(gè)初始容量的數(shù)組并賦值給elementData引用，一種是默認(rèn)構(gòu)造函數(shù)神汹，使用的是默認(rèn)容量10庆捺，一種是通過(guò)一個(gè)集合來(lái)構(gòu)建
- clone函數(shù)古今，底層通過(guò)System.arraycopy將原來(lái)ArrayList的緩沖數(shù)組elementData拷貝給新的ArrayList的緩沖數(shù)組
- 每一次影響集合結(jié)構(gòu)的修改（包括增加、刪除滔以、擴(kuò)容捉腥、移動(dòng)元素位置，不包括修改set）ArrayList的時(shí)候都要使得modCount自增醉者，確保感知在使用迭代器和進(jìn)行序列化過(guò)程中是否發(fā)生并發(fā)修改ArrayList的情況
- 序列化時(shí)先寫(xiě)集合的size（不是容量即element的長(zhǎng)度）到輸出流但狭，然后在寫(xiě)elementData數(shù)組元素到輸出流，反序列化時(shí)則是先讀集合容量撬即，然后在讀集合元素立磁。
- 在子列表上的操作（如add、remove等）都會(huì)反映到原來(lái)的ArrayList上面（共用elementData）剥槐，即子列表只是提供一種在原列表上的一種視圖唱歧。
