ArrayList类是一个继承自AbstractList类的变长数组，其长度可以随着元素数量的变化而变化。它同时实现了List、RandomAccess、Cloneable和Serializable接口。此外，ArrayList允许插入的元素为null，是一个线程不安全版本的Vector。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
所在路径：\java\util\ArrayList.java
ArrayList类继承关系图
一、成员变量
ArrayList类的成员变量共7个，大概可以分为四类。1是默认容量（长度）和最大长度；2是空数组实例；3是当前数组的值和长度；最后是常规的UID。各变量具体的描述如下所示。
/** 默认容量为10（List的长度） */
private static final int DEFAULT_CAPACITY = 10;
/** List的最大长度（因为有些虚拟机为head word保留了空间，所以这个值减了8） */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** 空数组实例，适用于有参数的构造器（容量传入为0） */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默认容量的空数组，适用于无参数的构造器（没有传入容量） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** 存储List元素的数组 */
transient Object[] elementData;
/** elementData的长度 */
private int size;
/** serialVersionUID */
private static final long serialVersionUID = 8683452581122892189L;
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别主要是供不同的构造器使用，ArrayList类的创造者认为这是一种规范：https://blog.csdn.net/weixin_43390562/article/details/101236833
transient关键字修饰elementData是为了在序列化时不将数组尾部的空元素也输入进去，而是采取实现writeObject()方法的方式，只序列化有值的数组部分：https://www.cnblogs.com/vinozly/p/5171227.html
二、构造器
1、无参构造器
直接将一个空的数组赋值给elementData。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2、入参为初始容量
初始化一个长度为initialCapacity的数组。
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);
}
}
3、入参为Collection接口的实现类或其子类
当入参为一个集合接口的实现类或其子类时，使用toArray()方法进行初始化。例如：List<String> stringList = new ArrayList<>(Arrays.asList("1", "2"));
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
三、add()和addAll()
1、add()
add()方法是ArrayList类的核心方法，它可以将元素添加到数组的尾部或指定位置。用户在使用add()方法不需要关心elementData的长度，只要不超过之前定义的最大长度，ArrayList会自动对elementData进行扩容。
/** 默认添加至尾部 */
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++;
}
每次插入数据前，ArrayList都会计算当前elementData是否需要扩容。扩容的具体过程如下：
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);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
扩容的动作最终由Arrays.copyOf()方法完成（这个方法我们之前介绍过，它最终调用的是System.arraycopy()方法，实际上就是数组元素的逐一拷贝），数组的实际长度会增加为原来的1.5倍。
modCount表示被修改次数，在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。当线程对ArrayList进行遍历时，通过比较modCount和expectModCount的值来确保循环不会因多线程的不安全操作而出错。
当newCapacity大于MAX_ARRAY_SIZE时，会调用hugeCapacity()方法，最多返回一个Integer.MAX_VALUE。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2、addAll()
addAll()方法可以将一个集合中的每个元素的都加入到数组中，具体的实现方法基本与add()一致。在copy前，ArrayList会先调用目标集合的toArray()方法，将其转换为一个Object类型的数组。
public boolean addAll(Collection<? extends E> 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<? extends E> 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;
}
四、remove()和removeAll()
1、remove()
remove()方法被用来从ArrayList中移除一个元素，移除元素的空当会被其他元素有序补齐。如果输入的参数是元素的index，ArrayList会直接用System.arraycopy()对其进行覆盖。如果入参是一个Object类对象，ArrayList会在遍历数组后调用fastRemove()方法。
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;
}
入参为Object类对象的remove()方法会在第一次遍历到该对象时移除并返回，此时ArrayList调用的是对象的equals()方法，必要的时候这个方法需要由调用者进行重写。
其中，fastRemove()方法的实现和入参为index的remove()方法是一样的，它的源码为：
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
}
2、removeAll()
removeAll()方法可以移除数组中所有被包含在输入集合中的元素，ArrayList采用判断后再赋值给新数组的方式，避免了频繁的arraycopy操作。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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()对应的是retainAll()方法，这个方法在调用fastRemove()方法时传入true，将入参集合中包含的元素留下来并删除其他元素。
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
五、indexOf()和lastIndexOf()
indexOf()和lastIndexOf()方法分别返回输入元素按从前往后和从后往前两种顺序查找出的数组下标，如果该元素出现了多次，则只返回按当前顺序查找到的第一个。
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;
}
六、writeObject()和readObject()
由于elementData被transient修饰，不会在序列化时被转换出来，ArrayList自己实现了writeObject()和readObject()方法。序列化时，ObjectOutputStream类会通过反射获得ArrayList的这两个方法，从而实现只序列化有elementData的有值部分。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
七、subList()
subList()方法会返回一个ArrayList的内部类，这个类同样继承自AbstractList，只是在起止index上与当前ArrayList有所不同。
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
/** 内部类SubList */
private class SubList extends AbstractList<E> implements RandomAccess
八、iterator()
iterator()方法同样返回一个类型为Itr的内部类，它实现了Iterator<E>接口。
public Iterator<E> iterator() {
return new Itr();
}
/** 内部类Itr */
private class Itr implements Iterator<E>
九、其他
最后，ArrayList同样提供了几个入参为各类接口实现的工具方法，用户可以自定义操作的规则。
/** 遍历并支持函数式处理 */
public void forEach(Consumer<? super E> action)
/** 有条件移除 */
public boolean removeIf(Predicate<? super E> filter)
/** 全部替换并支持函数式处理 */
public void replaceAll(UnaryOperator<E> operator)
/** 排序 */
public void sort(Comparator<? super E> c)
网友评论