java8集合框架(七)-List的实现类(ArrayList)

java8集合框架(七)-List的实现类(ArrayList)

今天是中秋节,祝大家中秋快乐。然分析源码的任务是不能停的,大业尚未成功,同志仍需努力。前5篇已经完成了Map接口的全部实现类的源码分析,现在继续分析List接口的实现类。List接口在日常的开发过程中,使用非常频繁,是存放有序的可重复的元素的容器。JDK中的实现有两种。一种是ArrayList,另一种是LinkedList。前者提供更好的随机读,所以使用的会更多一些。而本篇,就来分析它的实现方式。

Note:本篇源码分析基于jdk1.8版本

ArrayList

ArrayList的名字就可以看出它的特色,核心数据结构是数组。被认知为可自动扩容的数组实现。数组提供基于索引位的常数时间复杂度的读取和存储效率。另外ArrayList非线程安全,接受null值。实现了RandomAccess接口,在遍历时可以优化算法,以随机访问替代迭代器访问。

数据结构

ArrayList的数据结构较为简单。只是区分了容量为0的共享数组,这在扩容的时候会区别对待。

1
2
3
4
5
6
7
8
9
10
//没有设置容量,默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//显式设置容量为0的共享对象
private static final Object[] EMPTY_ELEMENTDATA = {};
//没有设置容量的共享对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//元素实际存放容器
transient Object[] elementData;
//实际元素个数
private int size;

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//申请空间,没有延迟
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//长度为0的数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//小于0抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
//使用前不会申请空间,有点延迟初始化的味道
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

说明:显式设置容量为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
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
68
69
70
71
72
73
74
75
76
77
78
79
//添加一个元素
public boolean add(E e) {
//检查扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//在指定位置添加一个元素
public void add(int index, E element) {
//检查index是否越界
rangeCheckForAdd(index);
//检查扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将elementData数组的index位置起,复制到index+1位置起,
//长度为size-length。最终将index位置空出来。
//System.arraycopy是native方法,注释上说明如果src和dest是同一个数组,实现的内部会产生一个临时数组以过渡。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//add指定的index不能超过size,即数组不会出现空窗
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//修改指定位置的元素
public E set(int index, E element) {
//越界检查
rangeCheck(index);
E oldValue = elementData(index);
//修改数组相应位置的值
elementData[index] = element;
return oldValue;
}
//删除指定位置的元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//如果删除的不是最后一个元素,要将数组往前copy
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;
}
//删除指定元素
public boolean remove(Object o) {
//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;
}
//所谓的fastRemove就是不做index检查,不返回被删除的元素。
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
}

说明:ArrayList的增删改很简单,也很容易理解。这里要注意的是System.arraycopy,这个函数是native方法,处理数组元素的批量移动性能很好。以后自己的代码也可以借鉴。

扩容

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
//确保能容纳下minCapacity个元素
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//add的操作都会调用
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//扩容
private void grow(int minCapacity) {
//老容量
int oldCapacity = elementData.length;
//新容量为之前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//但是不得小于minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//而超过MAX_ARRAY_SIZE时,直接设置Integer.MAX_VALUE为新容量
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;
}

说明:都说ArrayList的内部是动态数组,其实就是有自动扩容机制。每次调用add都会检查是否需要扩容。在分析数据结构的时候,有两个空数组。它们对应的扩容策略是不一样的。简单来说,EMPTY_ELEMENTDATA扩容后的最小容量没有限制,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA扩容后容量至少为10。一般情况下扩容1.5倍。

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//随机查找,常数时间
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//指定元素的索引
public int indexOf(Object o) {
//循环遍历对比,O(n)
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

缩容

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);
}
}

说明:有扩容还提供了缩容方法,可以将数组长度缩为元素个数,以达到节省空间的目的。

List2Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//桥梁
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//支持泛型
public <T> T[] toArray(T[] a) {
//a的长度不够,那么就当a送了一个类型信息
if (a.length < size)
// Make a new array of a's runtime type
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//否则直接往a填充
System.arraycopy(elementData, 0, a, 0, size);
//这里是何意?
if (a.length > size)
a[size] = null;
return a;
}

说明:这是ListArray的桥梁方法,不带参数就直接返回elementData的拷贝。泛型版本的参数数组长度小于size的时候,权当携带了类型信息,否则直接填充数据于参数数组。

ListIterator

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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;
//到尾了返回false
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();
//下一索引位+1
cursor = i + 1;
//老索引位赋值给lastRet
return (E) elementData[lastRet = i];
}
//遍历时删除
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//调用ArrayList的删除
ArrayList.this.remove(lastRet);
//维护索引位
cursor = lastRet;
lastRet = -1;
//调整ModConut,防止fast-fail
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//fast-fail
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;
}
@SuppressWarnings("unchecked")
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的set
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
//调用ArrayList的add,调整索引
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}

说明:ListIterator相较于Iterator增加了遍历和增改签名(删原本就有)。Itr实现了Iterator接口,ListItr继承Itr实现了增加的遍历签名。

排序

1
2
3
4
5
6
7
8
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}

说明:直接对内部数组排序

总结

ArrayList是平时使用最多的List实现。它的内部结构简单,基于索引位的读写均为常数时间的复杂度。通过上面的分析也能看到,在删除和扩容的时候常常需要伴随着数组复制。尽管System.arraycopy的性能很好,但还是有消耗的。所以如果是有频繁增删的需求,且看下篇LinkedList的源码分析。

参考

RandomAccess 接口使用

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。