ArrayList源码分析

前言

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承结构是这样

数据结构与扩容操作

既然名字是ArrayList,那么底层多多少少和数组有关。

先来看看构造函数里做了啥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] EMPTY_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);
}
}

当构造函数的参数为空时,给成员变量elementData赋了一个空的数组。
当我们指定了初始大小的时候,如果参数大于0,那么elementData就是我们设的大小,如果等于0,那么还是赋了一个空的数组给elementData

进行add操作时 。

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

我们可以注意到一个ensureCapacityInternal的函数,这个函数是确保底层的数组有足够的空间进行增加的。

1
2
3
4
5
6
7
8
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

ArrayList中还有一个成员变量是DEFAULT_CAPACITY,默认大小是10。
如果是无参数的new的ArrayList话而且是第一次调用add的话,那么minCapacity就会是10。
但是如果是下面再进行add的话,再进去这个函数,则是直接调用ensureExplicitCapacity函数。
不会在进行Math.max的操作了。
这里还是没有真正就行底层扩容操作。

再来看看ensureExplicitCapacity函数

1
2
3
4
5
6
7
8
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

这里用到了modCount变量,这个在HashMap中也有看到,这个和fail-fast有关,下面会介绍。
下面还对minCapacity - elementData.length > 0进行了一次判断,因为现在的长度的数组可能还没用完,如果这样的话,那么不用扩容,直接用就行了。
还有一种情况就是minCapacity已经超过int最大值了,变成了负数了,那样也不会进行扩容。

关键是在grow函数中

1
2
3
4
5
6
7
8
9
10
11
12
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}

这里才看到了真正的扩容操作。但是别急,在操作之前还需要进行判断作为保证。
这里有三个变量,和名字一样,

  • minCapacity就是这次扩容后的最小容量
  • newCapacity是最后进行扩容的大小,也就是最终扩容时用到的
  • oldCapacity是现在的大小。

现在我们在回去看add参数的话,会看到他调用的ensureCapacityInternal时的参数是当前的大小加1,注意,只是加了1而已,每次add都扩容的话,那么代价肯定会非常高的。

这里的溢出检查的newCapacity是现在的size加上size的一半。也就是原来的大小的3/2。
所以不出意外的话,大多数情况下,每次扩容的大小都是原来的大小的3/2。
那么我们还需要考虑特殊情况,就是溢出的情况。

如果newCapacity乘上了原来的3/2,超过了int的范围,变成了负数,那么就是newCapacity - minCapacity < 0为true了,那么newCapacity的大小就是minCapacity,也就是原来的大小加上了1。

如果没有溢出,但是比MAX_ARRAY_SIZE大,也就是在Integer.MAX_VALUE - 9Integer.MAX_VALUE之间。那么newCapacity的大小就是hugeCapacity的返回值。

1
2
3
4
5
6
7
8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

这里如果minCapacity溢出了,也就是现在的size的大小已经是Integer.MAX_VALUE了,那么就抛出OutOfMemoryError了。

hugeCapacity函数中,minCapacityMAX_ARRAY_SIZE进行了比较,如果minCapacity大于MAX_ARRAY_SIZE但是还没有溢出,那么就直接扩容到Integer.MAX_VALUE

看到这里我猜想了如果出现了极端的情况,就是addsize刚好是Integer的最大值会怎么样?
那时,minCapacity - elementData.length的结果是1,还是可以进入grow函数。最后进入hugeCapacity函数,最后抛出OutOfMemoryError
给力。代码的鲁棒性很好。

fail-fast机制与遍历

上面我们提到一个变量modCount,每次我们进行add或者是进行一些其他的修改数组的操作时,这个参数就会加1。
在单线程中,这个当然是不会出错的。
但是在多线程中,我们知道如果我们在遍历时,可能会抛出ConcurrentModificationException
这个异常就是提醒我们在遍历时,有其他的线程对数组进行了修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

比如这个forEach方法,在进行操作前先记录当前的modCount大小,最后操作完比对现在的modCount,如果不一样,那么就抛出异常。

RandomAccess接口

这个接口是空的,只是做一个标记的作用。

1
2
public interface RandomAccess {
}

什么标记呢,就是对实现了这类接口的类进行遍历时,

1
2
for (int i=0, n=list.size(); i &lt; n; i++)
list.get(i);

1
2
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();

如果第一种遍历方式要比第二种快,那么他就应该实现RandomAccess接口,这样我们在使用的时候,在特定场景可能会根据是否实现了RandomAccess来进行遍历。
这个我们在比较LinkedList的时候就能理解了。
因为LinkedList是链表的方式,如果我们使用第一种遍历,那相当于每次get都从头开始找了。
所以LinkedList就不能实现这个接口。
而ArrayList底层是数组,所以直接get反而更快一点,而用第二种还需要进行一个SubList的构造。

其他

1
2
3
4
5
6
7
8
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

这个方法很有意思,因为我们的扩容机制不是一个一个的增加的,一下子增加原来的3/2大小。
如果我们不再往里面增加元素的话,那么多出来的就很浪费。
这个方法就是去除多余的没设置值的空间。

1
2
3
4
5
6
7
8
9
10
11
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);
}
}

clone方法可以看到,做的是浅拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

这个方法,可以看到开销还是挺大的,那个注释很有意思,把后面缩小之后的引用置位null。
如果不置位null,仅仅是size-1的话,那么位于size位的对象无法被GC收集。
这样就会造成内存泄漏。

1
2
3
4
5
6
7
8
9
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

clear方法并没有释放底层的数组,只是把每个引用置位null