Java集合系列-ArrayList源碼分析

文章目錄

• Java集合系列-ArrayList源碼分析
• 前言
• 一、為什么想去分析ArrayList源碼？
• 二、源碼分析
• • 1.宏觀上分析List
  • 2.方法匯總
• 三、ArrayList基本說明
• 總結(jié)

---

前言

一、為什么想去分析ArrayList源碼？

大家都懂，這個很重要
備注: 源碼分析系列全部基于jdk8

二、源碼分析

1.宏觀上分析List

代碼如下（示例）：

public interface List<E> extends Collection<E>

可以看到list其實是一個接口，繼承與Collection.

2.方法匯總

1. 獲取list的大小，最大為Integer.MAX_VALUE個元素：

int size();

2. 判斷集合是否有元素

boolean isEmpty(); //判斷集合是否有元素

3. 判斷一個集合是否包含某一個元素，可能出現(xiàn)。ClassCastException和NullPointerException異常

boolean contains(Object o);

4. 返回一個迭代器

Iterator<E> iterator();

5. 轉(zhuǎn)換為一個對象數(shù)組

Object[] toArray();

6. 集合轉(zhuǎn)換為一個數(shù)組，元素類型根據(jù)泛型獲得

<T> T[] toArray(T[] a);

基本使用方法

import java.util.ArrayList; import java.util.Arrays; import java.util.List;public class Demo {public static void main(String[] args) {List<Integer> list = new ArrayList<Integer>();list.add(1);list.add(2);Integer[] array = list.toArray(new Integer[0]);Arrays.stream(array).forEach(System.out::println);} }

這里的list.toArray(new Integer[0])和list.toArray()是一樣的

7. 向集合中添加一個元素

boolean add(E e)

8. 移除集合中的一個元素，移除的是第一個出現(xiàn)的元素

boolean remove(Object o);

9. 是否包含一個集合

boolean containsAll(Collection<?> c);

10. 向list集合中添加一個集合

boolean addAll(Collection<? extends E> c);

11. 在指定位置插入集合

boolean addAll(int index, Collection<? extends E> c);

12. 移除指定的所有集合

boolean removeAll(Collection<?> c);

13. 移除指定的所有集合

boolean retainAll(Collection<?> c);

listA.retainAll(listB);保留 A中包含在集合B中的元素或者說移除A中沒有在B中的元素
15. 用函數(shù)接口的返回結(jié)果替代原list中的值.

default void replaceAll(UnaryOperator<E> operator) {Objects.requireNonNull(operator);final ListIterator<E> li = this.listIterator();while (li.hasNext()) {li.set(operator.apply(li.next()));}}

參考: replaceAll較為詳細(xì)的解釋

16. 排序方法

default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}

參考sort的使用方法

17. 移除list的所有元素

void clear();

18. 判斷兩個list是否相等

In other words, two lists are defined to be equal if they contain the same elements in the same order.

boolean equals(Object o);

19. 獲取list的hash值

int hashCode();

20. 獲取指定位置的元素

E get(int index);

21. 設(shè)置指定位置的元素的值

E set(int index, E element);

22. 在指定位置添加值

E set(int index, E element);

23. 移除指定位置的元素

E remove(int index);

24. 獲取指定元素的索引

int indexOf(Object o);

25. 獲取元素最后一次出現(xiàn)的索引值

int lastIndexOf(Object o);

26. 移除指定位置的元素

E remove(int index);

27. 返回一個迭代器，可以雙向遍歷

ListIterator<E> listIterator();

參考listIterator的使用方法
29. 返回一個迭代器，可以雙向遍歷

ListIterator<E> listIterator(int index);

30. 獲取list的一個指定范圍的子集

List<E> subList(int fromIndex, int toIndex);

31. 移除指定位置的元素

default Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.ORDERED);}

參考spliterator的使用方法

---

三、ArrayList基本說明

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 c.)

