Java常用类源码——ArrayList源码解析

ArrayList

ArrayList是我们经常使用的一个类了,是属于List接口的那一块,那么,我们就来看这个类的源码吧!

ArrayList签名

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

从上面我们知道ArrayList是实现了List、RandomAccess ,Cloneable,Serializable接口的一个类。

那么它的成员属性有哪些呢?如下的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 默认初始化对的容量是10
private static final int DEFAULT_CAPACITY = 10;
// 当初始化容量为0 时,构造一个这样的空的Object类型的数组,下面的构造方法中会有提到
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
//真正存储元素的容器,就是一个Object类型的数组,当
transient Object[] elementData; // non-private to simplify nested class access
// 标识数组的大小
private int size;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
// 指定容量大小的构造函数
public ArrayList(int initialCapacity) {
// 大于0的时候创建新的数组对象
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 指定大小为0 的时候,引用一个空数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
//当没有进行初始化容量大小的时候,将引用默认的空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//传入一个集合的时候
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;
}
}

在利用Collection来构造的时候,有一个确认对象类型的检验,如果集合中的对象不为Object类型,那么就利用Array类的静态方法进行拷贝,这个给出的注释是调用toArray()方法时可能出现问题。看来API开发人员想的还是比较的细致的。当转换的数组为空的时候,ArrayList并没有使用转换的空结果,而是依然使用自己构造的空数组。

主要方法

Add()

1
2
3
4
5
6
7
8
9
10
11
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

ArrayList的添加元素,是添加到数组的末尾的,并且是永远返回一个true, 这是说明这个向容器中添加的时候是永远不会出现错误的了哦!
再来看add()方法中的ensureCapacityInternal

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//将默认的容量大小和向里面再添加一个元素是的大小进行比较,选择其中较大的。
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}

这个方法是非常重要的,这里面是确保ArrayList容量能否再增加一个,那里面是怎么做的呢? 通过上面的代码知道ensureCapacityInternal 这个方法中首先是判断当前的对象数组是不是默认的空数组,如果是的话,就在默认容量(10)和需要的容量中取一个最大值,然后把得到的这个值传递给下一个函数ensureExplicitCapacity,所以在这里就可以解答上面 transient Object[] elementData上面的解释了,在创建一个空TreeMap,如果使用的默认的构造方法,那么elementData就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当首次插入对象的时候,最大值的时候一定是10,实际上就相当于构造了一个长度为10的对象的数组。

1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

ensureExplicitCapacity这个方法第一行先不管是干什么的,看后面的,就是判断需要的容量和现在用来存储的对象的数组(elementData)哪个更大,如果现在已经有的不够大了,那就扩容!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
// 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;
}

上面的这段代码进行了扩容的操作,可以看出扩容是通过newCapacity = oldCapacity + (oldCapacity >> 1); 这段代码实现的,这段代码实际是上就是将原来的容量变为原来的1.5倍。

但是要对扩容后的容量进行检验,共有两种可能:

  1. 得到的容量比需要的容量小,为什么会出现这样的情况呢,溢出了呗
  2. 得到的容量超过了规定的最大容量,进入hugeCapacity如果需要的容量小于0,抛出内存溢出异常,如果需要的容量比规定的最大容量大,那么最大容量只能是 Integer.MAX_VALUE.

最后将elementData通过Array的复制拷贝方法进行了扩容。以上就是整个添加新的元素的过程。从这个过程可以看出,ArrayList也并不是无限大的,他指定了最大容量是Interger.MAX_VALUE-8,再大的话,实际最大只能是Integer.MAX_VALUE这个值了。

add(int, E)

这个方法是在指定的位置上插入元素element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

首先进行的是合法性的检查,然后再进行容量的检验并扩容。
第三行是进行元素的复制,复制的方法是一个native方法,其实原理就是将原来index位置开始的元素,依次向后移动一位,通过openjdk,可以知道是代用了C语言和C++的代码。并且System.arraycopy()方法使用的是C语言中的-------------------- 方法。这个方法是比较高效的,所以在Java的源码中,有拷贝的地方几乎都是有它的身影的。add()方法最后将元素放入指定的位置中,元素的数量进行增加。

Remove方法

remove(int index)

从指定的位置删除元素,实现原理就是把index后面的数据都向前移动,时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}

  1. 第一行就是检验index的返回,有人会问为什么不检验负数的情况。本人亲自试验了一下,如果index是负数的话,第一行是可以正确执行的,但是在elementData(index)这样地方就会抛出java.lang.ArrayIndexOutOfBoundsException: -1即 数组越界异常,其实个人觉得,如果没有第一句 检验,仍然会抛出数组越界异常。只不过多了第一行的话,抛出的异常就是java.lang.IndexOutOfBoundsException: Index: 2, Size: 2,而且会打印出错误信息。又有哪个Java程序员不喜欢看到更详细的异常信息呢?
  2. 计算移动量,如果要删除的元素不是最后以一位,就要进行移动。
  3. 将移动后的数组末尾赋值null。这里有一句注释,让GC去回收,这个是一种释放内存的方式。赋值为null,的确是不做任何的处理更加的有效,因为Java的垃圾回收机制是通过一些垃圾回收方法来确定对象是否回收,其中的一个算法是”可达性分析”,如果没有其他的引用,即到”Root”不可达的话,是非常容易被垃圾回收机制回收的(这里大概讲一下Java的垃圾回收机制,更详细的请看我的关于Java垃圾回收机制原理的博客)。

