Java源码阅读之ArrayList - JDK1.8

文章目录
  1. 1. 前言
  2. 2. 基本介绍
    1. 2.1. 常量
    2. 2.2. 成员变量
    3. 2.3. 构造函数
  3. 3. 功能
  4. 4. 总结

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方,欢迎指正~
转载请注明出处https://blog.lzoro.com

前言

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

而且,只有感兴趣才能驱动你继续下去,不然读源码,写解析博客这么高(Ku)大(Zao)上的事,是很难坚持的。

详细地写一篇源码解析博客少则半天一天,比如本篇,多则几天,比如红黑树在Java - HashMap中的应用,又要画图又要注释,还要排版,时不时要加点表情,开个车什么的,你说要是没兴趣,怎么坚持呢,还不如吃个鸡实在(啊,暴露了我是吃鸡选手)。

闲话少说,打开你的IDE,挽起袖子,开撸代码,加上注释,总计1461行代码。

基本介绍

常量

相比HashMap来说,ArrayList的常量算是短小精悍了,只有几个。

其中包含一个默认容量和两个空数组等,如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 /**
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空数组共享实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 缺省大小的空数组共享实例
* 与 EMPTY_ELEMENTDATA 区分开来,以便知道第一个元素添加时如何扩容
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 最大可分配大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成员变量

成员变量也是简单到令人发指,一个负责实际存储的缓冲数组和一个表示大小的变量。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 实际负责存储的缓冲数组
* ArrayList的容量就是缓冲数组的长度
*
* 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一个元素添加时将会以默认容量扩容
*/
transient Object[] elementData; // 非私有,以简化嵌套类的访问

/**
* 大小
*/
private int size;

构造函数

三个构造函数,分别是利用默认初始容量/给定初始容量/给定特定集合来构造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
/**
* 根据给定初始容量构造一个空的list
*
* @param initialCapacity list的初始容量
* @throws IllegalArgumentException 当给定的初始容量非负时抛异常
*/
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);
}
}

/**
* 按默认初始容量(10)构造一个空的list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
* 根据给定集合构造一个list,将按集合迭代的顺序存储
*
* @param c 集合
* @throws NullPointerException 集合为null时抛异常
*/
public ArrayList(Collection<? extends E> c) {
//集合转数组后赋值给缓冲数组
elementData = c.toArray();
//判断大小
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//c.toArray方法可能不会返回Object[]形式的数组
//下面做一层判断
if (elementData.getClass() != Object[].class)
//做拷贝操作
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果是空集合,则替换成共享空数组实例
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

功能

看完了基本介绍,应该会觉得Just so so。

接下来就要逐一介绍各个功能的具体实现了。

ArrayList中,我们常用的功能有add/remove/get等。

无外乎增删改查,下面一一介绍~

add

在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
/**
* 从尾部添加指定元素
*
* @param e 元素
* @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;
}

/**
* 在指定位置插入元素
* 移动当前位置的元素 (如果存在) 和后继元素到右边
*
* @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进行数组复制
//目的是为了空出指定位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指定位置上放入指定元素
elementData[index] = element;
//容量+1
size++;
}

在添加的元素的时候,有一个关键方法ensureCapacityInternal是来确保内部缓存数组的容量,当容量不够时进行扩容,下面具体看下这个方法的调用链

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
/**
* 私有方法
*/
private void ensureCapacityInternal(int minCapacity) {
//判断是否是默认空实例,如果是的话,计算扩容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//调用ensureExplicitCapacity
ensureExplicitCapacity(minCapacity);
}

...

private void ensureExplicitCapacity(int minCapacity) {
//操作计算+1
modCount++;

// overflow-conscious code
//只有当容量不够时才扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/**
* 缓冲数组扩容以确保能够存储给定元素
*
* @param minCapacity 期望的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
//现有元素长度
int oldCapacity = elementData.length;
//新容量为 旧容量 + 旧容量的一半
//如 10 + 5 = 15
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:
//最小扩容容量通常是接近size的,所以这是一场胜利
//这么臭美的吗
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;
}

set

这里的set其实可以理解为修改,将指定位置的元素替换为新元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 修改指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//范围检查
rangeCheck(index);
//取出旧值用以返回
E oldValue = elementData(index);
//放入新的值
elementData[index] = element;
return oldValue;
}

remove