• ArrayList是list接口的一種實現(xiàn)，是一個可變大小的數(shù)組
• 實現(xiàn)了list所有可選擇的操作，并且允許null元素的存在
• 除了實現(xiàn)list的接口，這個類提供了操作數(shù)組大小的方法，在內(nèi)部，可以利用這個數(shù)組來存儲list
• ArrayList和Vector是類似的，但是ArrayList是非同步(unsynchronized)的, 其實也就是說ArrayList是非線程安全的，Vector是線程安全的。

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、listIterator都是常數(shù)時間
• 方法add 運行是amortized constant time 分?jǐn)偝?shù)時間，也就是說，向數(shù)組中添加一個元素，時間復(fù)雜度為O(n)
• 所有其他的操作算法時間復(fù)雜度都是O(1)
• 與LinkedList相比較而言，list有更小的常數(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實例都有一個容量(capacity)
• 容量具體指的是用來存放列表中元素的數(shù)組的大小
• 隨著元素添加到ArrayList中，其容量是在不斷自動增加的
• 增加策略的詳細(xì)信息并沒有特別指定，除了增加一個元素到ArrayList需要amortized constant time

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.

• 在添加大量的元素到arrayList之前，是可以使用ensureCapacity來增加ArrayList的容量大小的
• 使用ensureCapacity可以減少需要重新分配內(nèi)存的數(shù)量

• 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.

• 需要注意的是ArrayList并不是線程安全的
• 在并發(fā)的場景下，如果至少有一個線程來修改list的結(jié)構(gòu)，那么我們需要外部保證必須同步(結(jié)構(gòu)性修改可以是add、delete或者調(diào)整backing array數(shù)組大小中的任意一個操作；僅僅只是設(shè)置list中一個元素的值不是結(jié)構(gòu)性的修改)
• 典型的實現(xiàn)是，用synchronize修飾某些包裹encapsulate了整個list的對象

If no such object exists, the list should be “wrapped” using the {@link Collections#synchronizedList Collections.synchronizedList} method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...));

• (承接上文)如果沒有一個encapsulate了這個list的對象存在，那么應(yīng)該使用Collections.synchronizedList，來防止對list意外的非同步訪問

The iterators returned by this class's {@link #iterator() iterator} and {@link #listIterator(int) 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 {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator will throw a {@link 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()和istIterator(int)方法是快速失敗的，并拋出ConcurrentModificationException: 如果這個list在創(chuàng)建了iterator以后，在任意時刻被結(jié)構(gòu)性修改，除了iterator自身調(diào)用remove和add方法
• 因此在并發(fā)修改的場景下，這個迭代器快速失敗而不是在未來一個不確定性的時間冒險專斷或者不確定性行為

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 {@code 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.

• 需要注意的是，一般說來，迭代器快速失敗的行為不能做出保證，因為它不可能在出現(xiàn)非同步并發(fā)修改時做出任何保證；基于最大努力，快速失敗的迭代器拋出ConcurrentModificationException異常
• 因此，寫一個基于這個異常來做修正的代碼是不正確的；迭代器快速失敗的行為應(yīng)該僅僅被用來檢測bug

---

# 四、ArrayList基本說明 public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• ArrayList繼承了抽象的list-AbstractList
• 實現(xiàn)了List、RandomAccess、Cloneable和java.io.Serializable 4個接口

/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;

• 默認(rèn)的初始化容器大小

/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};

• 共享的空數(shù)組實例，用來當(dāng)作空的實例，容器大小為0

/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• 共享的空數(shù)組實例，用作默認(rèn)大小的空實例，容器大小為10
• 與上面的EMPTY_ELEMENTDATA的區(qū)別在于當(dāng)?shù)谝粋€元素添加進去的時候，我們知道需要擴多大的容量

/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access

• 作為數(shù)組緩存，來存放ArrayList中的元素
• ArrayList數(shù)組容量的大小時這個緩存數(shù)組的長度
• 任何元素為DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList，在第一次添加元素時，會擴張為DEFAULT_CAPACITY

/*** The size of the ArrayList (the number of elements it contains).** @serial*/private int size;

• ArrayList中包含有元素的個數(shù)，注意與capacity的區(qū)別

/*** 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);}}

• 構(gòu)造器，構(gòu)造一個指定大小的ArrayList

/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

• 構(gòu)造器，構(gòu)造一個初始化容量大小為10的空ArrayList

/*** 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;}}

• 通過一個集合來構(gòu)造ArrayList
• 構(gòu)造器總結(jié): 三個構(gòu)造器，1)指定大小 2) 默認(rèn)大小 3）利用集合

/*** 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ù)是用來調(diào)整容器為當(dāng)前列表所包含的元素的個數(shù)(size)
• modCount，這個參數(shù)在講AbstractList內(nèi)部類迭代器的時候，具體講解，主要是用來記錄list被結(jié)構(gòu)性修改次數(shù)的

protected transient int modCount = 0;

• 另外就是elementData，在上面也講過，它是用來作為一個緩存，來存放ArrayList中的元素的

/*** 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);}}

• 用來增加當(dāng)前ArrayList實例的容量大小
• 確保能夠包含所指定的最小容量大小個數(shù)的元素

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

如果用來存放list的緩存數(shù)組的長度elementData.length小于所設(shè)定的最小容量minCapacity，那么就需要進行擴容

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));} private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity; }

• grow—擴容相關(guān)的代碼

/*** 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 codeint 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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

• MAX_ARRAY_SIZE 表述數(shù)組所允許分配的最大大小
• grow函數(shù)用來擴容elementData數(shù)組，來確保可以存放所設(shè)置的minCapacity個元素
• 這里擴容的原理:默認(rèn)是比原來的大小新增0.5倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  (1) 如果擴容以后的newCapacity比需要的minCapacity小，則直接將newCapacity修改為minCapacity;
  (2)如果擴容以后的newCapacity比需要的minCapacity大，并且比最大值MAX_ARRAY_SIZE都還要大，則需要調(diào)用hugeCapacity，比較minCapacity和MAX_ARRAY_SIZE的大小，如果minCapacity大于MAX_ARRAY_SIZE，則將newCapacity設(shè)置為Integer.MAX_VALUE，否則設(shè)置為MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8),那么這里為什么是MAX.VALUE-8,則是因為數(shù)組作為一個對象，需要一定的內(nèi)存存儲對象頭信息，對象頭信息最大占用內(nèi)存不可超過8字節(jié)。參考
  (3) 然后將舊數(shù)組拷貝到新數(shù)組 參考
  elementData = Arrays.copyOf(elementData, newCapacity);
• 關(guān)于這里為什么要調(diào)用ensureCapacity:當(dāng)我們已經(jīng)確定了要插入的對象的數(shù)目（并不是在創(chuàng)建ArrayList之前就知道有多少對象要插入的情況），就應(yīng)該首先調(diào)用ensureCapacity來一次性擴容到可以容得下要插入的對象個數(shù)，這樣就避免的多次進行數(shù)組拷貝的情況，提高了效率，算是優(yōu)化吧;當(dāng)然，我們在創(chuàng)建ArrayList之前就知道有多少對象要插入就使用有參構(gòu)造。參考

/*** Returns the number of elements in this list.** @return the number of elements in this list*/public int size() {return size;}

• 返回list中的元素個數(shù)

/*** Returns <tt>true</tt> if this list contains no elements.** @return <tt>true</tt> if this list contains no elements*/public boolean isEmpty() {return size == 0;}

• 判斷l(xiāng)ist中是否有元素

/*** Returns <tt>true</tt> if this list contains the specified element.* More formally, returns <tt>true</tt> if and only if this list contains* at least one element <tt>e</tt> such that* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.** @param o element whose presence in this list is to be tested* @return <tt>true</tt> if this list contains the specified element*/public boolean contains(Object o) {return indexOf(o) >= 0;}

• 判斷l(xiāng)ist中是否包含某個對象，這里我們在判斷一個list元素為自定義對象的時候，需要重寫equal和hashCode方法，這里才能判斷是否包含某個對象，下面的demo會返回false

public class Demo {public static void main(String[] args) {List<Student> list = new ArrayList<>();Student A = new Student();A.setName("A");A.setAge(1);Student B = new Student();B.setName("B");B.setAge(2);list.add(A);list.add(B);Student C = new Student();C.setName("A");C.setAge(1);System.out.println(list.contains(C));} } /*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.*/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;}

