Java源码之ArrayList

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/08/22/Java源码之ArrayList/

访问原文「Java源码之ArrayList

关于ArrayList

相信ArrayList是小伙伴们在Java开发中经常会使用的类之一。那么ArrayList究竟是一个什么类呢。大概来说它是List接口的可调整大小的数组实现。 实现所有可选列表操作,并允许所有元素,包括null。除了实现List接口之外,他的类还提供了一些方法来操纵数组的内部大小来存储列表。 也就是说ArrayList内部是由数组实现,往ArrayList中放置元素也是默认按照先后顺序进行放置;它的大小是可调整的,不用像使用数组一样担心它不够存放数据(这里排除内存限制)。

总的来说ArrayList不论从使用还是理解上都是比较简单的,那么让我们来分析一下其中的一些关键方法吧。

关键成员变量

下面列出了ArrayList的关键成员变量,数量并不多,可以看到元素在ArrayList中是存储在数组中的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 存储元素的数组缓冲区
* ArrayList的容量是此数组缓冲区的长度
* 空ArrayList的elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* 当插入第一个元素后大小为DEFAULT_CAPACITY
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList的大小,即存储元素的数量
*
* @serial
*/
private int size;

插入方法

最简单的方法就是add一个元素,下面是这个方法的源码。这个方法比较简单,但我们看第一步是ensureCapacityInternal,这个方法是检测新size是否超出目前可容纳的最大值,超出的话需要扩展容量,最后走到grow方法中,具体代码下面已经给出。需要注意的是modCount++这一句,这个变量表示此列表已被结构修改的次数,结构修改是改变列表大小的那些修改,或以其他方式扰乱它,使得正在进行的迭代可能产生不正确的结果。也就是说在迭代的时候进行结构修改将导致程序出错。

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
/**
* 在列表的最后插入元素
*
* @param 即将插入的元素
* @return true
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 增加modCount
elementData[size++] = e;
return true;
}
// 检测是否超出目前可容纳的最大值
private void ensureCapacityInternal(int minCapacity) {
// 放入第一个值时minCapacity设置为DEFAULT_CAPACITY
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 当所需最小容量大于目前容量的话,需要增加容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 增加容量以确保它至少能够容纳最小容量参数指定的元素数量
*
* @param minCapacity 所需的最小容量
*/
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通常接近大小
elementData = Arrays.copyOf(elementData, newCapacity);
}

另外一个常用的插入就是在指定位置插入,例如在首位(index为0)的位置插入等等。下面是这部分的源码,比较好理解,关键部分已经加上注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 在此列表中的指定位置插入指定的元素。
* 将当前位于该位置的元素(如果有)和任何后续元素(向其索引添加一个)移动。
*
* @param index 指定元素要插入的索引
* @param element 插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 检测index的合法性,不行小于0或者大于size
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将index位置以及其后所有元素的索引增加1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// index位置放入元素
elementData[index] = element;
// 大小加1
size++;
}

其次还有addAll方法,分别为向列表最后插入和指定位置插入两个方法,这两个方法都是在add方法上延伸出来的,很好理解,不再赘述。

删除方法

删除元素也是我们经常使用的方法,首先看按照索引删除元素。下面的代码注释已经比较明白,需要注意的是rangeCheck这个方法只检测index是否大于等于size,不检测是否小于0。这是因为是否小于0在访问数组时进行检测。

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
/**
* 删除该列表中指定位置的元素。
* 将任何后续元素移动到左侧(从其索引中减去一个元素)。
*
* @param index 要删除的元素的索引
* @return the element 删除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
// index范围检测
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// index以及之后元素的索引减1
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 检查给定的索引是否在范围内。 如果没有,则抛出适当的运行时异常。
* 该方法不检查索引是否为负数:它始终在数组访问之前立即使用,如果index为负,则抛出ArrayIndexOutOfBoundsException。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

下面是根据删除指定元素。指定的元素可以为null,在找到指定元素的位置(索引)后,通过fastRemove删除元素。

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
/**
*
* 如果存在制定元素则从这个列表中删除第一个出现的指定元素。
* 如果列表中不包含元素,那么它是不变的。
*
* 如果该列表包含指定的元素,返回true.
*
* @param o 要删除的元素
* @return 包含这个元素则返回true
*/
public boolean remove(Object o) {
// 如果o为null,则删除第一个为null的元素
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;
}
// 不包含各种检测的从指定索引位置删除元素
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
}

还有用的比较多的是批量删除,以其中一个方法为例,如下。可见这个函数交由方法removeAll处理。在removeAll中,并没有删除,而是遍历每一个元素,判断是否需要保留,不需要保留的会被需要保留的覆盖。可能这句话不好理解,可以看一下具体的代码。

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
/**
* 从这个列表中删除包含在指定集合中的所有元素。
*
* @param c 包含要从这个列表中删除的元素的集合
* @return {@code true} 如果列表的数据被修改
* @throws ClassCastException 如果该列表中的元素类与指定的集合不兼容
* @throws NullPointerException 如果该列表包含一个空元素,并且指定的集合不允许null元素
*/
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
/**
* complement为false表示删除,为true表示保留
*
*/
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;
}
// w不为size,表示这个列表有修改,则需要修改size等属性
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;
}

查询方法

查询方法是必须了解的,因为我们存起来也是为了获取。这个方法非常的简单,只做简单的参数检验,然后返回对应下标的元素。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 返回列表中指定位置的元素
*
* @param index 返回元素的索引
* @return 元素在这个列表中的指定位置
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}

总结一下

基本上把ArrayList涉及的关键函数都做了详细说明。其余的一些都比较好理解了。