ArrayList可以说是我们最常用的集合类了，底层通过数组实现，同时允许有空值存在。
首先我们看源码中ArrayList类的继承以及实现：
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
我们可以看出，ArrayList继承了AbstractList，实现了List
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放集合数据
transient Object[] elementData; // non-private to simplify nested class access
//实际元素大小
private int size;
//AbstractList里的属性，记录对list的操作次数
protected transient int modCount = 0;
注意：
- size代表的是数组中实际的元素个数，而elementData.length为集合的容量，表示数组最多可以存储多少元素。
- 两个空数组，简单来讲就是第一次添加元素时知道该 elementData从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
默认构造了一个容量为10的空的List集合，但初始化的时候只是赋了一个空的数组，实际上是第一次添加元素将容量扩容到10的。
3.2、根据容量构造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);
}
}
构造一个初时容量为initialCapacity的List集合。在无参构造中我们使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而在根据容量构造时，如果容量为0我们使用的是EMPTY_ELEMENTDATA，这些差别我们一会在add方法中就可以看到区别。
3.3、根据Collection构造public ArrayList(Collection c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
将Collection转换为数组赋给elementData，如果c的size不为0，则判断c的类型，如果与该List不一致则作一次转换再赋值。如果c的size为0，则赋空数组：EMPTY_ELEMENTDATA。
4、主要方法 4.1、add方法public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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 code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//扩大1.5倍
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;
}
在每次进行add操作之前都要先进行容量确定。然后size增加一。
- calculateCapacity函数中elementData如果为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则返回DEFAULT_CAPACITY,与minCapacity的最大值，对于第一次add当然是DEFAULT_CAPACITY更大一些，所以无参构造默认构造容量为10的List。而如果是有参构造的，也就是通过EMPTY_ELEMENTDATA构造的List，第一次add后容量为1，这就是两者的区别。
- ensureExplicitCapacity函数modCount自增，然后判断minCapacity与elementData.length的大小，如果minCapacity大，就进行扩容操作。
- grow函数也很好理解，首先将原来容量扩大1.5倍，如果1.5倍满足不了新的容量需求，则直接将所需容量当作新容量。如果所需容量或者1.5容量过大，则直接Integer.MAX_VALUE作为新的容量。
- 可能有人会问为什么扩容的时候先判断1.5倍是否合乎要求而不是直接扩容到所需容量？那是因为如果每次扩展都是只扩展到当时所需容量，那么一旦执行一次扩容后，下一次再次执行add就需要再次扩容，这样效率就会大大降低！
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int 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;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
add方法有种，一种是默认在数组最后方添加新的元素；另一种是在索引index处添加或者修改元素，这种方法在最开始会判断index位置是否存在（包括数组后方第一个元素），不存在会抛出IndexOutOfBoundsException数组越界异常。
addAll(Collection c)是将Collection中的所有元素放在该List最后。
addAll(int index, Collection c)是将Collection中的所有元素放在该List索引index位置，原List的index后元素后移。
4.2、set方法public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
该方法是修改数组上index位置上的元素，改为element。该方法与add(int index, E element)方法类似。区别就是add可以在数组最后添加新的元素，而set只能修改已存在的元素。这也就是rangeCheck与rangeCheckForAdd的区别。
4.3、get方法public E get(int index) {
rangeCheck(index);
return elementData(index);
}
获取索引index位置的元素。
4.4、remove方法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 work
return oldValue;
}
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 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
}
先看这两常用的romove方法，第一个是通过索引index来移除index处的元素，然后将后面元素前移，size减一，当然index需要判断是否存在。第二个是通过对象删除，如果为空则找到第一个为空的元素位置然后调用fastRemove移除该元素，将index后的元素前移，size减一；如何不为空则找到第一个与给定对象equals的元素位置，然后就跟为空一样了。没有找到则返回false。fastRemove方法其实跟remove(int index)一样只是返回值不同。
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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 work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
removeAll()是去除所有存在于Collection c中的元素。而retainAll()是去除所有不存在于Collection c中的元素。这两个方法刚好相反，第一个相当于求交集之后再求补集，另一个是求交集。
@Override
public boolean removeIf(Predicate 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 unmodified
//计数器，记录revove掉的次数
int removeCount = 0;
//声明要remove掉的集合，声明为set，保证不重复remove
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
//循环遍历list
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//boolean test(T t);校验参数是否匹配，匹配则返回true，如果匹配，则在removeSet中存入索引，removeCount值加一
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//校验此时的集合是否在多线程IO下受到改变，若受到改变则抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//源码中这句，表明了，将不需要移除的空间左移
// shift surviving elements left over the spaces left by removed elements
//定义anyToRemove，如果removeCount > 0则为true
final boolean anyToRemove = removeCount > 0;
//如果anyToRemove为true则继续进行，否则意味着没有匹配的可移除元素，直接return anyToRemove = false;
if (anyToRemove) {
//若有元素符合移除条件，则声明新size，重新定义list大小(ArrayList初始默认容量为10)
final int newSize = size - removeCount;
//循环遍历元素赋值，这里用到了一个新的方法nextClearBit(fromIndex)
//将需要移除的元素在重新存储的时候跳过
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
//如果新的集合与原集合比较，将指定要移除的设置为null,GC回收内存
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//更新全局变量的集合大小为移除后的新集合大小
this.size = newSize;
//再次判断是否受到多线程IO影响
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
//官方解释：返回设置为在指定的起始索引上或之后出现的第一个位的索引。
public int nextClearBit(int fromIndex) {
// Neither spec nor implementation handle bitsets of maximal length.
// See 4816253.
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
checkInvariants();
int u = wordIndex(fromIndex);
if (u >= wordsInUse)
return fromIndex;
long word = ~words[u] & (WORD_MASK << fromIndex);
while (true) {
if (word != 0)
return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
if (++u == wordsInUse)
return wordsInUse * BITS_PER_WORD;
word = ~words[u];
}
}
private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
这里面代码有一丢丢复杂哈，具体上网上找了一篇有中文注释的源码大家阅读一下（手动狗头）。具体解释就是去除集合中满足某个条件的元素。例：去除集合中所有三岁的狗。
class Dog {
private String name;
private int age;
...
}
List list = new ArrayList<>();
list.removeIf(dog -> dog.age == 3);
由于ArrayList集合允许重复所以一般remove()用的比较少，因为remove()只能去除第一次出现的元素。一般我们都用removeAll()或者removeIf()，因为这两个方法可以去除集合中所有满足条件的元素。
4.5、indexOf方法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;
}
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中的位置，第一个为对象在List中从前往后第一次出现的位置，没有返回-1；第二个为对象在List中从后往前第一次出现的位置，没有返回-1。
4.6、toArray方法public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public 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;
}
该方法是将List转换为数组，第一种无参的是直接转换为Object类型的；第二种则是转换为给定类型T的数组，其中T必须是原List中元素对象E发父类或者E本身，否则抛出ArrayStoreException异常。如果给定的T[]长度小于size则返回原List长度的数组，大于的话将多出来的部分用null填充。
4.7、iterator方法这部分具体参考https://www.cnblogs.com/mrpour/p/10764088.html
4.8、其他方法public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
将List的容量缩小到实际长度的大小。
public int size() {
return size;
}
返回List的实际长度。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
判断List是否包含某个对象，即是否存在一个对象element满足element.equals(o)为true。
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
清除List中所有的元素，使其为空值。
public ListsubList(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 + ")"); }
从fromIndex截取到toIndex，返回截取出来的List。
public void sort(Comparator c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
对于List中的元素进行排序，如果在排序过程中modCount发生变化，即List发生改变，则抛出ConcurrentModificationException异常。