• 返回list中指定元素第一次出現(xiàn)時的位置，這個位置是在elementData這個數(shù)組中的位置，這里需要注意如果需要元素為null時的判斷

/*** Returns the index of the last occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the highest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.*/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;}

• 返回list中指定元素最后一次出現(xiàn)時的位置，這里需要注意如果需要元素為null時的判斷

/*** 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 Cloneablethrow new InternalError(e);}}

• 返回對當(dāng)前ArrayList實例的一個淺拷貝

/*** Returns an array containing all of the elements in this list* in proper sequence (from first to last element).** <p>The returned array will be "safe" in that no references to it are* maintained by this list. (In other words, this method must allocate* a new array). The caller is thus free to modify the returned array.** <p>This method acts as bridge between array-based and collection-based* APIs.** @return an array containing all of the elements in this list in* proper sequence*/public Object[] toArray() {return Arrays.copyOf(elementData, size);}

• 將list轉(zhuǎn)化為數(shù)組，這里的數(shù)組是重新分配的一個空間，不會和原來的list元素存在任何引用關(guān)系，因此調(diào)用者可以自由的修改數(shù)組中的元素

/*** Returns an array containing all of the elements in this list in proper* sequence (from first to last element); the runtime type of the returned* array is that of the specified array. If the list fits in the* specified array, it is returned therein. Otherwise, a new array is* allocated with the runtime type of the specified array and the size of* this list.** <p>If the list fits in the specified array with room to spare* (i.e., the array has more elements than the list), the element in* the array immediately following the end of the collection is set to* <tt>null</tt>. (This is useful in determining the length of the* list <i>only</i> if the caller knows that the list does not contain* any null elements.)** @param a the array into which the elements of the list are to* be stored, if it is big enough; otherwise, a new array of the* same runtime type is allocated for this purpose.* @return an array containing the elements of the list* @throws ArrayStoreException if the runtime type of the specified array* is not a supertype of the runtime type of every element in* this list* @throws NullPointerException if the specified array is null*/@SuppressWarnings("unchecked")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;}

