collection框架的接口继承树（图片来自网络）
ArrayList（图片来自网络）
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实现类
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.)
/**
* 默认数组的初始化容量
*/
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);//这句执行后如果超过int的最大值那么newCapacity会是一个负数，这个需要了解一下数字二进制的加减原理。
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用来干嘛的？
- 记录内部修改次数
- 迭代器（Iterator）每调用一次next()函数都会调用checkForComodification方法判断一次，此方法用来判断创建迭代对象的时候List的modCount与现在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 创建对象时获取的modCount值
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
ArrayList 在循环中删除会出现的问题
for循环：
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);
}
}
//打印结果
1
2
3
4
5
这时候会发现连续两个3会跳过一个。原因就是在删除一个元素的时候，list元素会移位，去补齐被删除的位置，这时候，i++了就会跳过原来被删除的位置。
Iterator
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
if (value == 3) {
iter.remove();
}
}
//打印结果
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); //调用ArrayList的删除方法删除上一次返回的元素
cursor = lastRet; //下一个元素的下标赋值为当前被删除的下标
lastRet = -1; //
expectedModCount = modCount; //为了保证不抛异常，更新Itr类的expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
根据上述代码，next() 方法会先把cursor的值赋值给下标i，并返回下标为i的元素，并会，将cursor + 1 操作， lastRet 被赋值为当前被删除的元素的下标。
在remove()中 主要删除逻辑交给了ArrayList的remove()方法，删除过程cursor被赋值为lastRet（ArrayList删除后会把被删除的位置补齐，保证下一次访问不会漏掉）， lastRet被赋值为 -1 （代表上一次返回的元素已经被删除的标记）
foreach:
for (Integer i : list) {
if (i == 3) {
list.remove(3);
}
}
//程序会出错java.util.ConcurrentModificationException
这里就很精彩了，调用foreach,程序会执行两条语句分别是：
Itr.hasNext();
Itr.next();
但是在删除的时候却是list.remove();
这会导致modCount 和 expectedModCount不一致了
下一次next()的时候 执行到 checkForComodification()就会出错啦~
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
