ArrayList源码解析
这仨货
- elementData:就是实际存储元素的数组,被transient,表明不参与序列化，意味着elementData里的数据仅存在调用者的内存中
- EMPTY_ELEMENT空数组
-
DEFAULTCAPACITY_EMPTY_ELEMENT: 不同于EMPTY_ELEMENT，这个空的Object[]有啥用？
（为什么要两个空数组？3号空数组用法如下，那么二号呢？其实二号要解决的是当我想创建一个空集合时，即调用new ArrayList(0),在随后调用add方法时，不会被自动扩容成大小为10，这就是二者区别-defaultCapacity。)
无参构造函数
当调用无参构造函数时，将它赋给elementData，这样做感觉好像没多大用？其实它就像一个标记，什么时候会用到它呢？当第一个元素被添加的时候
add()
size： 是实际元素个数
扩容三姐妹之二三
---DEFAULT_CAPACITY = 10；也就是说当你new ArrayList()调用add(E e)或是其它add方法后，会根据需要创建一个Object[minCapacity]初始数组-------(感觉写了半天细枝末节的东西)
---modeCount是用作Fail-Fast机制
---grow()执行数组扩容操作，利用Arrays.copyOf(),继续追踪发现是调用了System.arrayCopy(),创建了一个扩容后大小的新数组copy[]，返回copy
ArrayList还有一类构造函数：ArrayList(Collection<? extends E> c),它什么原理呢？ Collection接口有个toArray()，举例如具体实现类ArrayList的toArray()里调用Arrays.copyOf()，如上所述它返还一个copy[]，而该构造函数里就利用了这个来将c转化为数组赋给elementData。其实很多地方都用到了Arrays.copy(),比如trimToSize()..
ADD（）：
ArrayList其实是一个动态变化的数组，我们来看它在添加删除元素时的变化：
从add入手：add(E e); add(int index; E elementi); add(Collention<? extends E> c); add(int index, Collection<? extends E> c)四种方法。
- add(E e):首先会调用ensureCapacityInternal(size+1),该方法又会调用ensureEcplicitCapacity(),在该方法里如果size+1>elementData.length，则调用growth()方法进行扩容，逻辑如下
扩容
一般情况下扩容为原来的1.5倍，这里又用到 了Arrays.copyOf()
- add(int index, E e)
add
显而易见，先判断index是否越界，在进行扩容判断，之后调用System.arraycopy()将原数组index及之后的元素后挪一位，最后添加
- add(Collention<? extends E> c)与add(int index, Collection<? extends E> c)核心类是toArray()与System.arraycopy(),与之前提的一样（代码不贴了--累人！）
indexOf(Object o）与lastIndexOf(Object o)都会对o进行null判断，因为ArrayList可以添加null；clone()为浅拷贝，elementData数据不包括在内
get,set,remove方法都没什么好说的
removeAll(Collection<?> c), retainAll(Collection<?> c)
这两个方法中若c==null则抛出NullPointException异常，接着调用batchRemove(Collection<?> c, boolean complement)
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;
}
//w == size则说明没有改变，返回false，removeAll与retainAll结果为false
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;
}
该方法在complement为true时，取elementData与c的交集，即相同部分保留；为false时，取elementData独有部分保留。所以removeAll调用batchRemove(c, false)，retainAll调用batchRemove(c, true);
迭代器
- Iterator
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的元素的下标
int lastRet = -1; // 被返回的元素的下标，即调用next()返回elementData[lastRet]
int expectedModCount = modCount; //fail-fast,迭代中若数组被更改(add,remove
添加删除操作）会造成二者不相等，抛ConcurrentModificationException
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); //fail-fast
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); //调用的是ArrayList的remove方法
cursor = lastRet; //lastRet表示被删除的位置，后被cusor前挪一位填补上，cusor变为lastRet
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//如果相对elementData中每个元素都执行相同操作，你可以写一类实现Consumer接口，
复写accept（），在调用该方法
@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();
}
}
Consumer是个函数式接口，函数描述符为：T → void, 多用于lambda
- ListIterator
//继承itr，实现ListIterator implements Iterator<E>,ListIterator拓展了Iterator
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;
}
//返回前一个元素，即cusor-1处；cusor退一位，反复调用实现倒叙；如果之后你接着调用next(),
previous()将返回同一个结果
@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];
}
//下面的add（）方法会重置lastRet = -1;所以add后避免调用set
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//add会插入到原本调用next函数返回的元素之前，cusor自增1仍指向原本next函数返回的元素，
此时可通过previous来得到新增的元素；这样设计保证了next函数不受影响
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 extends AbstractList<E> implements RandomAccess
内部类private class SubList，作用就是生成一个[fromeIndex,toIndex)大小的小型List，麻雀虽小五脏俱全，只能通过subList(int fromIndex, int toIndex)函数调用，功能实现依赖外部类ArrayList，实现了自己的迭代器ListIterator。
还有一方法Arraylist.sort在这篇文章里介绍MergeSort与TimSort，ComparableTimSort
