一、宏观关系
ArrayList实现了List接口，而List接口继承了Collection接口（下文源码参照Java8版本）
二、数据结构
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//一个空的数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//一个空的默认大小的数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放数据的数组
transient Object[] elementData;
//记录数组的大小
private int size;
//记录集合结构被修改的次数
protected transient int modCount = 0;
1、EMPTY_ELEMENTDATA
当调用有参构造指定容量的时候，会把数组elementData指向它。减少空数组频繁创建的内存开销。
2、DEFAULTCAPACITY_EMPTY_ELEMENTDATA
调用ArrayList的无参构造器的时候，会把数组elementData指向它。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
思考1：为什么要区分为两个空数组实例呢，直接一个不行么？
是为了优化性能和内存使用：
- EMPTY_ELEMENTDATA 允许 ArrayList 在不需要存储任何元素时不分配任何内存。
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 允许 ArrayList 在添加第一个元素时直接扩展到一个合理的默认容量，而不是从一个非常小的容量开始逐步扩容，这样可以减少扩容操作的次数，提高性能。
这种设计使得 ArrayList 能够在不同场景下灵活地管理内存，同时保持了添加元素时的高效性。
3、elementData
细心的肯定发现，elementData是用transient关键字来修饰的。
transient
——Java的关键字，用于类的序列化机制。
当一个类实现Serializable接口时，这个类的所有非静态成员变量都会被序列化，除非他们被transient修饰了。
序列化：把对象转换成字节流
反序列化：把字节流转换成对象
思考2：为什么要用transient来修饰呢？
ArrayList通过重写writeObject和readObject方法来实现自定义序列化，只将必要的元素序列化。（具体后面会分析）
——使用transient关键字修饰elementData数组的好处是，它允许ArrayList在序列化时只关注实际存储的数据，而不是整个数组的容量。这样可以使得序列化过程更加高效，并且可以根据需要调整序列化的细节。例如，如果ArrayList中的某些元素是临时的或者不需要序列化，那么可以通过这种方式来避免不必要的序列化操作。
4、modCount
是Java集合类中的一个保护级别的字段，记录集合结构被修改的次数（改变集合大小或者以其他方式干扰正在进行的迭代器遍历的操作，如添加、删除或替换集合中的元素。）
作用：支持 Java 集合的 fail-fast 迭代器机制
——————
fail-fast（快速失败）迭代器会在迭代过程中抛出 ConcurrentModificationException 异常，以响应不可预测的并发修改。这种机制确保了在迭代过程中，如果有其他线程对集合进行了结构性修改，迭代器能够及时检测到这种修改并报错，从而避免出现不确定的行为。
这里就想到了平时会遇到的一种实际情况：
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
//使用for循环
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("b")) {
list.remove(i); // 可能会抛出 ConcurrentModificationException
}
}
//使用迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if (item.equals("b")) {
iterator.remove(); // 安全的，不会抛出 ConcurrentModificationException
}
}
思考3：为什么用for循环会抛出异常，而用迭代器不会呢？
这里就和modCount相关，当对集合进行删除/添加操作的时候，modCount就会++
- for循环的时候
modCount值更改了，和迭代器在创建时会记录当前的 modCount 值不一致。迭代器就会抛出异常。 - 迭代器遍历的时候
如果你使用迭代器自带的 remove 方法删除元素，迭代器会更新其内部状态，包括 expectedModCount，以匹配集合的最新状态。因此，使用迭代器的 remove 方法删除元素是安全的，不会抛出 ConcurrentModificationException。
三、构造函数
1、无参构造
（上面已有，不做赘述）
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);
}
}
//传入集合
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
//如果传入集合也是ArrayList，就直接把elementData执行toArray后的数组a
elementData = a;
} else {
//如果不是，就调用Arrays.copyOf方法把a赋值给elementData
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
思考4：为什么要用Arrays.copyOf（）
- 确保类型兼容
传入的集合通过toArray方法返回一个数组，但是这个数组的类型不一定就是Object[]（可能存在向上转型的情况）。用Arrays.copyOf()的方法能确保新数组的类型是Object[] - 安全性
如果 c 是 ArrayList，c.toArray() 返回的数组实际上是 String[] 类型，如果直接将这个数组赋值给 elementData，而 elementData 期望的是 Object[] 类型，那么在尝试存储非字符串类型的 Object 时，就会抛出 ArrayStoreException。
总之使用 Arrays.copyOf() 可以确保无论 c.toArray() 返回什么类型的数组，最终 elementData 总是 Object[] 类型，从而避免了潜在的类型问题
四、成员方法
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) {
//如果是无参构造的空数组，那么就去默认容量10和传入容量的大者；否则直接为传入容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//保证显式的容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果需要的容量比目前数组的长度更大，就调用grow进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//扩容1.5倍
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);
}
//校验处理
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
总结：
- 懒初始化，如果是第一次添加元素，会直接给默认的初始容量10。
- 之后每次超出就会新建一个1.5倍大的数组（如果仍然不够就直接赋值当前最小需要的容量值），将旧数组中的所有元素复制到新数组中。然后把内部的数组引用指向新的数组，旧数组的引用会丢失，然后被垃圾回收。
这个复制过程是通过System.arraycopy()方法完成的，这是一个高效的数组复制方法。
》带参数
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++;
}
private void rangeCheckForAdd(int index) {
//这个就是我们常见的数组下标越界异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2、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;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
3、clear()
public void clear() {
// 将 size 设置为 0，表示没有元素
size = 0;
// 将数组中的所有元素位置置为 null，以帮助垃圾回收
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
}
注意：clear之后只是把内部数组元素个数size置为0，但是内部数组的内存空间大小是不变的。
4、序列化方法
》writeObject()
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();
}
}
writeObject方法在序列化的时候调用，负责把ArrayList的状态写入到ObjectOutputStream。
这个方法会先写modCount，然后写入ArrayList的实际大小size，最后逐个写入存储在elementData中的数据。
》readObject()
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
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
}
}
}
readObject方法在反序列化的时候调用，负责从ObjectInputStream中读取ArrayList的状态。这个方法先读取modCount和size。然后根据读取的大小创建一个新的elementData数组，并且逐个读取元素来填充到这个数组中。
5、内部迭代器相关
public Iterator<E> iterator() {
return new Itr();
}
//迭代器的内部类
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回元素的下标
int lastRet = -1; // 最近一次返回元素的下标，在调用next() 或 previous() 方法时，lastRet 都会被更新为返回元素的索引
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//modCount检查
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;
//返回元素，并且更新lastRet
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
//remove后会把lastRet设置为-1，防止连续调用remove
lastRet = -1;
//更新expectedModCount为当前值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
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();
}
}
//判断modCount与最开始记录的是否一致
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
@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];
}
}
从上述可以看出，ArrayList有一个内部迭代器，每次在调用next()、add()、remove()方法时，都会先判断modCount和expectedModCount是否相等，不相等说明在迭代期间是否被更改过表结构。
————
而上文提到的用迭代器的remove、add不会报错，就是因为内部迭代器在调用这些方法后，会把expectedCount更新。
注意：
remove方法使用lastRet来定位删除元素的，所以remove得在 previous() 、next()之后调用。如果 lastRet 为 -1，表示没有元素被迭代，那么调用 remove() 或 set() 就是非法的，迭代器也会抛出 IllegalStateException 异常。
五、总结
- ArrayList底层数据结构是一个Object类型的数组elementData，默认容量为10，懒初始化。
- 添加元素会进行扩容检查，如果容量不够，就会进行1.5倍的扩容oldCapacity + (oldCapacity >> 1)，仍然不够就直接扩容置目标容量。扩容方法是新开一个数组，把旧数组数据赋值过去。
- 因为底层是数组的结构，有序可重复。
- 使用自定义的序列化方法writeObject和readObject，只将必要的元素序列化，节省不必要的内存空间和性能开销。
- 通过保护字段modCount支持快速失败机制，当对集合进行删除/添加操作的时候，modCount就会++。如果迭代过程中表结构修改，就会抛出ConcurrentModificationException 异常。可用迭代器的remove、add方法解决。
- 多线程环境下，线程不安全。可能报并发修改异常ConcurrentModificationException
扫一扫
3万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