• 和上面的方法類似

下面開始講元素操作部分

@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}

• 獲取指定位置index的元素

/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);}

• 判斷元素是否在指定范圍內(nèi)

/*** Checks if the given index is in range. If not, throws an appropriate* runtime exception. This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

• 設(shè)置指定位置元素的值

/*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}

• 向list中添加一個元素

/*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}

(1) 添加元素是添加在內(nèi)部數(shù)組的最后一個位置
(2) ensureCapacityInternal方法，add()方法的時候，會導(dǎo)致list發(fā)生結(jié)構(gòu)性的修改，然后需要將modCount進行+1操作

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity; }private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity); }

• 在指定位置添加元素的值

/*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/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++;}

(1) 檢查所要添加的位置是否在合理范圍

/*** A version of rangeCheck used by add and addAll.*/private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

(2) 調(diào)用ensureCapacityInternal(size + 1)，增加修改計數(shù)器modCount和判斷是否需要擴容
(3) 移動數(shù)組元素，將源數(shù)組src的從起始位置srcPos開始的元素 復(fù)制到目標(biāo)數(shù)組dest的從destPos開始長度為length的數(shù)組位置

public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

(4) 然后將element賦值到指定位置elementData[index] = element;，最后修改整個list的大小size++

• 移除指定位置的元素

/*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** @param index the index of the element to be removed* @return the element that was removed from the list* @throws IndexOutOfBoundsException {@inheritDoc}*/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 workreturn oldValue;}

(1) rangeCheck(index); 先檢查需要移除的位置index是否合理
(2) 修改標(biāo)志修改次數(shù)的參數(shù)值 modCount++
(3) 調(diào)整數(shù)組
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
(4) 將數(shù)組的最后一個位置置為null，方便gc;然后計算list的大小
(5) 返回所移除的元素

• 移除指定元素

/*** Removes the first occurrence of the specified element from this list,* if it is present. If the list does not contain the element, it is* unchanged. More formally, removes the element with the lowest index* <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists). Returns <tt>true</tt> if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return <tt>true</tt> if this list contained the specified element*/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 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}

(1) 快速移除 fastRemove，省去了邊界檢查

• 清空列表

/*** Removes all of the elements from this list. The list will* be empty after this call returns.*/public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}

• 添加集合到list的末尾，這個操作行為的結(jié)果是不確定的，如果要添加的集合在添加的過程中被修改

/*** Appends all of the elements in the specified collection to the end of* this list, in the order that they are returned by the* specified collection's Iterator. The behavior of this operation is* undefined if the specified collection is modified while the operation* is in progress. (This implies that the behavior of this call is* undefined if the specified collection is this list, and this* list is nonempty.)** @param c collection containing elements to be added to this list* @return <tt>true</tt> if this list changed as a result of the call* @throws NullPointerException if the specified collection is null*/public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

• 插入集合到指定位置

/*** Inserts all of the elements in the specified collection into this* list, starting at the specified position. Shifts the element* currently at that position (if any) and any subsequent elements to* the right (increases their indices). The new elements will appear* in the list in the order that they are returned by the* specified collection's iterator.** @param index index at which to insert the first element from the* specified collection* @param c collection containing elements to be added to this list* @return <tt>true</tt> if this list changed as a result of the call* @throws IndexOutOfBoundsException {@inheritDoc}* @throws NullPointerException if the specified collection is null*/public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountint 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;}