remove(Object o)

删除指定的元素,仅仅删除符合条件的第一个元素,如果不存在,返回false即删除失败

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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;
}

分析这段代码,首先对o进行了非空处理。如果不进行这样的处理,将会引发o.equals的空指针异常。这个是非常常见的处理方式在这if else语句块中,都用了fastRemove(index) 听上去挺高大上的,快速删除的,其实看了源码就知道,很简单。

1
2
3
4
5
6
7
8
9
10
11
12
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}

这不就是remove(index)方法的后半部分吗?为何不直接调用这个方法呢?肯定是为了提交一点点效率嘛,这毕竟是Java API嘛.

removeAll(Collection<?> c)

在集合中,删除与Collection中元素相等的元素

1
2
3
4
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

第一行是java1.7新出的工具类,用于检验非空的,如果为空,抛出空指针异常。
接下来就来看下面的这个方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

下面来分析一下这段代码。首先对集合中的对象数组进行了一次复制,然后将数组中的元素依次与collection进行对比。try{}块的结果就是得到了一个数组,数组前w位元素或与collection相同(complement=true的时候)或不同(complement=false)。
下面来看finally,先来看第二个if{}代码块,它的作用就是把数组中w以后的元素全部变为null值,让gc来回收。现在回到finally的第一个if中,看条件(r != size),似乎永远不会满足这个条件吧。上面的for循环一直r++啊,可是别忘了,c.contains(elementData[r])这句话是有可能抛出异常的,如果一旦类型不匹配,就会抛出异常 进入finally中。
这个方法,如果没有删除任何数据,那么将会返回false。

现在我们再来看return batchRemove(c,false);这行的含义吧。它指定了第二个参数为false,所以在batchRemove()保留下来的都是与collection中不同的元素。相同的元素都被删除了。这样就达到了removeAll(Collection<?> c)的目的。

迭代器

迭代器可是操作ArrayList的神器,在ArrayList内部通过内部类的形式实现了Iterator接口,完成对ArrayList的操作,下面就看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* An optimized version of AbstractList.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;
public boolean hasNext() {
return cursor != size;
}
@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];
}
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();
}
}
@Override
@SuppressWarnings("unchecked")
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++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

这个类并不长,让我们来分析一下
(1) 属性
a 游标
int cursor; 我们知道iterator是始终向前走的,就是这个游标始终在++的原因
b 末尾标识
int lastRe 标识了最后一个返回的元素的索引位置,-1代表这个元素不存在
C 操作数标识
int expectedModCount = modCount; 这个非常重要,它用来校验在使用iterator期间,是否存在非Iterator的操作对ArrayList进行了修改。
(2)checkForComodification 方法
这个方法很简单,但是可以看到在这个内部类中,几乎所有方法都在调用它。它所做的工作就是校验在使用iterator期间,是否存在非Iterator的操作对ArrayList进行了修改。
在ArrayList中,有很多操作都修改了一个变量,modCount。每次进行操作,modCount都在++。前面一直不理解这个有什么用,在这看到了它的用意。Iterator的游标特性决定了它对ArrayList中元素在这一时刻的位置很敏感,如果当前游标在index位置,而有其他操作在index-1的位置上插入了一个元素,那么调用iterator的next()方法,返回的还是当前这个元素,这样就乱了。为了避免这个情况发生,需要在这个期间把ArrayList“锁住“。它并没有实现真正的锁,所以采用了这个校验的方式。
(3)next()
返回当前游标位置的元素,这里面第一个if判断的条件很有意思。因此游标前移,当移动到一个不存在数据的地方,它抛出了异常。而并没有返回null。这就是我们为什么在使用iterator的时候不能用(null==iterator.next())来判断的原因。而是在要每次循环开始的时候判断iterator.hasNext()。
(4) remove()
删除lastRe 所标识位置的元素。我们可以把它理解为当前元素。在try前面有一个校验,保证元素没有被改动过,要不就删错了。
在try{}语句块中,首先删除了lastRe标识的元素,然后让游标指向了这个位置。我们知道在删除元素以后,这个位置有了新的元素,这样再次调用next()的时候不会出现空指针异常,更不会跳过一个元素。
最后expectedModCount = modCount;这句相当于释放了锁。也是在表示,在我Iterator的地盘,只有我能够去修改mod,别人动了就不行!``

总结

  1. ArrayList是用Object数组来实现的,所谓的动态扩容,实际上是不断的产生新的数组,然后进行复制。
  2. 在使用ArrayList插入大量元素时,应该有选择的申请一个容量,而不是使用默认的容量,因为扩容是会消耗很多的时间的。
  3. ArrayList不是线程安全的,它的操作中没有使用同步的方法,如果想使用线程安全的,可以用Vector,也可以使用Collections.synchronizedList 来创建线程安全的list。
坚持原创技术分享,您的支持将鼓励我继续创作!