ArrayList详解
ArrayList详解
继承AbstractList
实现List
静态成员变量
private static final int DEFAULT_CAPACITY = 10;
默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};
用于空实例的共享空数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
用于默认大小空实例的共享空数组。我们将其与EMPTY_ELEMENTDATA区分开来，以便知道添加第一个元素的时候需要扩张多少。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
功能：分配数组的最大大小。 有些虚拟机在数组中保留一些头词。 尝试分配更大的数组可能会导致OutOfMemoryError: Requested array size exceeds VM limit
详述：Integer.MAX_VALUE = \(2^{31}-1\)
成员变量
transient Object[] elementData;
存储元素的数组。如果数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组，在添加第一个元素的时候，会扩张到DEFAULT_CAPACITY的大小
private int size;
ArrayList的大小。（包含的元素数量）
方法
public ArrayList(int initialCapacity)
功能：构造一个指定大小的空的数组
public ArrayList()
功能：构造一个初始大小为10的空的数组
public ArrayList(Collection<? extends E> c)
功能：构造包含指定集合元素的列表，按集合迭代器返回的顺序排列。
public void trimToSize()
功能：将这个ArrayList实例的容量调整为数组的当前大小（size大小）。应用程序可以使用这个操作最小化ArrayList实例的存储空间。
描述：该方法还会导致modCount++
public void ensureCapacity(int minCapacity)
功能：如果有必要，增加ArrayList的容量大小，以确保它能至少容纳minCapacity个元素。
详述：如果数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组，且minCapacity小于DEFAULT_CAPACITY则不会进行操作。
此处调用grow(minCapacity)实现容量增加。该操作会导致modCount++。modCount是继承自AbstractList的成员变量。
private Object[] grow(int minCapacity)
功能：增加容量，以确保它至少能容纳由minCapacity参数指定的元素数量。
详述：调用newCapacity(minCapacity)
private Object[] grow()
功能：容量至少扩大为size+1。
详述：调用grow(size+1)
private int newCapacity(int minCapacity)
功能：返回大于等于minCapacity的容量。如果可以，返回增加50%的当前容量。除非minCapacity大于MAX_ARRAY_SIZE，否则不会返回大于MAX_ARRAY_SIZE的容量
详述：newCapacity计算出原来1.5倍的容量大小。
如果newCapacity小于minCapacity。如果数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则返回DEFAULT_CAPACITY和minCapacity中的较大值。如果minCapacity小于0则抛出异常。其余情况返回minCapacity。
如果newCapacity大于minCapacity，则判断newCapacity是否大于MAX_ARRAY_SIZE。小于情况返回newCapacity，大于情况返回hugeCapacity(minCapacity)的结果
private static int hugeCapacity(int minCapacity)
详述：如果minCapacity小于0，抛出异常；如果minCapacity大于MAX_ARRAY_SIZE，返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE。
public int size() {return size;}
功能：返回列表中的元素个数
public boolean isEmpty() {return size == 0;}
返回true如果列表不包含任何元素。
public boolean contains(Object o) {return indexOf(o) >= 0;}
功能：返回true如果列表包含至少一个元素满足Objects.equals(o, e)。
详述：调用indexOf(o)进行查找
public int indexOf(Object o) {return indexOfRange(o, 0, size);}
功能：返回第一个出现的满足Objects.equals(o, e)的下标，没有则返回-1。
int indexOfRange(Object o, int start, int end)
功能：返回下标在start到end之间的第一个满足Objects.equals(o, e)的元素的下标。
详述：如果o==null，则查找第一个为null的元素，否则查找o.equal(e)
public int lastIndexOf(Object o) { return lastIndexOfRange(o, 0, size);}
功能：返回最后一个出现的满足Objects.equals(o, e)的下标，没有则返回-1。
int lastIndexOfRange(Object o, int start, int end)
功能：返回下标在start到end之间的最后一个满足Objects.equals(o, e)的元素的下标。
详述：如果o==null，则查找最后一个为null的元素，否则查找o.equal(e)
public Object clone()
功能：返回这个实例的一个浅拷贝。 (元素本身不会被复制。) 新的ArrayList的modCount为0
public Object[] toArray() {return Arrays.copyOf(elementData, size);}
功能：返回一个包含该列表所有元素的数组。
详述：这个方法返回的数组是安全的，列表中不包含指向数组中元素的引用。（该方法分配了一个新的数组）。
public T[] toArray(T[] a)
功能：返回一个包含列表中的所有元素的数组；返回数组的运行时类型为指定数组a的运行时类型。 如果列表长度小于指定数组a的长度，则将其拷贝到数组a中，返回数组a。否则，使用数组a的运行时类型和列表的长度分配一个新数组，再把列表中的元素拷贝进去，返回新数组。
public E get(int index)
功能：返回在列表中特定位置的元素。
public E set(int index, E element)
功能：用特定元素element替换列表中指定位置index的元素。返回值为原来的元素。
private void add(E e, Object[] elementData, int s)
功能：This helper method split out from add(E) to keep method bytecode size under 35 (the -XX:MaxInlineSize default value),which helps when add(E) is called in a C1-compiled loop.
public boolean add(E e)
功能：增加一个元素到列表的末尾。
描述：该方法会导致modCount++。调用add(e, elementData, size);实现增加。
public void add(int index, E element)
功能：在列表的指定位置插入指定的元素。 将当前在该位置的元素(如果有的话)和任何后续元素向右移动(在其下标上加1)。
描述：先调用rangeCheckForAdd(index)判断index是否越界，再判断elementData容量是否足够，不够则调用grow()扩大容量。插入元素前将index位及其后续元素都向右移动一位，再修改index位上元素为element。该方法会导致modCount++。
private void rangeCheckForAdd(int index)
功能：判断是否越界，越界则抛出异常
public E remove(int index)
功能：移除列表中指定位置的元素。 将所有后续元素向左移动(从其下标中减去1)。
描述：判断index是否越界， 调用fastRemove(es, index)移除元素。返回值为原来的元素。
private void fastRemove(Object[] es, int i)
功能：私有的移除方法，跳过了边界检查，而且不会返回移除的元素。
描述：modCount++。
赋值newSize = size - 1。如果newSize > i，说明i指向的不是数组的最后一个元素，需要调用System.arraycopy(es, i + 1, es, i, newSize - i);将后续的元素向前移动一位。
设置数组最后一位为null，并更新size为newSize。
public boolean equals(Object o)
功能：判断是否与对象o相等
描述：判断o == this。
判断o是否是List。
用一个expectedModCount保存当前状态的modCount。
判断o是否是ArrayList。如果是，则调用equalsArrayList((ArrayList<?>) o)判断；否则，调用equalsRange((List<?>) o, 0, size)进行判断。
在返回判断结果之前，调用checkForComodification(expectedModCount)判断期间是否发生过结构变化。
boolean equalsRange(List<?> other, int from, int to)
描述：先判断to是否大于elementData的长度。如果大于则说明了发生了结构变化。
取得other的迭代器，循环从from到to，用Objects.equals比较elementData里的元素和迭代器的值是否相等。
private boolean equalsArrayList(ArrayList<?> other)
功能：判断两个含有的元素数量是否相同。
描述：记录other的modCount为otherModCount。
比较size和other.size是否相同。
如果相同，再比较size是否小于elementData和other.elementData的长度。如果大于，则会抛出ConcurrentModificationException。此处是为了防止其他线程在当前线程判断是否相等时对elementData和other.elementData进行了修改。
如果没有异常，则循环遍历，用Objects.equals比较各个元素是否相同。
在返回判断结果之前，调用other.checkForComodification(otherModCount)判断other期间是否发生过结构变化。
private void checkForComodification(final int expectedModCount)
功能：判断当前的modCount跟expectedModCount是否相同。
描述：如果不相同说明，expectedModCount记录的状态发生了结构变化。
public int hashCode()
功能：返回哈希码
描述：用expectedModCount记录modCount的值。调用hashCodeRange(0,size)获取hash值。checkForComodification(expectedModCount)判断是否发生结构变化
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
功能：计算哈希值
描述：先判断to是否大于elementData的长度。如果大于，则抛出ConcurrentModificationException。否则，计算哈希码。
public boolean remove(Object o)
功能：删除列表中第一个满足Objects.equals(o, get(i))的元素，并返回true。元素不存在则不改变。
描述：用i遍历下标，查找第一个符合匹配的元素，没找到则返回false。找到了则退出循环，调用fastRemove(es, i)删除元素。
private void fastRemove(Object[] es, int i)
功能：私有的移除方法，跳过了边界判断，而且不会返回被删除的值
描述：modCount++。
如果i指向的不是列表最后一个元素，则调用System.arraycopy(es, i + 1, es, i, newSize - i)把i的后续元素均向左移动一位。
将es数组的最后一个元素赋值为null，并更新size。
public void clear()
功能：移除列表中所有的元素。
描述：modCount++。从头到尾遍历，将数组的每个位置设置为null。并将size更新为0
public boolean addAll(Collection<? extends E> c)
功能：按照指定集合的Iterator返回的顺序，将指定集合中的所有元素追加到列表的末尾。
描述：如果指定的集合在操作进行时被修改，则此操作的行为未定义。（没看太懂）
调用c.toArray()获得数组a。modCount++。判断a的长度numNew是否为0，为0则返回false。判断数组elementData是否能放入a数组，不能则调用grow(s + numNew)扩大数组容量。
调用System.arraycopy(a, 0, elementData, s, numNew);实现复制，最后更新size。
public boolean addAll(int index, Collection<? extends E> c)
功能：按照指定集合的Iterator返回的顺序，将指定集合中的所有元素追加到列表的指定位置。原来位置上的元素及其后续元素均向右移动。
描述：调用rangeCheckForAdd(index);判断是否越界。在将数组a中的元素拷贝至elementData之前，计算出需要右移的元素个数numMoved，调用System.arraycopy(elementData, index,elementData, index + numNew,numMoved);实现元素右移。
其余与addAll(Collection<? extends E> c)操作相同。
protected void removeRange(int fromIndex, int toIndex)
功能：移除列表中[fromIndex,toIndex)区间内的元素。并将剩下的后继元素左移。
描述：判断fromIndex>toIndex，否则抛出异常。
modCount++。
调用shiftTailOverGap(elementData, fromIndex, toIndex);实现元素移除
private void shiftTailOverGap(Object[] es, int lo, int hi)
功能：通过移动后续元素，实现删除[lo,hi)区间的元素。
描述：调用System.arraycopy(es, hi, es, lo, size - hi);实现元素移动，再将移动后超出范围的位置置为null。
public boolean removeAll(Collection<?> c) {return batchRemove(c, false, 0, size);}
功能：从列表中删除指定Collection中包含的元素。
描述：调用batchRemove(c, false, 0, size);。
public boolean retainAll(Collection<?> c) {return batchRemove(c, true, 0, size);}
功能：保留列表中指定Collection中包含的元素。
描述：调用batchRemove(c, true, 0, size);。
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end)
功能：保留/删除区间[from,end)中c中含有的元素
描述：complete==true时保留c中含有的元素，为false时删除c中含有的元素。
调用Objects.requireNonNull(c)判断Collection对象c为非空。
变量r从from开始遍历，如果满足c.contains(es[r]) != complement，则退出循环；如果遍历到最后一个都没有满足的，返回false。
退出循环后，用w记录r的位置，r向右移动一位。
从r开始循环到end，判断每一个元素es[r]是否在c中，如果在c中，则将该元素覆盖es[w]，并且w++。（即w和r两个下标，如果es[r]符合要求，则覆盖到es[w]上，且w++）。
如果中途c.contains()抛出异常，则调用System.arraycopy(es, r, es, w, end - r);保持与AbstractCollection的行为兼容性。并将w+=end-r，指向最后一个元素。
无论如何，最后modCount += end - w，记录结构变化，并且调用shiftTailOverGap(es, w, end);将末尾的元素设置为null。
private void writeObject(java.io.ObjectOutputStream s)
功能：序列化
private void readObject(java.io.ObjectInputStream s)
功能：反序列化
public ListIterator listIterator(int index)
功能：返回一个从指定位置开始的列表迭代器。
描述：调用rangeCheckForAdd(index);判断是否越界，返回new ListItr(index)
public ListIterator listIterator() {return new ListItr(0);}
功能：返回一个从0开始的列表迭代器。
public Iterator iterator() {return new Itr();}
功能：返回一个迭代器
Itr
private class Itr implements Iterator
成员变量
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
方法
public boolean hasNext() {return cursor != size;}
public E next()
功能：返回cursor指向的元素。
描述：调用checkForComodification()判断是否有结构性修改。
赋值i=cursor，判断i是否大于等于size，如果是，则抛出异常NoSuchElementException。
判断i是否大于elementData的长度，如果大于，则抛出异常ConcurrentModificationException。
赋值curosr=i+1，返回elementData[i]，并将i赋值给lastRet
public void remove()
描述：判断lastRet是否小于0，如果是，抛出IllegalStateException。
调用checkForComodification()判断是否有结构性修改。
通过ArrayList.this.remove(lastRet);，删除lastRet指向的元素。
因为后续元素往左移了一位，所以更新cursor = lastRet。更新lastRet = -1。因为发生了结构性变化，所以更新expectedModCount = modCount。
public void forEachRemaining(Consumer<? super E> action)
功能：
描述：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
功能：判断结构是否修改过