• 移除指定范圍(左閉右開)的元素

/*** Removes from this list all of the elements whose index is between* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.* Shifts any succeeding elements to the left (reduces their index).* This call shortens the list by {@code (toIndex - fromIndex)} elements.* (If {@code toIndex==fromIndex}, this operation has no effect.)** @throws IndexOutOfBoundsException if {@code fromIndex} or* {@code toIndex} is out of range* ({@code fromIndex < 0 ||* fromIndex >= size() ||* toIndex > size() ||* toIndex < fromIndex})*/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 workint newSize = size - (toIndex-fromIndex);for (int i = newSize; i < size; i++) {elementData[i] = null;}size = newSize;}

• 將集合C中存在與list中的元素移除走

/*** Removes from this list all of its elements that are contained in the* specified collection.** @param c collection containing elements to be removed from this list* @return {@code true} if this list changed as a result of the call* @throws ClassCastException if the class of an element of this list* is incompatible with the specified collection* (<a href="Collection.html#optional-restrictions">optional</a>)* @throws NullPointerException if this list contains a null element and the* specified collection does not permit null elements* (<a href="Collection.html#optional-restrictions">optional</a>),* or if the specified collection is null* @see Collection#contains(Object)*/public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}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 workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}

(1) 如果c.contains(elementData[r]) == false，也就是說當(dāng)前l(fā)ist中位于位置r的元素不在c中，那么就將r位置的元素放到當(dāng)前l(fā)ist的對應(yīng)位置為w的地方
(2) 上面的代碼 什么情況下會發(fā)生r != size的情況
(3) 另外這里的removeAll指的是把含在c中的元素從list中移除，而不是如果c中有一個元素不在list中，則不進行移除

• 將集合C中存在與list中的元素保留下來

/*** Retains only the elements in this list that are contained in the* specified collection. In other words, removes from this list all* of its elements that are not contained in the specified collection.** @param c collection containing elements to be retained in this list* @return {@code true} if this list changed as a result of the call* @throws ClassCastException if the class of an element of this list* is incompatible with the specified collection* (<a href="Collection.html#optional-restrictions">optional</a>)* @throws NullPointerException if this list contains a null element and the* specified collection does not permit null elements* (<a href="Collection.html#optional-restrictions">optional</a>),* or if the specified collection is null* @see Collection#contains(Object)*/public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}

• 序列化writeObject和反序列化readObject

/*** Save the state of the <tt>ArrayList</tt> instance to a stream (that* is, serialize it).** @serialData The length of the array backing the <tt>ArrayList</tt>* instance is emitted (int), followed by all of its elements* (each an <tt>Object</tt>) in the proper order.*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint 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 stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityint 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();}}}

迭代器------Itr

• 根據(jù)當(dāng)前的list返回一個迭代器Iterator

public Iterator<E> iterator() {return new Itr();}

• list的內(nèi)部類 迭代器Itr，是AbstractList的迭代器Itr的一個優(yōu)化版本

*** An optimized version of AbstractList.Itr*/private class Itr implements Iterator<E> {

• 核心變量
  cursor—下一個元素的索引值
  lastRet—上一次返回元素的索引值
  expectedModCount —期望被修改的次數(shù)

int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;

• 判斷迭代器是否還有更多的元素，下一個元素的索引cursor是否為list的大小size

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];}

(1) 檢查修改次數(shù) 期望修改的次數(shù)expectedModCount和實際修改次數(shù)是否相同

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}

(2) 判斷下一個元素的索引是否超過了list的大小size
(3) 將當(dāng)前l(fā)ist轉(zhuǎn)化為數(shù)組 Object[] elementData = ArrayList.this.elementData;
(4) 判斷下一個元素的索引值是否超過了當(dāng)前數(shù)組elementData的長度,這里為什么需要做這個判斷
(5) 修改cursor的指，指向當(dāng)前要返回元素的下一個元素的索引位置 cursor = i + 1;
(6) 返回當(dāng)前索引值 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();}}

移除上一個返回的元素以后:
(1) 下一個元素的索引值cursor為上一個返回元素的索引
(2) 上一個返回元素的索引為-1
(3) 修改期望修改值expectedModCount

