ArrayList源碼分析--jdk1.8
LinkedList源碼分析--jdk1.8
HashMap源碼分析--jdk1.8
AQS源碼分析--jdk1.8
ReentrantLock源碼分析--jdk1.8
十多年的六合網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷(xiāo)的優(yōu)勢(shì)是能夠根據(jù)用戶(hù)設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整六合建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)從事“六合網(wǎng)站設(shè)計(jì)”,“六合網(wǎng)站推廣”以來(lái)，每個(gè)客戶(hù)項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
??1. ArrayList是可以動(dòng)態(tài)擴(kuò)容和動(dòng)態(tài)刪除冗余容量的索引序列，基于數(shù)組實(shí)現(xiàn)的集合。
?2. ArrayList支持隨機(jī)訪(fǎng)問(wèn)、克隆、序列化，元素有序且可以重復(fù)。
?3. ArrayList初始默認(rèn)長(zhǎng)度10，超出擴(kuò)容1.5倍，使用Object[]存儲(chǔ)各種數(shù)據(jù)類(lèi)型。
??數(shù)據(jù)結(jié)構(gòu)是集合的精華所在，數(shù)據(jù)結(jié)構(gòu)往往也限制了集合的作用和側(cè)重點(diǎn)，了解各種數(shù)據(jù)結(jié)構(gòu)是我們分析源碼的必經(jīng)之路。
?ArrayList的數(shù)據(jù)結(jié)構(gòu)如下：
重慶分公司
重慶分公司
/*
* 用數(shù)組實(shí)現(xiàn)的集合，支持隨機(jī)訪(fǎng)問(wèn)，元素有序且可以重復(fù)
* RandomAccess(ArrayList) 支持快速隨機(jī)訪(fǎng)問(wèn)，使用for循環(huán)更加快速
* LinkedList 使用 iterator迭代器更加 快速
* RandomAccess 這是一個(gè)標(biāo)記接口，一般此標(biāo)記接口用于 List 實(shí)現(xiàn)，以表明它們支持快速（通常是恒定時(shí)間）的隨機(jī)訪(fǎng)問(wèn)。
* 該接口的主要目的是允許通用算法改變其行為，以便在應(yīng)用于隨機(jī)或順序訪(fǎng)問(wèn)列表時(shí)提供良好的性能
* 包含類(lèi)中的基礎(chǔ)屬性和3個(gè)構(gòu)造方法
*/
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 默認(rèn)長(zhǎng)度 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 默認(rèn)空的數(shù)組
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* ArrayList中的元素 是Object[]類(lèi)型的數(shù)組
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 動(dòng)態(tài)數(shù)組的實(shí)際大小 ，默認(rèn)為0
* @serial
*/
private int size;
/**
* 最大數(shù)組容量2147483639
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 集合長(zhǎng)度構(gòu)造函數(shù)
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 無(wú)參構(gòu)造函數(shù)，設(shè)置元素?cái)?shù)組為空 注意此時(shí)初始容量是0，而不是大家以為的 10
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 集合參數(shù)構(gòu)造函數(shù)
*/
public ArrayList(Collection c) {
elementData = c.toArray(); // 轉(zhuǎn)化為數(shù)組
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class) //是否成功轉(zhuǎn)化為Object類(lèi)型數(shù)組
elementData = Arrays.copyOf(elementData, size, Object[].class); //不為Object數(shù)組的話(huà)就進(jìn)行復(fù)制
}
? ArrayList extends AbstractList
? AbstractList extends AbstractCollection
?java中所有類(lèi)都繼承Object，所以ArrayList的繼承結(jié)構(gòu)如上圖。
? 1. AbstractList是一個(gè)抽象類(lèi)，實(shí)現(xiàn)了List接口，List 定義了一些List通用方法，而AbstractList抽象類(lèi)中可以有抽象方法，還可以有具體的實(shí)現(xiàn)方法，AbstractList實(shí)現(xiàn)接口中一些通用的方法，實(shí)現(xiàn)了基礎(chǔ)的add/get/indexOf/iterator/subList/RandomAccessSubList方法，ArrayList再繼承AbstractList，拿到通用基礎(chǔ)的方法，然后自己在實(shí)現(xiàn)一些自己特有的方法，這樣的好處是：讓代碼更簡(jiǎn)潔，繼承結(jié)構(gòu)最底層的類(lèi)中通用的方法，減少重復(fù)代碼。
? 2.ArrayList實(shí)現(xiàn)了List、RandomAccess、Cloneable、Serializable接口
? ??1)List接口，ArrayList既然繼承自AbstractList抽象類(lèi)，而AbstractList已 經(jīng)實(shí)現(xiàn)了List接口，那么ArrayList類(lèi)為何還要再實(shí)現(xiàn)List接口呢？我們帶著疑問(wèn)往下看：
public class Demo1 extends ArrayList {
public static void main(String[] args) {
//返回[]
System.out.println(Arrays.toString(Demo1.class.getInterfaces()));
}
public class Demo2 implements Serializable {
public static void main(String[] args) {
//返回[interface java.io.Serializable]
System.out.println(Arrays.toString(Demo2.class.getInterfaces()));
}
public class Test{
public static void main(String[] args) {
Serializable c1 = new Demo1();//未顯示實(shí)現(xiàn)接口
Serializable c2 = new Demo2();//顯示實(shí)現(xiàn)接口
Serializable proxy2 = createProxy(c2);
proxy2.foo();
Serializable proxy1 = createProxy(c1);
proxy1.foo();
}
private static T createProxy(final T obj) {
final InvocationHandler handler = new InvocationHandler() {
@Override
public Object invoke(Object proxy, Method method, Object[] args)
throws Throwable {
return method.invoke(obj, args);
}
};
//實(shí)現(xiàn)接口代理，Demo1報(bào)錯(cuò)，Demo2成功
//java.lang.ClassCastException: $Proxy1 cannot be cast to
//example.Test$Serializable
return (T) Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj
.getClass().getInterfaces(), handler);
} 可以看出這樣這樣設(shè)計(jì)是有道理的，因此，這并不是一個(gè)錯(cuò)誤，很可能是作者Josh Bloch為了便于實(shí)現(xiàn)代理而精心設(shè)計(jì)的。
參考與：開(kāi)發(fā)collection 的作者Josh說(shuō)
? ??2)RandomAccess接口，這是一個(gè)標(biāo)記接口，一般此標(biāo)記接口用于 List 實(shí)現(xiàn)，以表明它們支持快速（通常是恒定時(shí)間）的隨機(jī)訪(fǎng)問(wèn)，該接口的主要目的是允許通用算法改變其行為，以便在應(yīng)用于隨機(jī)或順序訪(fǎng)問(wèn)列表時(shí)提供良好的性能，實(shí)現(xiàn)了該接口的話(huà)使用普通的for循環(huán)來(lái)遍歷，性能更高，而沒(méi)有實(shí)現(xiàn)該接口的話(huà)，使用Iterator來(lái)迭代，這樣性能更高，例如linkedList。所以這個(gè)標(biāo)記性只是為了讓我們知道我們用什么樣的方式去獲取數(shù)據(jù)性能更好
? ??3)Cloneable接口，可以使用Object.Clone()方法。
? ??4)Serializable接口，序列化接口，表明該類(lèi)可以被序列化，什么是序列化？簡(jiǎn)單的說(shuō)，就是能夠從類(lèi)變成字節(jié)流傳輸，反序列化，就是從字節(jié)流變成原來(lái)的類(lèi)
?? ??1)add(E)；//默認(rèn)直接在末尾添加元素
/**
* 新增元素
*/
public boolean add(E e) {
//賦值初始長(zhǎng)度 或者擴(kuò)容,新增元素，當(dāng)前實(shí)際size+1的長(zhǎng)度
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素
elementData[size++] = e;
return true;
}
/**
* 確保elemenData數(shù)組有合適的大小
* 如果元素為空，則復(fù)制長(zhǎng)度默認(rèn)為10 或者更大
* @author jiaxiaoxian
* @date 2019年2月12日
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {//如果數(shù)組為空，則從size+1的值和默認(rèn)值10中取最大的
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 確保elemenData數(shù)組有合適的大小
* @author jiaxiaoxian
* @date 2019年2月12日
* 如果長(zhǎng)度大于元素長(zhǎng)度則擴(kuò)容
*/
private void ensureExplicitCapacity(int minCapacity) {
//記錄修改次數(shù)，迭代中不一致會(huì)觸發(fā)fail-fast機(jī)制,因此在遍歷中刪除元素的正確做法應(yīng)該是使用Iterator.remove()
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity); //擴(kuò)容
}
/**
* 擴(kuò)容
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 舊容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為舊容量的1.5倍
if (newCapacity - minCapacity < 0) // 新容量小于參數(shù)指定容量，修改新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
newCapacity = hugeCapacity(minCapacity); // 指定新容量
// minCapacity is usually close to size, so this is a win: 拷貝擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
//如果小于0 就報(bào)錯(cuò)，如果大于最大值 則取最大值
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)add(int index, E element)；//給指定下標(biāo)，添加元素
/**
* 給指定下標(biāo)，添加元素
*/
public void add(int index, E element) {
//判斷下標(biāo)是否越界
rangeCheckForAdd(index);
//賦值初始長(zhǎng)度 或者擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
//將源數(shù)組中從index位置開(kāi)始后的size-index個(gè)元素統(tǒng)一后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//賦值
elementData[index] = element;
size++;
}
/**
* 判斷下標(biāo)是否越界
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* src:源數(shù)組
* srcPos:源數(shù)組要復(fù)制的起始位置
* dest:目的數(shù)組
* destPos:目的數(shù)組放置的起始位置
* length:復(fù)制的長(zhǎng)度
* 注意：src 和 dest都必須是同類(lèi)型或者可以進(jìn)行轉(zhuǎn)換類(lèi)型的數(shù)組
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);?? ??3)addAll(Collection c)；//添加Collection類(lèi)型元素
/**
* 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部
*/
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//將數(shù)組a[0,...,numNew-1]復(fù)制到數(shù)組elementData[size,...,size+numNew-1]
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}?? ??4)addAll(int index, Collection c)；//指定位置，添加Collection類(lèi)型元素
/**
* 從指定的位置開(kāi)始，將指定collection中的所有元素插入到此列表中，新元素的順序?yàn)橹付╟ollection的迭代器所返回的元素順序
*/
public boolean addAll(int index, Collection c) {
//判斷下標(biāo)是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
//先將數(shù)組elementData[index,...,index+numMoved-1]復(fù)制到elementData[index+numMoved,...,index+2*numMoved-1]
//即，將源數(shù)組中從index位置開(kāi)始的后numMoved個(gè)元素統(tǒng)一后移numNew位
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}總結(jié)：
?正常情況下會(huì)擴(kuò)容1.5倍，特殊情況下（新擴(kuò)展數(shù)組大小已經(jīng)達(dá)到了最大值）則只取最大值。
?
?? ??1)remove(int index); //根據(jù)指定下標(biāo) 刪除元素?? ??
/**
* 根據(jù)指定下標(biāo) 刪除元素
*/
public E remove(int index) {
//判斷索引是否越界
rangeCheck(index);
modCount++;
//獲取舊元素
E oldValue = elementData(index);
//將數(shù)組elementData中index位置之后的所有元素向前移一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//將原數(shù)組最后一個(gè)位置置為null，由GC清理
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} ? ??? ??2)remove(Object o); //根據(jù)指定元素 刪除元素?
/**
* 移除ArrayList中首次出現(xiàn)的指定元素(如果存在)，ArrayList中允許存放重復(fù)的元素
*/
public boolean remove(Object o) {
// 由于ArrayList中允許存放null，因此下面通過(guò)兩種情況來(lái)分別處理。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//私有的移除方法，跳過(guò)index參數(shù)的邊界檢查以及不返回任何值
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}?
/*
* 根據(jù)下標(biāo)快速刪除元素
*/
private void fastRemove(int index) {
modCount++;
//將數(shù)組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
}
/**
* 清空ArrayList，將全部的元素設(shè)為null，等待垃圾回收將這個(gè)給回收掉，所以叫clear
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}?
?? ??3)removeAll(Collection c); //刪除包含在指定容器c中的所有元素?
/**
* 刪除ArrayList中包含在指定容器c中的所有元素
*/
public boolean removeAll(Collection c) {
//檢查指定的對(duì)象c是否為空
Objects.requireNonNull(c);
return batchRemove(c, false);
}
/**
* 刪除全部
* @author jiaxiaoxian
* @date 2019年2月12日
*/
private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; //讀寫(xiě)雙指針
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) //判斷指定容器c中是否含有elementData[r]元素
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;
}?? ??4)removeIf(Predicate filter); //按照一定規(guī)則過(guò)濾(刪除)集合中的元素?
/**
* 按照一定規(guī)則過(guò)濾(刪除)集合中的元素
* 如：idList.removeIf(id -> id == nul);
* 去掉 List idList 集合中id 為 null 的
* @param filter
* @return
*/
@Override
public boolean removeIf(Predicate filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}總結(jié)：
?remove函數(shù)用戶(hù)移除指定下標(biāo)的元素，此時(shí)會(huì)把指定下標(biāo)到數(shù)組末尾的元素向前移動(dòng)一個(gè)單位，并且會(huì)把數(shù)組最后一個(gè)元素設(shè)置為null，這樣是為了方便之后將整個(gè)數(shù)組不被使用時(shí)，會(huì)被GC，可以作為小的技巧使用。
/**
* 覆蓋指定下標(biāo)元素
*/
public E set(int index, E element) {
//判斷索引是否越界
rangeCheck(index);
//獲取舊元素
E oldValue = elementData(index);
//覆蓋為新元素
elementData[index] = element;
//返回舊元素
return oldValue;
}
/**
* 判斷下標(biāo)是否越界
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /**
* 返回指定索引的值
*/
public E get(int index) {
//判斷索引是否越界
rangeCheck(index);
return elementData(index);
}
/**
* @author jiaxiaoxian
* @date 2019年2月12日
* 返回下標(biāo)元素的 值
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}/**
* 查找下標(biāo)， 如果為null,直接和null比較，返回下標(biāo)
*/
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;
}
/**
* 查找最后出現(xiàn)的下標(biāo)，從大往下循環(huán)查找
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
} /**
* 復(fù)制，返回此ArrayList 的淺拷貝
*/
public Object clone() {
try {
ArrayList v = (ArrayList) super.clone();
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ù)據(jù)實(shí)際容量大小，刪除自動(dòng)增長(zhǎng)后冗余的容量
* 該方法用于回收多余的內(nèi)存。也就是說(shuō)一旦我們確定集合不在添加多余的元素之后，調(diào)用 trimToSize() 方法會(huì)將實(shí)現(xiàn)集合的數(shù)組大小剛好調(diào)整為集合元素的大小。
* 注意：該方法會(huì)花時(shí)間來(lái)復(fù)制數(shù)組元素，所以應(yīng)該在確定不會(huì)添加元素之后在調(diào)用
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}/**
* 實(shí)例化一個(gè)Itr對(duì)象，并返回
*/
public Iterator iterator() {
return new Itr();
}
/**
* 內(nèi)部類(lèi)，類(lèi)似Iterator，可以幫我們對(duì)List進(jìn)行遍歷，增刪改查等
*/
private class Itr implements Iterator {
int cursor; // index of next element to return 下一個(gè)元素
int lastRet = -1; // index of last element returned; -1 if no such 當(dāng)前元素
int expectedModCount = modCount; //modCount，就是為了判斷是否有多個(gè)線(xiàn)程訪(fǎng)問(wèn)修改
public boolean hasNext() {
return cursor != size;
}
@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];
}
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();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
} /**
* 這個(gè)類(lèi)繼承了內(nèi)部類(lèi)Itr
* 除了擁有上一個(gè)類(lèi)的功能，還增加了向前遍歷，增加元素，更改元素內(nèi)容等功能
*/
private class ListItr extends Itr implements ListIterator {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
} /**
* 雖然這個(gè)類(lèi)很長(zhǎng)，其實(shí)里面的大部分方法調(diào)用都是ArrayList中的
* ListIterator在這個(gè)類(lèi)中采用匿名內(nèi)部類(lèi)做了一點(diǎn)更改，不過(guò)也很類(lèi)似
* 畢竟這個(gè)類(lèi)就是根據(jù)ArrayList建一個(gè)子集類(lèi)，就不贅述了
*/
private class SubList extends AbstractList implements RandomAccess {
private final AbstractList parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
//實(shí)現(xiàn)fail-fast機(jī)制 (迭代中不允許操作增刪改)
checkForComodification();
// 舊值
E oldValue = ArrayList.this.elementData(offset + index);
// 賦新值
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
//實(shí)現(xiàn)fail-fast機(jī)制 (迭代中不允許操作增刪改)
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator iterator() {
return listIterator();
}
public ListIterator listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
/**
* 實(shí)現(xiàn)fail-fast機(jī)制
* 線(xiàn)程不安全 迭代中不允許修改
* @author jiaxiaoxian
* @date 2019年2月12日
*/
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator spliterator() {
checkForComodification();
return new ArrayListSpliterator(ArrayList.this, offset,
offset + this.size, this.modCount);
}
} /**
* @since 1.8
* 實(shí)例化一個(gè)ArrayListSpliterator對(duì)象，并返回
*/
@Override
public Spliterator spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/**
* Index-based split-by-two, lazily initialized Spliterator
* 并行迭代
* 基于索引的二分裂，懶惰初始化的Spliterator
* */
static final class ArrayListSpliterator implements Spliterator {
private final ArrayList list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList 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 lst;
if ((hi = fence) < 0) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
public ArrayListSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator(list, lo, index = mid,
expectedModCount);
}
public boolean tryAdvance(Consumer action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
public long estimateSize() {
return (long) (getFence() - index);
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
} 1）ArrayList可以存放null，本質(zhì)是Object[]類(lèi)型的數(shù)組。
2）ArrayList區(qū)別于數(shù)組的地方在于能夠自動(dòng)擴(kuò)展大小，其中關(guān)鍵的方法就是gorw()方法。
3）ArrayList由于本質(zhì)是數(shù)組，所以它在數(shù)據(jù)的查詢(xún)方面會(huì)很快，而在插入刪除這些方面，性能下降很多，
有移動(dòng)很多數(shù)據(jù)才能達(dá)到應(yīng)有的效果，而LinkedList則相反。
4）ArrayList實(shí)現(xiàn)了RandomAccess，所以在遍歷它的時(shí)候推薦使用for循環(huán)。
5）初始化數(shù)組時(shí)推薦給初始長(zhǎng)度，反復(fù)擴(kuò)容會(huì)增加時(shí)耗，影響性能效率。
6) Arrays工具類(lèi)用來(lái)處理數(shù)組的工具類(lèi)，Arrays.asList()方法返回的 ArrayList 數(shù)組是一個(gè)定長(zhǎng)列表，
7) 我們只能對(duì)其進(jìn)行查看或者修改，但是不能進(jìn)行添加或者刪除操作，不能執(zhí)行影響長(zhǎng)度的操作，
8) 因?yàn)榇薃rrayList是Arrays中內(nèi)部靜態(tài)類(lèi)，只實(shí)現(xiàn)了部分查看修改方法，添加和刪除方法是
9) 繼承AbstractList父類(lèi)的空方法，此ArrayList非彼ArrayList。
