在面試中經(jīng)常被問到JDK源碼的問題，基于大學(xué)時期對數(shù)據(jù)結(jié)構(gòu)和算法的掌握，雖然能夠答出基本實(shí)現(xiàn)，但是總給人一種一知半解的印象。于是內(nèi)心斟酌了一下，考慮到徹底的研究JDK內(nèi)部工具類的實(shí)現(xiàn)對自己的編碼風(fēng)格和今后工作中的使用會更有幫助，再者把自己的理解寫成博客，既能鞏固知識點(diǎn)，也能將分析過程分享出來，供所有學(xué)習(xí)路上的朋友一同探討。
所使用的JDK版本
JDK8版本
注釋
java.util
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
是List接口的其中一種實(shí)現(xiàn)，具體就是通過可變長度數(shù)組。實(shí)現(xiàn)了list所有可選操作，允許包括null的所有元素。除了實(shí)現(xiàn)了List接口，該類提供了對存儲元素的數(shù)組的大小進(jìn)行操作的方法。
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
size, isEmpty, get, set, iterator, and listIterator操作可以在常數(shù)時間內(nèi)完成，add操作可以在amortized constant time時間內(nèi)完成，大概可以理解為均攤常數(shù)時間，如某一種操作會執(zhí)行100w次，其中某幾次執(zhí)行時間會比較長，但是每次執(zhí)行平均下來還是常數(shù)時間的。所以add n個元素是O(n)復(fù)雜度。其他操作的執(zhí)行時間是線性相關(guān)的。與LinkedList實(shí)現(xiàn)相比，具有較低的常數(shù)因子。至于什么是常數(shù)因子，谷歌了一下，可以看看這個解釋，不依賴于輸入?yún)?shù)的因子被稱為常數(shù)因子，如復(fù)雜度6n，6就是常數(shù)因子。
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
每個ArrayList實(shí)例都有一個可容納容量capacity，capacity值即用于存放元素的數(shù)組長度。capacity值始終大于等于list.size()。當(dāng)往ArrayList中添加元素時，其容量會自動擴(kuò)容。擴(kuò)容的具體策略不是特定的，但是策略始終保證add一個元素的時間開銷是均攤常數(shù)時間。
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new ArrayList(...));
應(yīng)用通過在add大量的元素前進(jìn)行ensureCapacity 操作，自動增加ArrayList 實(shí)例的容量，執(zhí)行ensureCapacity 操作有助于減少增量重新分配的次數(shù)。值得注意的是，這種實(shí)現(xiàn)不是同步的。如果有多個線程同時訪問ArrayList實(shí)例，并且其中有一個線程操作從結(jié)構(gòu)上改變了list，它必須在操作外部做好同步。（任何的對ArrayList增加或者刪除元素的操作，或顯式改變ArrayList內(nèi)部數(shù)組大小，都是引起ArrayList結(jié)構(gòu)性改變的操作，單單對元素設(shè)值不屬于此類操作）。通?？梢酝ㄟ^對包裹list的對象進(jìn)行同步，或者可以使用Collections.synchronizedList方法來對list同步，如List list = Collections.synchronizedList(new ArrayList(...));
The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
迭代器iterator具有fail-fast機(jī)制，即當(dāng)iterator創(chuàng)建之后的任意時刻，一旦發(fā)現(xiàn)某些操作（除了iterator自己的刪除和添加方法）使ArrayList結(jié)構(gòu)上發(fā)生了改變，iterator都會拋出ConcurrentModificationException異常。
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
當(dāng)出現(xiàn)沒有經(jīng)過同步的并發(fā)修改時，iterator的fail-fast行為不能被完全保證。
實(shí)現(xiàn)
靜態(tài)變量
- serialVersionUID：Java的序列化機(jī)制是通過判斷類的serialVersionUID來驗(yàn)證版本一致性的。序列化操作的時候系統(tǒng)會把當(dāng)前類的serialVersionUID寫入到序列化文件中，當(dāng)反序列化時系統(tǒng)會去檢測文件中的serialVersionUID，判斷它是否與當(dāng)前類的serialVersionUID一致，如果一致就說明序列化類的版本與當(dāng)前類版本是一樣的，可以反序列化成功，否則失敗。
- int DEFAULT_CAPACITY = 10：默認(rèn)的數(shù)組容量，即數(shù)組長度
- Object[] EMPTY_ELEMENTDATA = {}：所有空的ArrayList共享同一個空數(shù)組
- Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}：默認(rèn)構(gòu)造的空數(shù)組，和EMPTY_ELEMENTDATA區(qū)分開是為了知道在添加元素時，我們該把數(shù)組擴(kuò)容到多大。
私有變量
- transient Object[] elementData：ArrayList中元素都存放在這個緩存當(dāng)中，數(shù)組長度即ArrayList的容量。當(dāng)我們往ArrayList添加一個元素時，如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，則elementData自動擴(kuò)容到DEFAULT_CAPACITY。
- int size：ArrayList實(shí)際存放的元素數(shù)量
構(gòu)造函數(shù)
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
ArrayList(int initialCapacity)指定數(shù)組的初始容量大??；ArrayList()構(gòu)造一個默認(rèn)空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA，以便于在第一次添加元素時擴(kuò)容；ArrayList(Collection<? extends E> c)通過傳入一個Collection來構(gòu)造ArrayList，元素順序是由Collection的iterator決定的。
方法
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
將數(shù)組容量trim到當(dāng)前l(fā)ist所實(shí)際包含元素的數(shù)量（size）以優(yōu)化內(nèi)存占用，包含判斷空list的操作，用Arrays.copyOf將原數(shù)組內(nèi)容拷貝到一個長度為size的新數(shù)組。
modCount是AbstractList中的一個變量，同于統(tǒng)計(jì)ArrayList發(fā)生結(jié)構(gòu)性改變（structurally modified）的次數(shù)。如果該值發(fā)生了改變，可以作為iterator拋出ConcurrentModificationException的依據(jù)。
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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) {
ensureExplicitCapacity(minCapacity);
}
}
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));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
ensureCapacity(int minCapacity)和ensureCapacityInternal(int minCapacity)都是用來擴(kuò)容的，保證數(shù)組可以容納minCapacity個元素，最終都會調(diào)用ensureExplicitCapacity(int minCapacity)，如果參數(shù)指定的minCapacity大于當(dāng)前elementData的長度，則進(jìn)行擴(kuò)容操作。
/**
* 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)
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) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
grow(int minCapacity)計(jì)算的新數(shù)組長度為MAX(oldCapacity*1.5, minCapacity)，即原數(shù)組長度的1.5和參數(shù)指定的minCapacity比較取較大值，再調(diào)用Arrays.copyOf將原數(shù)組內(nèi)容拷貝到新數(shù)組。
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
就是直接判斷size值，很容易理解
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;
}
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;
}
indexOf和lastIndexOf很好理解，順序遍歷和逆序遍歷elementData，對null有特殊判斷邏輯。contains方法內(nèi)部用indexOf(o) >= 0實(shí)現(xiàn)，復(fù)雜度為O(n)。
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
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);
}
}
淺拷貝。
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;
}
toArray()用Arrays.copyOf將原數(shù)組內(nèi)容拷貝到一個長度為size的新數(shù)組并返回。所以對新數(shù)組的任何操作不會影響到原ArrayList的內(nèi)容。
toArray(T[] a) 判斷如果入?yún)?shù)組a的長度小于list長度，構(gòu)造一個長度為size的新數(shù)組并返回。如果入?yún)?shù)組a的長度大于list長度，則調(diào)用System.arraycopy拷貝元素，在數(shù)組a有效部分的最后附加一個元素null以表示結(jié)束。
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
都是根據(jù)下標(biāo)直接對elementData數(shù)組元素進(jìn)行操作。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
add(E e)首先調(diào)用ensureCapacityInternal保證elementData數(shù)組可以容納size + 1個元素，把e放在數(shù)組最后位置，更新size大小。
add(int index, E element)通過調(diào)用System.arraycopy先把elementData數(shù)組中index及其右側(cè)元素都右移一個位置，再將element放置在index位置，更新size大小。
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;
}
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;
}
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
}
remove(int index)通過調(diào)用System.arraycopy將elementData數(shù)組中index+1及其右側(cè)元素都左移一個位置，然后對elementData最后一個位置賦值為null以便于GC，這一步防止了內(nèi)存泄漏。
remove(Object o)刪除數(shù)組中第一個出現(xiàn)的o.equals(e)的元素，實(shí)際刪除操作是調(diào)用了fastRemove(int index) 方法，該方法沒有做rangeCheck并且不會返回被刪除元素。
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
對elementData的每個元素賦值null，以便于GC。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll(Collection<? extends E> c)和addAll(int index, Collection<? extends E> c)都是通過System.arraycopy將Collection添加到elementData末尾。
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
通過調(diào)用System.arraycopy將toIndex及其右側(cè)的元素左移numMoved個位置。并將elementData數(shù)組中newSize位置右側(cè)的元素全都賦值為null以便于GC
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
檢查數(shù)組越界
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
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;
}
removeAll(Collection<?> c)刪除ArrayList中所有的Collection中包含的元素，retainAll(Collection<?> c)僅保留Collection中包含的元素。batchRemove(Collection<?> c, boolean complement)用兩個下標(biāo)w（記錄新數(shù)組的當(dāng)前位置）和r（記錄原數(shù)組的當(dāng)前位置）對elementData進(jìn)行對元素位置的移動。如果出現(xiàn)異常導(dǎo)致r沒有遍歷到elementData的結(jié)尾，則保留出現(xiàn)異常的位置后面的所有元素，并將這些元素拷貝到新的位置。把elementData新數(shù)組中剩余元素賦值為null，以便于GC。
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();
}
}
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
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
}
}
}
讀寫對象操作
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public Iterator<E> iterator() {
return new Itr();
}
返回迭代器
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
subList(int fromIndex, int toIndex)返回list的一個視圖，對subList的非結(jié)構(gòu)性改變操作（non-structural
changes）會作用到list上，反之亦然。如果原list發(fā)生了結(jié)構(gòu)性改變，則subList返回的內(nèi)容是未被定義的。
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
函數(shù)式編程風(fēng)格，引入forEach(Consumer<? super E> action)方法。構(gòu)造實(shí)例實(shí)現(xiàn)Consumer的accept方法，傳給forEach，在forEach內(nèi)部會依次將elementData中的元素應(yīng)用于accept方法。
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
返回ArrayListSpliterator
public boolean removeIf(Predicate<? super E> 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;
}
函數(shù)式編程風(fēng)格，參數(shù)傳入一個實(shí)現(xiàn)了Predicate的實(shí)例，通過實(shí)例的test方法判斷是否要刪除ArrayList中的一個或者多個元素。具體實(shí)現(xiàn)是，把滿足test條件filter.test(element)的元素的位置放入一個BitSet，再通過移動元素的方式構(gòu)造新的數(shù)組。
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
函數(shù)式編程風(fēng)格，參數(shù)傳入一個實(shí)現(xiàn)了UnaryOperator的實(shí)例，對elementData的每個位置的元素應(yīng)用實(shí)例的apply方法，將apply方法返回的新值覆蓋對應(yīng)位置的原值。
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
排序，實(shí)際調(diào)用的是數(shù)組排序Arrays.sort((E[]) elementData, 0, size, c);
內(nèi)部類
Itr和ListItr
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
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<? super E> 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();
}
}
。。。
private class ListItr extends Itr implements ListIterator<E> {
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();
}
}
}
SubList
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> 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) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
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<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> 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<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
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<? super E> 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<E> 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;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
ArrayListSpliterator
···
static final class ArrayListSpliterator<E> implements Spliterator<E> {
/*
* If ArrayLists were immutable, or structurally immutable (no
* adds, removes, etc), we could implement their spliterators
* with Arrays.spliterator. Instead we detect as much
* interference during traversal as practical without
* sacrificing much performance. We rely primarily on
* modCounts. These are not guaranteed to detect concurrency
* violations, and are sometimes overly conservative about
* within-thread interference, but detect enough problems to
* be worthwhile in practice. To carry this out, we (1) lazily
* initialize fence and expectedModCount until the latest
* point that we need to commit to the state we are checking
* against; thus improving precision. (This doesn't apply to
* SubLists, that create spliterators with current non-lazy
* values). (2) We perform only a single
* ConcurrentModificationException check at the end of forEach
* (the most performance-sensitive method). When using forEach
* (as opposed to iterators), we can normally only detect
* interference after actions, not before. Further
* CME-triggering checks apply to all other possible
* violations of assumptions for example null or too-small
* elementData array given its size(), that could only have
* occurred due to interference. This allows the inner loop
* of forEach to run without any further checks, and
* simplifies lambda-resolution. While this does entail a
* number of checks, note that in the common case of
* list.stream().forEach(a), no checks or other computation
* occur anywhere other than inside forEach itself. The other
* less-often-used methods cannot take advantage of most of
* these streamlinings.
*/
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
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) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
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) {
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<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> 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;
}
}
···
相關(guān)
List接口分析
