整体介绍
ArrayList实现了List接口，是一个常见的集合类,它有一下特点：
- 是顺序容器，即元素存放的数据与放进去的顺序相同，
- 允许放入null元素，
- 底层通过数组实现。
- 添加元素而容量不足时，可自动扩充底层数组的容量。
- 除该类未实现同步外，其余跟Vector大致相同。
- 操作时间复杂度分别为：
- size,isEmpty,get,set,iterator,listIterator方法运行时间为常量时间
- add方法运行为摊还常量时间，也即增加n个元素的时间为O(n)
- 其他的操作运行时间大致为线性时间，常数因子相较于LinkedList更小。
摊还时间是一个操作的平均代价，可能某次操作代价很高，但总体的来看也并非那么糟糕；add方法是摊还常量时间与底层数组容量自动扩充有关
image.png
源码分析
成员变量
/**
* 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 当ArrayList的空实例,用于无参数初始化
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* ArrayList的底层数组
* 泛型只是编译器提供的语法糖所以这里的数组是一个Object数组
* ArrayList的容量就是elementData.length
* 当ArrayList为空时,elementData == EMPTY_ELEMENTDATA
* 当第一个元素加入时elementData.length == DEFAULT_CAPACITY
* transient 说明这个数组无法序列化。
*/
private transient Object[] elementData;
/**
* ArrayList包含的元素数量,与容量不同.
*/
private int size;
/**
* 数组最大容量
* 一些虚拟器需要在数组前加个头标签，所以减去8 。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 这个变量并不是ArrayList里面定义的,而是继承自父类AbstractList
* ArrayList在使用Iterator时发生不同步会抛出错误就是依靠了这个变量
(虽然不可靠,想要可靠的同步保证用
List list = Collections.synchronizedList(new ArrayList(...))
或
concurrent包下的CopyOnWriteArrayList
或
用synchronized进行一层代理)
* add和remove方法都是有modCount++.
* 下面再具体说说modCount的作用
*/
protected transient int modCount = 0;
get()
get()方法本身很简单,不涉及数组的容量扩充,除了检查下标范围以及类型转换,与一般的数组get()操作没区别
public E get(int index) {
//检查是否越界,
//由于java数组本身就会检查是否越界,所以这里只是检查是否超过了size,
//要知道数组的大小大于size,index大于size并不会触发数组越界.
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
//对元素进行类型转换,底层储存是Object,但返回是E.
return (E) elementData[index];
}
set()
set()方法也很简单,不涉及数组的容量扩充,除了检查下标范围,与一般的数组set()操作没区别
public E set(int index, E element) {
//在get()中提到的,检查越界问题.
rangeCheck(index);
//直接用element替换elementData[index]
//赋值到指定位置，复制的仅仅是引用
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
add()
如果不算入容量扩充的耗费,
add()方法运行时间为常量时间.但是可能某次add()触发了容量扩充,那么那次操作的运行时间为线性时间.所以add()的运行时间为摊还常量时间,即n次操作的时间为O(n).add()会触发modCount++
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
*从这个方法可知第一次add元素,初始容量为DEFAULT_CAPACITY,即10
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
*add()的modCount++来源于这里
*当新容量大于当前容量时,触发容量扩充,即调用grow方法.
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
*ArrayList实现容量自动扩充是依靠了这个方法.
*新容量为原容量的1.5倍
*耗费时间为O(n),因为需要复制原来的元素到扩充后的数组.
*/
private void grow(int minCapacity) {
// overflow-conscious code
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);
}
remove
-
remove运行时间为O(n),因为ArrayList底层实现为数组,所以删除元素后,需要移动之后的元素. - 除了越界检查,与一般数组的
remove没有区别 - 在
remove后并不会影响数组容量 -
remove会触发modCount++
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]的引用,
//因为假如不清除引用,那么ArrayList就会一致保留那个对象
//GC不能清除仍被持有引用的对象
elementData[--size] = null;
return oldValue;
}
序列化
- 在上面成员变量那里提到了Object[] elementData用了transient关键字,无法序列化,这里ArrayList复写了readObject和writeObject方法,实现底层数组的序列化.
- 复写的writeObject用modCount保证了当发生不同步问题时抛出错误(虽然不可靠)
- 关于序列化的知识可以看我转载的<<深入理解Java对象序列化>>
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 记下方法开始时的modCount
int expectedModCount = modCount;
//将没有transient关键字的成员变量写入
s.defaultWriteObject();
//这里写入数组的容量,但是把数组元素的数量size视为容量,
//而不用原来的容量elementData.length
s.writeInt(size);
// 将底层数组的元素依次写入
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//与之前记下的modCount对比,看是否有其他线程操作了ArrayList,有则抛出错误.
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 将没有transient关键字的成员变量读入
s.defaultReadObject();
// 将数组容量读入,
//但是如上面writeObject所写把size视为了数组容量,所以这里没有实质的作用
s.readInt(); // ignored
if (size > 0) {
// 扩充数组大小
ensureCapacityInternal(size);
Object[] a = elementData;
// 把数组元素一次写入
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
迭代器
ArrayList用iterator()可以返回迭代器.
- 实现了Iterator<E>接口;
private class Itr implements Iterator<E> - 当有多个线程同时操作ArrayList,使用迭代器可以抛出错误,避免发生不同步(这里就是用了
modCount,用法与writeObject()的差不多) - 迭代器使得对容器的遍历操作完全与其底层相隔离，可以到达极好的解耦效果。
iterator()
public Iterator<E> iterator() {
//使用构造函数,返回一个新的迭代器
return new Itr();
}
迭代器成员变量
int cursor; // 下一个返回的元素的下标
int lastRet = -1; // 上一次返回的元素的下标,初始为-1
//记下创建迭代器时的modCount,用于之后的同步检查
int expectedModCount = modCount;
hasNext()
hasNext()用于检测是否有下一个元素返回,实现很简单.
public boolean hasNext() {
return cursor != size;
}
checkForComodification()
- 这个方法是迭代器可以在多个线程操作时抛出错误(fail-fast机制)的关键方法
- 下面的
remove和next都调用了这个方法 - 实现很简单,对比modCount,如果不一致,则说明有其他线程也在用ArrayList,抛出错误.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
next()
-
next()方法的实现很简单,代码写的很清楚 -
next()在内部做了很多安全检查,保证了使用迭代器的安全性 -
next()调用了checkForComodification(),使用了fail-fast机制
@SuppressWarnings("unchecked")
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];
}
remove()
- 迭代器的
remove()方法内部是调用了ArrayList的remove()方法 -
remove()调用了checkForComodification(),使用了fail-fast机制
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();
}
}
后记
- ArrayList的源代码写的很好,注释也很清晰,我在这篇分析里面有很多内容其实都是从注释里翻译,或者加了点自己的理解.
- 这里只是挑了几个我觉得重要的地方做了分析,其余的推荐直接看源代码
