collection框架的接口繼承樹（圖片來自網(wǎng)絡(luò)）
ArrayList（圖片來自網(wǎng)絡(luò)）
Collection 接口
代碼注釋說明：
The root interface in the collection hierarchy. A collection
represents a group of objects, known as its elements. Some
collections allow duplicate elements and others do not. Some are ordered
and others unordered. The JDK does not provide any direct
implementations of this interface: it provides implementations of more
specific subinterfaces like Set and List. This interface
is typically used to pass collections around and manipulate them where
maximum generality is desired.
接口定義的方法
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter)
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Stream<E> stream()
default Stream<E> parallelStream()
List接口
An ordered collection (also known as a sequence). The user of this
interface has precise control over where in the list each element is
inserted. The user can access elements by their integer index (position in
the list), and search for elements in the list
ArrayList實現(xiàn)類
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.)
/**
* 默認數(shù)組的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 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 = {};
/**
* 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簡化嵌套類訪問的非私有入口
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* 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;
}
/**
* 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;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code（對溢出進行考慮的代碼）
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 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);//這句執(zhí)行后如果超過int的最大值那么newCapacity會是一個負數(shù)懒叛，這個需要了解一下數(shù)字二進制的加減原理衫画。
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;
}
/**
* 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);
}
/**
* 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));
}
modCount用來干嘛的掐松？
- 記錄內(nèi)部修改次數(shù)
- 迭代器（Iterator）每調(diào)用一次next()函數(shù)都會調(diào)用checkForComodification方法判斷一次，此方法用來判斷創(chuàng)建迭代對象的時候List的modCount與現(xiàn)在List的modCount是否一樣鸣驱，不一樣的話就報ConcurrentModificationException異常，這就是所謂的fail-fast策略圆仔，快速失敗機制勒奇。
迭代器遍歷元素
ArrayList的iterator() 方法
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
//expectedModCount 創(chuàng)建對象時獲取的modCount值
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
ArrayList 在循環(huán)中刪除會出現(xiàn)的問題
for循環(huán)：
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(3);
list.add(4);
list.add(5);
Integer value = null;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 3) {
list.remove(3);
}
}
//打印結(jié)果
1
2
3
4
5
這時候會發(fā)現(xiàn)連續(xù)兩個3會跳過一個。原因就是在刪除一個元素的時候濒募，list元素會移位鞭盟，去補齊被刪除的位置，這時候瑰剃，i++了就會跳過原來被刪除的位置齿诉。
Iterator
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
if (value == 3) {
iter.remove();
}
}
//打印結(jié)果
1
2
4
5
// cursor 指向當前元素的下一個元素的下標 size list的大小
public boolean hasNext() {
return cursor != size;
}
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; //cursor 往后移一位
return (E) elementData[lastRet = i]; //返回當前元素，并將lastRet 賦值為當前返回元素下標
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); //調(diào)用ArrayList的刪除方法刪除上一次返回的元素
cursor = lastRet; //下一個元素的下標賦值為當前被刪除的下標
lastRet = -1; //
expectedModCount = modCount; //為了保證不拋異常晌姚，更新Itr類的expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
根據(jù)上述代碼鹃两，next() 方法會先把cursor的值賦值給下標i，并返回下標為i的元素舀凛，并會俊扳，將cursor + 1 操作， lastRet 被賦值為當前被刪除的元素的下標猛遍。
在remove()中 主要刪除邏輯交給了ArrayList的remove()方法馋记，刪除過程cursor被賦值為lastRet（ArrayList刪除后會把被刪除的位置補齊，保證下一次訪問不會漏掉）懊烤， lastRet被賦值為 -1 （代表上一次返回的元素已經(jīng)被刪除的標記）
foreach:
for (Integer i : list) {
if (i == 3) {
list.remove(3);
}
}
//程序會出錯java.util.ConcurrentModificationException
這里就很精彩了梯醒，調(diào)用foreach,程序會執(zhí)行兩條語句分別是：
Itr.hasNext();
Itr.next();
但是在刪除的時候卻是list.remove();
這會導致modCount 和 expectedModCount不一致了
下一次next()的時候 執(zhí)行到 checkForComodification()就會出錯啦~
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
