ArrayList 是一个动态数组, 它是线程不安全的, 允许元素为null. 其底层数据结构是数组, 它实现了List
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10;
// 在初始化时, 传入的大小为0时, 赋值给elementData
private static final Object[] EMPTY_ELEMENTDATA = {};
// 当使用无参构造函数时, 赋值给elementData
// 使用两个不同的数组表示空数组的原因是, 无参构造函数在第一次调用add时, 需要进行扩容(扩容到默认大小10)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private int size;
transient Object[] elementData;
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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
}
ArrayList中一共有三个构造函数, 方法中做的事情并不复杂, 目的都是初始化底层数组elementData, 需要注意的是elementData是被transient关键字修饰的.
首先分析下添加单个元素的add方法.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public boolean add(E e) {
// 判断是否需要扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
// 判断是否需要扩容
ensureCapacityInternal(size + 1);
// 指定位置之后的所有元素往后移动
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
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++;
// 如果超过了当前数组的最大长度, 进行扩容
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);
// 将数据移动到新的数组中
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;
}
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
protected transient int modCount = 0;
}
当add(E e)方法添加到队尾时分为两步, 判断并扩容然后赋值. 当add(int index, E element)方法添加到指定位置分为三步, 判断并扩容, 移动元素然后赋值. 可以结合注释阅读代码.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
E elementData(int index) {
return (E) elementData[index];
}
public E remove(int index) {
rangeCheck(index);
modCount++;
// 返回被删除的元素
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) // 将index之后的所有元素往前移动一位
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将最后一位设为null, 并且size - 1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 如果有重复的元素, 那么就删除下标小的元素
public boolean remove(Object o) {
if (o == null) { // 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;
}
// 快速删除, 和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;
}
}
删除的代码并不是很复杂, 直接参照注释阅读源码即可.
当我们在ArrayList中添加了大量元素, 然后删除了大部分元素, 这会导致数组中有很多空闲部分, 此时可以调用trimToSize方法进行收缩.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
}
ArrayList实现了Serializable接口, 该接口只是一个标记接口, 表示是否可以被序列化. 在ArrayList代码中, 最重要的elementData是被transient修饰, 表示该属性不需要被序列化. 主要原因在于elementData中可能含有大量的null(删除元素后将末尾设置为null), 每次都进行序列化会浪费时间和空间, 所以在ArrayList中重写了writeObject方法用于序列化elementData对象.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
ArrayList实现了RandomAccess接口, 该接口只是一个标记接口, 用来表明其支持快速(通常是固定时间)随机访问. 此接口的主要目的是允许一般的算法更改其行为, 从而在将其应用到随机或连续访问列表时能提供良好的性能.
继承自RandomAccess表示该类能快速随机访问存储的元素, 比如数组, 通过下标index进行快速访问, 实现了该接口的ArrayList底层实现就是数组, 同样是通过下标访问, 只是我们需要用get()方法的形式, ArrayList底层仍然是数组的访问形式. 相比较而言, LinkedList底层实现是链表, 所以并没有实现RandomAccess接口.
数组支持随机访问, 查询速度快, 增删元素慢; 链表支持顺序访问, 查询速度慢, 增删元素快. 所以对应的ArrayList查询速度快, LinkedList查询速度慢, RandomAccess这个标记接口就是标记能够随机访问元素的集合, 简单来说就是底层是数组实现的集合.
ArrayList实现了Cloneable接口, 该接口也是一个标记接口, 表示实现接口的子类对象都能使用Object类中的clone()方法.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn‘t happen, since we are Cloneable
throw new InternalError(e);
}
}
}
ArrayList实现的是浅拷贝, 调用clone方法后返回的是当前ArrayList的一个拷贝, 当修改ArrayList中的某个元素后影响拷贝的副本内的元素.
迭代器是一种设计模式, 提供一种方法来访问聚合对象中的各个元素, 而不用暴露这个对象的内部表示. 在ArrayList中, 迭代器分两种: Iterator和ListIterator.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public E next() {
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;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
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++]);
}
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
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;
}
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];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} 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();
}
}
}
}
Itr与ListItr的代码比较简单, 如果熟悉迭代器模式, 就不需要什么解释了. 这边需要注意的是, 在我们修改集合时中元素时(调用add, remove等方法), modCount就会累加一. 而在一个迭代器初始化的时候会将modCount赋值给expectedModCount, 如果在迭代器遍历的过程中, 一旦发现这个集合的modCount和迭代器中存储的expectedModCount不一样那就会抛异常.
我们知道ArrayList不是线程安全的, 因此如果在使用迭代器的过程中有其他线程修改了list, 那么将抛出ConcurrentModificationException, 这就是所谓fail-fast策略. 这一策略在源码中的实现是通过modCount域, modCount 顾名思义就是修改次数, 对ArrayList内容的修改都将增加这个值, 那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount. 在迭代过程中, 判断modCount跟expectedModCount是否相等, 如果不相等就表示已经有其他线程修改了List.
ArrayList是一个比较基础的集合类, 它的结构简单(本质上就是一个变长的数组), 实现上也不复杂. 本文讲解的并不是其全部的源码, 只是几个比较重要的方法, 其余方法可以自行翻阅阅读.
原文：https://www.cnblogs.com/annwyn/p/14432923.html