• 為list中剩余的每一個元素執(zhí)行指定的操作

@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 trafficcursor = i;lastRet = i - 1;checkForComodification();}

(1) 先判斷當(dāng)前迭代器所指向下一個元素的索引是否超過了當(dāng)前l(fā)ist的大小size
(2) 先判斷當(dāng)前迭代器所指向下一個元素的索引是否超過了當(dāng)前緩存數(shù)組的長度length
(3) 然后為剩下的每一個元素都執(zhí)行consumer.accept((E) elementData[i++]);
(4) 更新參數(shù) cursor = I; lastRet = i - 1;

內(nèi)部類 ListItr

/*** An optimized version of AbstractList.ListItr*/private class ListItr extends Itr implements ListIterator<E> { /*** Returns a list iterator over the elements in this list (in proper* sequence), starting at the specified position in the list.* The specified index indicates the first element that would be* returned by an initial call to {@link ListIterator#next next}.* An initial call to {@link ListIterator#previous previous} would* return the element with the specified index minus one.** <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.** @throws IndexOutOfBoundsException {@inheritDoc}*/public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index);return new ListItr(index);}

• 返回一個從指定位置開始的list iterator
• 指定位置表明 第一個元素將是初次調(diào)用next方法返回的
• 初次調(diào)用previous方法會返回指定位置-1處的元素

/*** Returns a list iterator over the elements in this list (in proper* sequence).** <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.** @see #listIterator(int)*/public ListIterator<E> listIterator() {return new ListItr(0);}

• ListItr 繼承Itr， 實現(xiàn)接口ListIterator

接口ListIterator

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator’s current position in the list. A {@code ListIterator} has no current element; its cursor position always lies between the element that would be returned by a call to {@code previous()} and the element that would be returned by a call to {@code next()}.

• ListIterator是一個針對lists的迭代器，這個迭代器允許程序以不同的方向去遍歷list、在迭代的過程中修改list和獲取迭代器在list的當(dāng)前位置
• ListIterator 沒有當(dāng)前的元素
• ListIterator的cursor position總是處于調(diào)用者調(diào)用previous()所返回的值和調(diào)用者調(diào)用next()所返回的值之間

An iterator for a list of length {@code n} has {@code n+1} possible cursor positions, as illustrated by the carets ({@code ^}) below:

Element(0) Element(1) Element(2) … Element(n-1)
cursor positions: ^ ^ ^ ^ ^

• 一個作為長度為n的list的迭代器有n+1個可能的cusor位置

Note that the {@link #remove} and {@link #set(Object)} methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call to {@link #next} or {@link #previous()}.

• 注意remove和set方法并不是使用cursor position 而是使用 調(diào)用next或者previous方法返回的上一個元素lastRet
• ListItr構(gòu)造器

ListItr(int index) {super();cursor = index;}

• 利用ListItr反向遍歷list的時候，判斷是否有上一個元素

public boolean hasPrevious() {return cursor != 0; }

• 針對一系列調(diào)用next方法時，返回的元素的索引值

public int nextIndex() {return cursor;}

• 針對一系列調(diào)用previous方法時，返回的元素的索引值

public int previousIndex() {return cursor - 1;} }

• 獲取cursor所在位置的前面一個位置的值

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];}

• 設(shè)置上一個返回值的位置的值為元素e

public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}

• 在下一個元素的索引位置處設(shè)置值e

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();}} /*** Returns a view of the portion of this list between the specified* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If* {@code fromIndex} and {@code toIndex} are equal, the returned list is* empty.) The returned list is backed by this list, so non-structural* changes in the returned list are reflected in this list, and vice-versa.* The returned list supports all of the optional list operations.** <p>This method eliminates the need for explicit range operations (of* the sort that commonly exist for arrays). Any operation that expects* a list can be used as a range operation by passing a subList view* instead of a whole list. For example, the following idiom* removes a range of elements from a list:* <pre>* list.subList(from, to).clear();* </pre>* Similar idioms may be constructed for {@link #indexOf(Object)} and* {@link #lastIndexOf(Object)}, and all of the algorithms in the* {@link Collections} class can be applied to a subList.** <p>The semantics of the list returned by this method become undefined if* the backing list (i.e., this list) is <i>structurally modified</i> in* any way other than via the returned list. (Structural modifications are* those that change the size of this list, or otherwise perturb it in such* a fashion that iterations in progress may yield incorrect results.)** @throws IndexOutOfBoundsException {@inheritDoc}* @throws IllegalArgumentException {@inheritDoc}*/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方法將返回當(dāng)前l(fā)ist在指定范圍(左閉右開區(qū)間范圍)的list元素
• 如果區(qū)間范圍邊界值fromIndex和toIndex值相同，那么返回的list為空
• 這個返回的list是和原來的list是有關(guān)系的，返回list的結(jié)構(gòu)性改變會引起原list的結(jié)構(gòu)性改變，反過來也一樣。
• 返回來的這個list是SubList支持list的所有操作,因為繼承了AbstractList, 重寫了對應(yīng)的方法