数组的移除和添加一样,也分为几种方式

  • 根据下标移除
  • 根据对象移除
  • 根据集合移除
  • 根据过滤器移除
  • 根据范围移除(受保护的方法)
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
/**
* 删除指定位置的元素,后继元素左移(前移)
*
* @param index 下标
* @return the 被移除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下标检查
rangeCheck(index);
//操作计数 + 1
modCount++;
//获取指定位置的元素(用以返回)
E oldValue = elementData(index);

int numMoved = size - index - 1;
//用system.arraycopy的方式移动元素
//相当于是index位置后的元素前移
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最后一个数组元素引用置为null,方便GC
elementData[--size] = null; // clear to let GC do its work
//返回
return oldValue;
}


/**
* 当元素存在的时候,删除第一个找到的指定元素
*
* 如果元素不存在,则list不会变动
*
* @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) {
//o是否是null元素(数组允许存储null)
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//调用内部的fastRemove方法,后面分析
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
//这里跟上面不一样的是,是用equals来比较,而不是比较地址
if (o.equals(elementData[index])) {
//同上
fastRemove(index);
return true;
}
}
return false;
}

/**
* 根据给定的集合,将list中与集合相同的元素全部删除
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//调用批量删除,后续分析
return batchRemove(c, false);
}


/**
* 通过一个过滤器接口实现,来实现删除
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
//用bitset来存储哪些下标对应的元素要删除,哪些下标对应的元素要保存
//这里不清楚BitSet的用法的,可以先行了解一下
final BitSet removeSet = new BitSet(size);
//判断并发修改用
final int expectedModCount = modCount;
final int size = this.size;
//按顺序遍历且没有并发修改
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//利用过滤器匹配元素,如果匹配,则删除计数+1,并将下标进行存储
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//判断是否存在并发修改
if (modCount != expectedModCount) {
//抛出并发修改异常
throw new ConcurrentModificationException();
}

// shift surviving elements left over the spaces left by removed elements
//判断是否有要删除的元素
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//下一个要保存的元素
i = removeSet.nextClearBit(i);
//存放到新数组
elementData[j] = elementData[i];
}
//把实际要保存的元素之后的全部置为null,用以GC
//实际上,上面的操作已经将要保留的元素全部前移了,后面的元素都是不保留的,所以要置为null来帮助gc
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//设置size
this.size = newSize;
//判断是否并发修改
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}

return anyToRemove;
}


/**
* 删除list中指定范围的元素
*
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
//范围删除时,其实数组被分成三个部分
//分别为[保留区 - 删除区 - 保留区]
//实际操作,则是计算出最后那部分保留区的长度
//利用arraycopy拷贝到第一个保留区的后面
//然后置空多余部分,帮助GC
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);

// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}

//最后,来看一下批量删除这个私有方法

/**
* 批量删除
*/
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++)
//这里其实有可能抛异常的
//complement
//为false时,则证明下标r的元素不在删除集合c中,所以这个时候存储的是不删除的元素

//为true时,则证明下标r的元素在删除集合c中,所以这个时候存储的是要删除的元素

//这个布尔值的设计很巧妙。所以本方法可以供removeAll、retainAll两个方法来调用
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;
}
//如果有需要删除的元素的话,则证明有一部分位置需要只为null,来帮助GC
//并且设置是否有修改的标志为true
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;
}

至此,删除相关的方法都已经分析完毕。

有几个比较有意思的应用

  • BitSet 标志哪些下标要删除,哪些不删除
  • batchRemove 方法中的布尔值很巧妙

get

作为数组型的list,获取方法时比较简单的,只需要根据给定下标,读取指定下标的数组元素即可。

1
2
3
4
5
6
public E get(int index) {
//范围检查
rangeCheck(index);

return elementData(index);
}

contains

当前list是否包含指定元素

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
/**
* 返回布尔值表示是否包含
*/
public boolean contains(Object o) {
//实际上是判断下标是否存在
return indexOf(o) >= 0;
}

/**
* 指定元素在list中首次出现的下标,不存在则返回-1
*/
public int indexOf(Object o) {
//通过遍历的方式查找
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;
}

//另外,还有一个,最后一次出现的下标

public int lastIndexOf(Object o) {
//跟上面的类似,只不过遍历方式是从尾部开始
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

clear

清空缓冲数组。

1
2
3
4
5
6
7
8
9
10
11
public void clear() {
//修改计数 + 1
modCount++;

// clear to let GC do its work
//全部置为null,帮助GC
for (int i = 0; i < size; i++)
elementData[i] = null;
//size设置为0
size = 0;
}

以上相关方法基本都已经介绍完毕。

总结

Array相比其他集合框架,如Map、Set之类的,还是比较简单的。

只需要了解相关方法的应用和原理,注意下标越界问题,以及内部的缓冲数组是如何扩容的,基本上就OK了。

溜了溜了。有帮助的话给格子点个赞呗~~3Q~

分享到