內(nèi)部類 SubList

private class SubList extends AbstractList<E> implements RandomAccess

• SubList繼承了AbstractList，實現(xiàn)了 RandomAccess

• RandomAccess 表示list接口的實現(xiàn)類支持快速隨機訪問

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

• 內(nèi)部變量

private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;

• 構(gòu)造器

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;}

• 設(shè)置指定位置的元素為e

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;}

（1）與ArrayList的方法進行比較，多了modCount的比較和設(shè)置對應(yīng)的值時增加了偏移量

public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;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();}

• 返回可以前后遍歷list的迭代器，里面包含了ListItr相應(yīng)的方法，比如 next，previous

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 trafficlastRet = 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();}};}

• SubList類也包含了sublist方法

public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, offset, fromIndex, toIndex);}

• spliterator()方法，這里涉及到內(nèi)部類ArrayListSpliterator，后面會詳細(xì)講這個類的作用

public Spliterator<E> spliterator() {checkForComodification();return new ArrayListSpliterator<E>(ArrayList.this, offset,offset + this.size, this.modCount);}

至此，SubList的所有方法就講完了，現(xiàn)在來繼續(xù)講解ArrayList的剩余方法

• 為list中每一個元素執(zhí)行相同的操作

@Overridepublic 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();}}

• List item

/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* list.** <p>The {@code Spliterator} reports {@link Spliterator#SIZED},* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.* Overriding implementations should document the reporting of additional* characteristic values.** @return a {@code Spliterator} over the elements in this list* @since 1.8*/@Overridepublic Spliterator<E> spliterator() {return new ArrayListSpliterator<>(this, 0, -1, 0);}

內(nèi)部類 ArrayListSpliterator

/** Index-based split-by-two, lazily initialized Spliterator */static final class ArrayListSpliterator<E> implements Spliterator<E>

• 基于索引
• 一分為二
• 延遲初始化的可拆分的迭代器 參考
• 該對象可以使用trySplit進行迭代器拆分，每次拆分后的迭代器接近上一次的二分之一。
  這是官方對于大數(shù)據(jù)量數(shù)組多線程遍歷加工的一種趨勢性指引。參考

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/splitprivate int fence; // -1 until used; then one past last indexprivate int expectedModCount; // initialized when fence set

(1) index 當(dāng)前索引，在遍歷或者拆分的時候被修改
(2) fence 沒使用的時候默認(rèn)為-1，最后指向最后一個索引

• 構(gòu)造器

/** Create new spliterator covering the given range */ArrayListSpliterator(ArrayList<E> list, int origin, int fence,int expectedModCount) {this.list = list; // OK if null unless traversedthis.index = origin;this.fence = fence;this.expectedModCount = expectedModCount;}

• 初始化變量fence，在第一次使用的初始化fence到list的大小

private int getFence() { // initialize fence to size on first useint 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;}

• 拆分ArrayList

public ArrayListSpliterator<E> trySplit() {int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;return (lo >= mid) ? null : // divide range in half unless too smallnew ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);}

• 當(dāng)前元素執(zhí)行action

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;}

• 剩下的元素執(zhí)行相同的操作

public void forEachRemaining(Consumer<? super E> action) {int i, hi, mc; // hoist accesses and checks from loopArrayList<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;}elsemc = 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ī)則過濾集合中的元素

@Overridepublic 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 unmodifiedint 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 elementsfinal 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;}

• 用于將給定的操作內(nèi)容替換掉數(shù)組中每一個元素。

@Override@SuppressWarnings("unchecked")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++;}

• List 排序

@Override@SuppressWarnings("unchecked")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++;}

ArrayList的整體框架 參考

總結(jié)

總結(jié)

以上是生活随笔為你收集整理的Java集合Collection源码系列-ArrayList源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。