logo头像
Snippet 博客主题

深入分析ArrayList源码

1. ArrayList简述

1.1 ArrayList介绍

List 接口下的可调整大小的数组实现。
数组: 一旦初始化长度就不可以发生改变

1.2 数组结构介绍

  • 增删慢:每次删除元素,都需要更改数组长度、拷贝以及移动元素位置。
  • 查询快:由于数组在内存中是一块连续空间,因此可以根据地址+索引的方式快速获取对应位置上的元素。

1.3 ArrayList继承体系

ArrayList继承体系图

1.3.1 RandomAccess标记性接口

1.3.1.1 介绍

  • 标记接口由 List 实现使用,以表明它们支持快速(通常为恒定时间)随机访问。
    此接口的主要目的是允许通用算法更改其行为,以便在应用于随机访问列表顺序访问列表时提供良好的性
    能。
  • 用于操纵随机访问列表的最佳算法(例如 ArrayList )可以在应用于顺序访问列表时产生二次行为(如
    LinkedList )。
  • 鼓励通用列表算法在应用如果将其应用于顺序访问列表之前提供较差性能的算法时,检查
    给定列表是否为 instanceof ,并在必要时更改其行为以保证可接受的性能。
  • 人们认识到,随机访问和顺序访问之间的区别通常是模糊的。 例如,一些 List 实现提供渐近的线性访问时
    间,如果它们在实践中获得巨大但是恒定的访问时间。

1.3.1.2 源码

1
2
3
4
5
package java.util

/** 仅作为标记接口,无任何内容 */
public interface RandomAccess {
}

1.3.1.3 演示

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
/**
* @projectName: ltmf
* @className: com.ltmf.arraylist.RandomAccessTest
* @description: RandomAccess演示
* @author: tong.li
* @createTime: 2020/5/18 16:09
* @version: v1.0
*/
public class RandomAccessTest {

@Test
public void randomAccessForArrayList() {
// 创建ArrayList集合
List<String> list = new ArrayList();
// 添加10W条数据
for (int i = 0; i < 100000; i++) {
list.add(i+"a");
}
System.out.println("----通过索引(随机访问:)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问: "+(endTime-startTime));
System.out.println("----通过迭代器(顺序访问:)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()){
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: "+(endTime-startTime));
}


@Test
public void randomAccessForLinkedList() {
// 创建ArrayList集合
List<String> list = new LinkedList();
// 添加10W条数据
for (int i = 0; i < 100000; i++) {
list.add(i+"a");
}
System.out.println("----通过索引(随机访问:)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问: "+(endTime-startTime));
System.out.println("----通过迭代器(顺序访问:)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()){
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: "+(endTime-startTime));
}
}
1
2
3
4
5
6
7
8
9
10
# randomAccessForArrayList()第一次运行,访问速度差不多
----通过索引(随机访问:)----
随机访问: 1
----通过迭代器(顺序访问:)----
顺序访问: 1
# randomAccessForArrayList()第二次运行,访问速度有差距
----通过索引(随机访问:)----
随机访问: 4
----通过迭代器(顺序访问:)----
顺序访问: 6
1
2
3
4
5
# randomAccessForLinkedList()第一次运行,随机访问很慢
----通过索引(随机访问:)----
随机访问: 26497
----通过迭代器(顺序访问:)----
顺序访问: 3

1.3.2 Serializable标记性接口

1.3.2.1 介绍

  • 类的序列化由实现java.io.Serializable接口的类启用。
  • 不实现此接口的类将不会使任何状态序列化或反序列化。
  • 可序列化类的所有子类型都是可序列化的。
  • 序列化接口没有方法或字段,仅用于标识可串行化的语
    义。
  • 序列化的意思是将对象的数据写入到文件(写对象),而反序列化的意思是将文件中对象的数据读取出来(读对象) 。

1.3.2.2 源码

1
2
3
4
5
package java.io

/** 仅作为标记接口,无任何内容 */
public interface Serializable {
}

1.3.2.3 演示

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
/**
* @projectName: ltmf
* @className: com.ltmf.arraylist.SerializableTest
* @description: Serializable序列化演示
* @author: tong.li
* @createTime: 2020/5/18 15:03
* @version: v1.0
*/
public class SerializableTest {

public static void main(String[] args) throws IOException, ClassNotFoundException {
Goods apple = new Goods();
apple.setName("Apple");
apple.setMoney(new BigDecimal("5.8"));
System.out.println(apple);
//创建对象操作流 --> 序列化
ObjectOutputStream oos = new ObjectOutputStream(new
FileOutputStream("./goods.txt"));
//创建集合,且添加学生对象
ArrayList<Goods> list = new ArrayList();
list.add(apple);
list.add(new Goods("Watermelon ",new BigDecimal("3.58")));
// 将集合写入到文件
oos.writeObject(list);
//创建对象输入流 --> 反序列化
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("./goods.txt"));
//读取数据
Object o = ois.readObject();
//向下转型
ArrayList<Goods> al = (ArrayList<Goods>) o;
//遍历集合
for (int i = 0; i < al.size(); i++) {
//根据索引取出集合的每一个元素
Goods goods = al.get(i);
System.out.println(goods);
}
}

static class Goods implements Serializable {

private String name;
private BigDecimal money;

public Goods() {
}

public Goods(String name, BigDecimal money) {
this.name = name;
this.money = money;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public BigDecimal getMoney() {
return money;
}

public void setMoney(BigDecimal money) {
this.money = money;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (this.money == null) {
this.money = BigDecimal.ZERO;
}
sb.append("[").append("name = ").append(this.name).append(", ").append("money = ").append(this.money.setScale(2,BigDecimal.ROUND_HALF_UP)).append("]");
return sb.toString();
}

}
}
1
2
3
4
# Goods实现Serializable接口执行结果
[name = Apple, money = 5.80]
[name = Apple, money = 5.80]
[name = Watermelon , money = 3.58]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Goods未实现Serializable接口执行结果
Exception in thread "main" java.io.NotSerializableException: com.ltmf.arraylist.SerializableTest$Goods
at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1184)
at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:348)
at java.util.ArrayList.writeObject(ArrayList.java:766)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:498)
at java.io.ObjectStreamClass.invokeWriteObject(ObjectStreamClass.java:1140)
at java.io.ObjectOutputStream.writeSerialData(ObjectOutputStream.java:1496)
at java.io.ObjectOutputStream.writeOrdinaryObject(ObjectOutputStream.java:1432)
at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1178)
at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:348)
at com.ltmf.arraylist.SerializableTest.main(SerializableTest.java:31)

1.3.3 Cloneable标记性接口

1.3.3.1 介绍

  • 一个类实现Cloneable接口来指示Object.clone() 方法,该方法对于该类的实例进行字段的复制是合
    法的。
  • 在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛
    出。
  • 简言之,克隆就是依据已经有的数据,创造一份新的完全一样的数据拷贝。
  • 被克隆对象所在的类必须实现 Cloneable 接口 ,必须重写 clone 方法 。
  • clone的最顶层是Object对象的方法。

1.3.3.2 源码

1
2
3
4
5
package java.lang;

/** 仅作为标记接口,无任何内容 */
public interface Cloneable {
}

1.3.3.3 演示

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
/**
* @projectName: ltmf
* @className: com.ltmf.arraylist.CloneableTest
* @description: Cloneable克隆演示
* @author: tong.li
* @createTime: 2020/5/18 15:22
* @version: v1.0
*/
public class CloneableTest {

public static void main(String[] args) throws CloneNotSupportedException {
ArrayList<String> list = new ArrayList<String>();
list.add("君子坦荡荡,小人常戚戚");
list.add("大丈夫,行不更名,坐不改姓");
list.add("明人不做暗事,真人不说假话");
list.add("现实中,我活得那么真实");
list.add("虚拟世界里,也从不虚伪");
list.add("不是说我这个人有个性,而是说我这个人就是这么与众不同");
list.add("我就是我,今天晚上不一样的烟火!");
//调用方法进行克隆
Object o = list.clone();
// false表示两个不同的对象
System.out.println("-------------------简单示例---------------------------");
System.out.println("o == list: " + (o == list) );
System.out.println(o);
System.out.println(list);
System.out.println("-------------------克隆后修改值前打印---------------------------");
HashMap<String, String> appleAddress = new HashMap();
appleAddress.put("province","Shaanxi");
appleAddress.put("city","Luochuan");
Goods apple = new Goods("Apple", new BigDecimal("5.8"), appleAddress);
Goods clone = apple.clone();
System.out.println("apple == clone: " + (apple == clone) );
System.out.println(apple);
System.out.println(clone);
System.out.println("-------------------克隆后修改值后继续打印---------------------------");
clone.setName("Watermelon");
clone.setMoney(new BigDecimal("5.88"));
Map<String, String> address = clone.getAddress();
if (address != null && !address.isEmpty()) {
// 基本数据类型可以达到完全复制,引用数据类型则不可以
// 改变address,这个地址是两个对象共享的,一旦修改,两个对象持有的address都会修改
address.put("province","ShangHai");
address.put("city","NanHui");
}
System.out.println(apple);
System.out.println(clone);

}

static class Goods implements Cloneable {

private String name;
private BigDecimal money;
private HashMap<String, String> address;

public Goods(String name, BigDecimal money, HashMap<String, String> address) {
this.name = name;
this.money = money;
this.address = address;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public BigDecimal getMoney() {
return money;
}

public void setMoney(BigDecimal money) {
this.money = money;
}

public Map<String, String> getAddress() {
return address;
}

public void setAddress(HashMap<String, String> address) {
this.address = address;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (this.money == null) {
this.money = BigDecimal.ZERO;
}
sb.append("[")
.append("name = ").append(this.name).append(", ")
.append("address = ").append(this.address).append(", ")
.append("money = ").append(this.money.setScale(2,BigDecimal.ROUND_HALF_UP)).append("]");
return sb.toString();
}


@Override
public Goods clone() throws CloneNotSupportedException {
// 浅克隆
// return (Goods) super.clone();

// 深克隆
//调用超类Object中方法clone进行对象克隆,得到一个新的Goods对象
Goods newGoogs = (Goods) super.clone();
//调用Goods类其属性address的clone方法,对属性进行克隆
HashMap<String, String> s = (HashMap<String, String>) this.address.clone();
//再将克隆的Address设置给克隆出来的Googs对象
newGoogs.setAddress(s);
//返回克隆出来的Googs对象
return newGoogs;
}

}
}
1
2
3
4
5
# 简单示例运行结果
-------------------简单示例---------------------------
o == list: false
[君子坦荡荡,小人常戚戚, 大丈夫,行不更名,坐不改姓, 明人不做暗事,真人不说假话, 现实中,我活得那么真实, 虚拟世界里,也从不虚伪, 不是说我这个人有个性,而是说我这个人就是这么与众不同, 我就是我,今天晚上不一样的烟火!]
[君子坦荡荡,小人常戚戚, 大丈夫,行不更名,坐不改姓, 明人不做暗事,真人不说假话, 现实中,我活得那么真实, 虚拟世界里,也从不虚伪, 不是说我这个人有个性,而是说我这个人就是这么与众不同, 我就是我,今天晚上不一样的烟火!]
1
2
3
4
5
6
7
8
# 浅拷贝,拷贝对象和被拷贝对象共同持有同一份Address对象
-------------------克隆后修改值前打印---------------------------
apple == clone: false
[name = Apple, address = {province=Shaanxi, city=Luochuan}, money = 5.80]
[name = Apple, address = {province=Shaanxi, city=Luochuan}, money = 5.80]
-------------------克隆后修改值后继续打印---------------------------
[name = Apple, address = {province=ShangHai, city=NanHui}, money = 5.80]
[name = Watermelon, address = {province=ShangHai, city=NanHui}, money = 5.88]
1
2
3
4
5
6
7
8
# 深拷贝,拷贝对象和被拷贝对象持有不同的Address对象
-------------------克隆后修改值前打印---------------------------
apple == clone: false
[name = Apple, address = {province=Shaanxi, city=Luochuan}, money = 5.80]
[name = Apple, address = {province=Shaanxi, city=Luochuan}, money = 5.80]
-------------------克隆后修改值后继续打印---------------------------
[name = Apple, address = {province=Shaanxi, city=Luochuan}, money = 5.80]
[name = Watermelon, address = {province=ShangHai, city=NanHui}, money = 5.88]
1
2
3
4
5
# Goos对象未实现Cloneable接口
Exception in thread "main" java.lang.CloneNotSupportedException: com.ltmf.arraylist.CloneableTest$Goods
at java.lang.Object.clone(Native Method)
at com.ltmf.arraylist.CloneableTest$Goods.clone(CloneableTest.java:117)
at com.ltmf.arraylist.CloneableTest.main(CloneableTest.java:39)

1.3.4 AbstractList抽象类

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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
package java.util;

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {


/**
* 唯一的构造器,由子类构造,通常是隐式调用
*/
protected AbstractList() {
}


/**
* 列表被修改的次数,默认为0
*/
protected transient int modCount = 0;


/**
* add方法
* @param e
* @return
*/
public boolean add(E e) {
// 调用重载方法add(int index, E element),抛出UnsupportedOperationException异常
// 此处的size()顶层是AbstractCollection抽象方法,具体实现在子类的size()方法中
add(size(), e);
// 添加成功后返回true
return true;
}


/**
* add(E e)实际调用的方法
* 此类不允许add操作,否则会直接抛出UnsupportedOperationException异常
* @param index
* @param element
*/
public void add(int index, E element) {
throw new UnsupportedOperationException();
}


/**
* get方法直接就是抽象的,交给子类去重写
* @param index
* @return
*/
abstract public E get(int index);


/**
* 和add方法类似,此类不允许进行set操作,否则会直接抛出UnsupportedOperationException异常
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
throw new UnsupportedOperationException();
}

/**
* 和add方法类似,此类不允许进行set操作,否则会直接抛出UnsupportedOperationException异常
* @param index
* @return
*/
public E remove(int index) {
throw new UnsupportedOperationException();
}


// Search Operations 以下是搜索操作

/**
* 返回指定元素的第一次出现在这个列表中的索引,
* 若此列表中不包含的元素,直接返回-1。
* 若此列表中包含的元素,直接返回当前元素在列表的索引值。
* @param o
* @return
*/
public int indexOf(Object o) {
// 获取当前list的迭代器
ListIterator<E> it = listIterator();
if (o==null) {
// 如果传进来的对象o为null,正向循环遍历,若有null的元素,取索previousIndex引值
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
// 如果传进来的对象o不为null,正向循环遍历,若有null的元素,取previousIndex索引值
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
// 如果找不到返回-1
return -1;
}


/**
* 获取当前列表的迭代器,实际上调用的重载方法listIterator(0)
* @return
*/
public ListIterator<E> listIterator() {
return listIterator(0);
}

/**
* 实际获取列表迭代器的实现
* @param index
* @return
*/
public ListIterator<E> listIterator(final int index) {
// 添加的时候列表大小检查
rangeCheckForAdd(index);

return new ListItr(index);
}


/**
*
* @param index
*/
private void rangeCheckForAdd(int index) {
// 若index小于0,或者index超过了当前列表数组的长度,则抛出IndexOutOfBoundsException异常
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* IndexOutOfBoundsException索引越界异常消息格式
* @param index
* @return
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
}


/**
* 返回指定元素的最后一次出现在这个列表中的索引,
* 若此列表中不包含的元素,直接返回-1。
* 若此列表中包含的元素,直接返回当前元素在列表的索引值。
* @param o
* @return
*/
public int lastIndexOf(Object o) {
// 获取当前list的迭代器
ListIterator<E> it = listIterator(size());
if (o==null) {
// 如果传进来的对象o为null,反向循环遍历,若有null的元素,取nextIndex索引值
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
// 如果传进来的对象o不为null,反向循环遍历,若有null的元素,取nextIndex索引值
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
// 如果找不到返回-1
return -1;
}

// Bulk Operations 批量操作


/**
* 列表清空操作,实际调用的是removeRange方法
*/
public void clear() {
removeRange(0, size());
}


/**
* 清空所有元素
* @param fromIndex 要删除的第一个元素的索引
* @param toIndex 在要删除的最后一个元素之后的索引
*/
protected void removeRange(int fromIndex, int toIndex) {
// 获取正向迭代器
ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
it.next(); // 迭代器指向下个元素
it.remove(); // 通过迭代器删除当前元素
}
}


/**
* 添加集合元素到指定的位置
* @param index 要添加的元素
* @param c 集合元素
* @return
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 添加前数组长度校验,校验未通过则抛出IndexOutOfBoundsException异常
rangeCheckForAdd(index);
// 修改标记
boolean modified = false;
for (E e : c) {
// 遍历添加元素,但是add方法此类不可用,会抛出UnsupportedOperationException异常
add(index++, e);
modified = true;
}
return modified;
}


// Iterators 迭代器


/**
* Itr 迭代器基本结构和操作(向后next)
*/
private class Itr implements Iterator<E> {
/**
* 调用next返回的索引,可理解为光标指向.
*/
int cursor = 0;

/**
* 最近一次调用next或previous返回的元素的索引。
* 如果通过调用删除此元素,则将其重置为-1
*/
int lastRet = -1;

/**
* 记录修改次数,设置预期的修改次数。
* 迭代器认为后备列表应具有的modCount值。
* 如果违反了此期望,则迭代器已检测到并发修改就会抛出并发修改异常。
*/
int expectedModCount = modCount;

public boolean hasNext() {
// 判断是否还有下一个元素,只要当前光标指向的位置和size大小不一致就表示还有下一个元素
return cursor != size();
}

/**
* 通过迭代器正向取元当前元素,并将cursor向前移动。
* @return
*/
public E next() {
checkForComodification();
try {
// 记录当前索引位置
int i = cursor;
// 获取当前索引的元素
E next = get(i);
// 最近操作的索引位置
lastRet = i;
// 光标索引前进
cursor = i + 1;
// 返回元素
return next;
} catch (IndexOutOfBoundsException e) {
// 出现索引越界,先检查是否并发修改异常,若不是直接抛出NoSuchElementException异常
checkForComodification();
throw new NoSuchElementException();
}
}

public void remove() {
if (lastRet < 0)
// 检验操作是否合法
throw new IllegalStateException();
// 校验是否并发修改
checkForComodification();

try {
// 移除next或previous的元素,这块会抛UnsupportedOperationException异常
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
// 若移除的元素索引在当前cursor索引之后,需要将cursor向前移1位
cursor--;
// 删除后最近的为-1
lastRet = -1;
// 设置修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}

/**
* 检查并发修改,当modCount与expectedModCount不一致会抛出ConcurrentModificationException异常
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

/**
* ListItr列表的迭代器基本实现(向后next操作)和扩展实现(向前previous操作)
*/
private class ListItr extends Itr implements ListIterator<E> {
/**
* ListItr 构造,同时设置当列表的cursor索引
* @param index
*/
ListItr(int index) {
cursor = index;
}

/**
* 判断是否有上一个
* @return
*/
public boolean hasPrevious() {
return cursor != 0;
}

/**
* 反向获取元素
* @return
*/
public E previous() {
// 检验是否并发修改
checkForComodification();
try {
// 光标索引向前移位
int i = cursor - 1;
// 获取上一个元素
E previous = get(i);
// 最近previous操作的索引
lastRet = cursor = i;
// 返回上一个元素
return previous;
} catch (IndexOutOfBoundsException e) {
// 校验并发修改异常
checkForComodification();
// 否则抛出NoSuchElementException异常
throw new NoSuchElementException();
}
}

/**
* 下一个索引其实就是当前cursor位置
* @return
*/
public int nextIndex() {
return cursor;
}

/**
* 上一个索引其实就是当前cursor位置-1
* @return
*/
public int previousIndex() {
return cursor-1;
}

public void set(E e) {
if (lastRet < 0)
// 校验是否非法操作
throw new IllegalStateException();
// 检查是否并发修改
checkForComodification();

try {
// set元素e到指定的位置,此类会报UnsupportedOperationException异常
AbstractList.this.set(lastRet, e);
// 设置当前类别修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
// 索引异常直接断定是并发修改异常,并抛出ConcurrentModificationException异常
throw new ConcurrentModificationException();
}
}

public void add(E e) {
// 检查并发修改异常
checkForComodification();

try {
// 取出cursor位置
int i = cursor;
// 将元素e添加到i的位置
AbstractList.this.add(i, e);
// 记录最近一次调用next或previous返回的元素的索引。
lastRet = -1;
// 光标索引前移
cursor = i + 1;
// 同步修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
// 索引异常直接断定是并发修改异常,并抛出ConcurrentModificationException异常
throw new ConcurrentModificationException();
}
}
}


/**
* 列表切割
* @param fromIndex 起始索引
* @param toIndex 终止索引
* @return
*/
public List<E> subList(int fromIndex, int toIndex) {
// 如果当前列表实现了RandomAccess接口,new RandomAccessSubList()返回,否则new SubList()返回
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}


/**
* 重写后的equals方法
* @param o
* @return
*/
public boolean equals(Object o) {
if (o == this)
// 如果参数对象o和当前对象引用地址一样,直接返回true
return true;
if (!(o instanceof List))
// 如果参数对象o非List的实现子类,直接返回false,表示当前equals并不适合参数o对象
return false;

// 获取当前this指向迭代器的对象
ListIterator<E> e1 = listIterator();
// 获取当前参数o指向迭代器的对象
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
// 迭代两个列表,比对,若有不相同的元素,直接返回false
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
// 直到迭代完毕没有元素,返回true,否则返回false
return !(e1.hasNext() || e2.hasNext());
}


/**
* 重写的hashCode方法
* @return
*/
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}

}

2. ArrayList源码分析

2.1 成员变量

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
package java.util;

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

/**
* 默认初始容量为10。
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 用于空实例的共享空数组实例。
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 共享的空数组实例用于默认大小的空实例。当第一个元素被添加时,我们与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 = {};

/**
* 集合真正存储数组元素的数组。非私有以简化嵌套类访问。elementData被transient修饰,序列化不会被持久化。
* 存储ArrayList元素的数组缓冲区,ArrayList的容量是此数组缓冲区的长度。
* 添加第一个元素时,任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。
* 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.
* non-private to simplify nested class access.
*/
transient Object[] elementData;

/**
* 集合ArrayList的大小(它包含的元素数)。
* The size of the ArrayList (the number of elements it contains).
*/
private int size;


/**
* 要分配的最大数组大小。
* -8目的是某些虚拟机保留的数组header words。
* 尝试分配更大的数组可能会导致OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

2.2 构造器

1
2
3
4
5
6
7
8
9
10
/**
* 无参构造:构造一个初始容量为10的空列表。
* 通过空参构造方法创建集合对象并未构造一个初始容量为十的空列表,仅仅将
* DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋值给elementData将DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋
* 值给elementData。
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 有参构造一: 构造一个具有指定初始容量的空列表。
* 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 若如果指定的初始容量为负数,则抛出IllegalArgumentException异常
*/
public ArrayList(int initialCapacity) {
// 判断初始容量initialCapacity是否大于0
if (initialCapacity > 0) {
// 创建一个数组,且指定长度为传进来的initialCapacity
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果initialCapacity容量为0,把EMPTY_ELEMENTDATA的地址赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 以上两个条件都不满足抛出IllegalArgumentException异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
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
package java.util;

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

/**
* 有参构造二: 构造一个包含指定集合的元素的列表,其顺序由集合的迭代器返回。
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list 将其元素放入此列表的集合
* @throws NullPointerException if the specified collection is null 如果参数集合为null,则抛出NullPointerException异常
*/
public ArrayList(Collection<? extends E> c) {
// 将集合构造中的集合对象转成数组,且将数组的地址赋值给elementData
elementData = c.toArray();
// 将elementData的长度赋值给集合长度size,且判断是否不等于0
if ((size = elementData.length) != 0) {
// 判断elementData 和 Object[] 是否为不一样的类型
if (elementData.getClass() != Object[].class)
// 如果不一样,使用Arrays的copyOf方法进行元素的拷贝
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array. 替换为空数组。
this.elementData = EMPTY_ELEMENTDATA;
}
}

/**
* 将集合转数组的方法
* @return
*/
public Object[] toArray() {
// 调用数组工具类方法进行拷贝
return Arrays.copyOf(elementData, size);
}
}

/**
* 数组工具类
*/
package java.util;

public class Arrays {

public static <T> T[] copyOf(T[] original, int newLength) {
// 再次调用方法进行拷贝
return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// 用三元运算符进行判断,不管结果如何都是创建一个新数组
T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 将数组的内容拷贝到 copy 该数组中
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
// 返回拷贝元素成功后的数组
return copy;
}
}

2.3 重要方法

2.3.1 add方法

1
2
3
4
5
6
7
8
9
10
11
/**
* add方法一: 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
// 调用方法对内部容量进行校验,增加modCount!
ensureCapacityInternal(size + 1);
// 将添加进来的元素放到数组尾部,并改变size大小
elementData[size++] = e;
// 添加成功后返回true
return true;
}
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
/**
* add方法二: 将指定的元素插入此列表中的指定位置。
* 若指定位置有元素,将指定元素添加到指定位置后,后续元素右移一位。
*/
public void add(int index, E element) {
// 添加时范围检查
rangeCheckForAdd(index);
// 调用方法检验是否要扩容,且让修改增量++
ensureCapacityInternal(size + 1);
// 调用System.arraycopy拷贝数组,数组移位操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将指定元素赋值到指定的位置上
elementData[index] = element;
size++;
}

/**
* 索引合法性检查,add和addAll都在使用
*/
private void rangeCheckForAdd(int index) {
// 指定范围不合法就报错
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* add方法三: 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
* @param c
* @return
*/
public boolean addAll(Collection<? extends E> c) {
// 将集合c转化为Object[]数组
Object[] a = c.toArray();
// 记录数组的长度
int numNew = a.length;
// 调用方法检验是否要扩容,且让增量++
ensureCapacityInternal(size + numNew);
//调用方法将a数组的元素拷贝到elementData数组中
System.arraycopy(a, 0, elementData, size, numNew);
// 集合的长度+=a数组的长度
size += numNew;
// 只要a数组的长度不等于0,即说明添加成功返回true
return numNew != 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
/**
* add方法四:将指定集合中的所有元素插入到此列表中,从指定的位置开始。
* @param index
* @param c
* @return
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 校验索引是否合法
rangeCheckForAdd(index);
// 将集合c转化为Object[]数组
Object[] a = c.toArray();
// 记录数组的长度
int numNew = a.length;
// 调用方法检验是否要扩容,且让增量++
ensureCapacityInternal(size + numNew); // Increments modCount

// numMoved:代表要移动元素的个数,numMoved = 集合真实长度 - 要存的索引位置
int numMoved = size - index;
// 判断需要移动的个数是否大于0
if (numMoved > 0)
// 使用System中的方法arraycopy进行移动
// System.arraycopy 参数列表: src-源数组, srcPos-源数组中的起始位置, dest-目标数组, destPos-目的地数据中的起始位置, length-要复制的数组元素的数量.
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//才是真正将数据源中所有数据添加到数据目的集合的操作
System.arraycopy(a, 0, elementData, index, numNew);
// 集合的长度+=a数组的长度
size += numNew;
// 只要a数组的长度不等于0,即说明添加成功返回true
return numNew != 0;
}

2.3.2 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
/**
* remove方法一: 根据索引删除元素
* @param index
* @return
*/
public E remove(int index) {
// 检查索引合法性
rangeCheck(index);

// 增量++
modCount++;
// 将index对应的元素赋值给oldValue
E oldValue = elementData(index);

// 计算集合需要移动元素个数
int numMoved = size - index - 1;
// 如果需要移动元素个数大于0,就使用arrayCopy方法进行拷贝
// 注意:数据源和数据目的就是elementData
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将源集合最后一个元素置为null,尽早让垃圾回收机制对其进行回收
elementData[--size] = null;
// 返回被删除的元素
return oldValue;
}


/**
* 检查索引合法性,不合法抛出IndexOutOfBoundsException异常
* @param index
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
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
/**
* remove方法二: 删除指定的元素
* @param o
* @return
*/
public boolean remove(Object o) {
// 判断要删除的元素是否为null
if (o == null) {
// 遍历集合
for (int index = 0; index < size; index++)
// 判断集合的元素是否为null
if (elementData[index] == null) {
// 如果相等,调用fastRemove方法快速删除
fastRemove(index);
return true;
}
} else {
// 遍历集合
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
// 如果相等,调用fastRemove方法快速删除
fastRemove(index);
return true;
}
}
// 如果集合没有o该元素,那么就会返回false
return false;
}


/**
* 私有的remove方法,跳过边界检查,并且不会返回删除的值
* @param index
*/
private void fastRemove(int index) {
// 增量++
modCount++;
// 计算集合需要移动元素的个数
int numMoved = size - index - 1;
if (numMoved > 0)
// 如果需要移动的个数大于0,调用arrayCopy方法进行拷贝
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将集合最后一个元素置为null,尽早被释放
elementData[--size] = null; // clear to let GC do its work
}

2.3.3 set方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 用指定的元素替换此列表中指定位置的元素,并返回被覆盖的元素。
*/
public E set(int index, E element) {
// 索引合法性校验
rangeCheck(index);
// 先取出index对应的元素,且赋值给oldValue
E oldValue = elementData(index);
// 将element直接覆盖index对应的元素
elementData[index] = element;
// 返回被覆盖的元素
return oldValue;
}

/**
* 根据索引获取elementData对应的元素
* @param index
* @return
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}

2.3.4 get方法

1
2
3
4
5
6
7
8
9
10
11
/**
* 根据索引获取对应的元素
* @param index
* @return
*/
public E get(int index) {
// 索引合法性校验
rangeCheck(index);
// 根据索引获取elementData数组对应的元素
return elementData(index);
}

2.3.5 clear方法

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 清空列表中所有的元素,该调用返回后,该列表将为空。
*/
public void clear() {
// 增量++,实际修改集合次数++
modCount++;
// 遍历集合,将集合每一个索引对应位置上的元素都置为null,尽早让其释放
for (int i = 0; i < size; i++)
elementData[i] = null;
// 集合长度更改为0
size = 0;
}

2.3.6 contains 方法

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
/**
* 判断集合是否包含指定元素
* 底层也是通过循环遍历集合,取出一个个的元素和要找的元素进行比较
* @param o
* @return
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}


/**
* 获取指定元素在第一次出现在数组的索引位置,找不到返回-1
* 底层也是通过循环遍历集合,取出一个个的元素和要找的元素进行比较
* @param o
* @return
*/
public int indexOf(Object o) {
// 如果元素是null,也进行遍历操作,因为集合中有可能够会存储null
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
// 如果确实存在null,返回null所在的索引
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
// 如果确实存在该元素,返回该元素所在的索引
return i;
}
// 如果没有走if,也没有走else,那么就说明o该元素在集合中不存在,直接返回-1
return -1;
}

/**
* 和indexOf功能类似,只不过是从反向查找的
* @param o
* @return
*/
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;
}

2.3.7 isEmpty方法

1
2
3
4
5
6
7
/**
* 如果此列表不包含任何元素,返回true,否则返回false
* @return
*/
public boolean isEmpty() {
return size == 0;
}

2.3.8 ensureCapacityInternal方法

1
2
3
4
5
6
7
/**
* 确认内部容量,实际调用的是ensureExplicitCapacity方法
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 确认内部容量,实际调用的是ensureExplicitCapacity方法
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
// 实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中),这个字段继承父类AbstractList
modCount++;
// 判断最小容量 - 数组长度是否大于 0
if (minCapacity - elementData.length > 0)
// 将第一次计算出来的容量传递给核心扩容方法,开始扩容
grow(minCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 计算容量
* @param elementData
* @param minCapacity
* @return
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果elementData是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 比较默认容量和minCapacity,返回两者的最大容量
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果不相等,直接返回minCapacity
return minCapacity;
}

2.3.9 ensureExplicitCapacity方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 确认实际的容量
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
// 实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中)
modCount++;

// 判断最小容量 - 数组长度是否大于 0
if (minCapacity - elementData.length > 0)
// 将计算出来的容量传递给核心扩容方法
grow(minCapacity);
}

2.3.10 grow方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 扩容方法
* @param minCapacity
*/
private void grow(int minCapacity) {
// 记录数组的实际长度,若没有元素,长度为0
int oldCapacity = elementData.length;
// JDK7以前ensureCapacity方法扩容算法是 int newCapacity = (oldCapacity * 3)/2 + 1,元容量的1.5倍+1
// JDK7以后核心扩容算法为:原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断新容量 - 最小容量是否小于 0, 如果是第一次调用add方法必然小于
if (newCapacity - minCapacity < 0)
// 小于的话,传递过来minCapacity就是新容量大小
newCapacity = minCapacity;
// 判断新容量-最大数组大小 是否>0,如果条件满足就计算出一个超大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData
elementData = Arrays.copyOf(elementData, newCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 计算巨大的容量
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
// 这块判断是否内存溢出,因为溢出后这个值可能是-2454546854314(随机负数)
if (minCapacity < 0)
throw new OutOfMemoryError();
// 计算巨大容量,若minCapacity大于MAX_ARRAY_SIZE,取Integer.MAX_VALUE,否则为MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

2.3.11 toString方法

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
/**
* 继承的ArrayList亲爷爷AbstractCollection的toString()
* @return
*/
public String toString() {
// 注意:此时相当于用ArrayList对象在调用iterator()方法 获取迭代器
// 那么这个时候需要先看看ArrayList中的iterator()方法
Iterator<E> it = iterator();
// 调用ArrayList中hasNext方法判断是否有元素,如果hasNext()方法返回false
// 那么就toString方法就返回一个 "[]"
if (! it.hasNext())
return "[]";
// 创建StringBuilder,对集合的内容进行拼接,避免字符串频繁拼接产生很多无效对象
StringBuilder sb = new StringBuilder();
sb.append('[');
// 无限循环
for (;;) {
// 调用ArrayList中next方法取出元素
E e = it.next();
// 追加内容
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
// 如果没有下一个元素,返回缓冲区的字符串
return sb.append(']').toString();
sb.append(',').append(' ');
}
}

2.3.12 clone方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* ArrayList复写的clone是浅拷贝
* @return
*/
public Object clone() {
try {
// 调用继承过来的clone方法
java.util.ArrayList<?> v = (java.util.ArrayList<?>) super.clone();
// 根据elementData复制一个同大小数组出来
v.elementData = Arrays.copyOf(elementData, size);
// 修改次数置位0
v.modCount = 0;
// 返回拷贝副本
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}

2.3.13 trimToSize方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 将该ArrayList实例的容量调整为列表的当前大小。
* 应用程序可以使用此操作来最大程度地减少ArrayList实例的存储。
* 假设size为1000时,此时elementData的length容量就是扩充后的1.5倍=1500。
* 但是实际上元素个数固定在1000,此时可以用该方法压缩空间。
*/
public void trimToSize() {
// 修改次数++
modCount++;
// 如果实际存储的元素大小小于数组的大小,进行空间压缩
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

2.3.14 sort方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 重写sort方法
* @param c
*/
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
// 操作次数赋值给expectedModCount
final int expectedModCount = modCount;
// 调用Arrays.sort进行排序,这里不在展开Arrays源码
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
// 若在排序的过程中,操作次数有修改,抛出ConcurrentModificationException异常
throw new ConcurrentModificationException();
}
// 操作次数++
modCount++;
}

2.3.15 forEach方法

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
/**
* ArrayList的内部迭代,JDK8后新增的方法
* @param action
*/
@Override
public void forEach(Consumer<? super E> action) {
// 校验是否为null,若null抛出NPL异常
Objects.requireNonNull(action);
// 记录modCount的值
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]);
}
// 若modCount != expectedModCount,抛出ConcurrentModificationException异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

2.3.16 iterator方法

1
2
3
4
5
6
7
/**
* 以正常的顺序返回此列表中元素的迭代器
*/
public Iterator<E> iterator() {
// 实例化了Itr,Itr是ArrayList的私有内部类
return new Itr();
}

2.4 迭代器实现

2.4.1 Itr内部类

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
/**
* Itr是ArrayList的私有内部类,是AbstractList.Itr的优化版本
*/
private class Itr implements Iterator<E> {
// 下一个要返回元素的索引
int cursor;
// 最后一个返回元素的索引,若没有返回-1
int lastRet = -1; // index of last element returned; -1 if no such

// 将实际修改集合次数 赋值 给预期修改次数
// 在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常
// 由于expectedModCount是Itr的成员变量,那么只会被赋值一次!!!
// 同时由于集合调用了三次add方法,那么实际修改集合次数就是 3,因此expectedModCount的值也是 3
int expectedModCount = modCount;

// Itr空参构造
Itr() {}

/**
* 是否还有下一个元素
* @return
*/
public boolean hasNext() {
// 只要两个不等,代表还有下一个元素
return cursor != size;
}

/**
* 获取元素的方法
* @return
*/
@SuppressWarnings("unchecked")
public E next() {
// 每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
checkForComodification();
// 把下一个元素的索引赋值给i
int i = cursor;
// 判断是否有元素
if (i >= size)
throw new NoSuchElementException();
// 将集合底层存储数据的数组赋值给迭代器的局部变量 elementData
Object[] elementData = ArrayList.this.elementData;
// 再次判断,如果下一个元素的索引大于集合底层存储元素的长度 并发修改异常
// 注意,尽管会产生并发修改异常,但是这里显示不是我们要的结果
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 每次成功获取到元素,下一个元素的索引都是当前索引+1
cursor = i + 1;
// 返回元素
return (E) elementData[lastRet = i];
}

/**
* 迭代器删除元素方法
*/
public void remove() {
// 判断最后返回元素的索引是否小于0,满足条件就产生非法状态异常
if (lastRet < 0)
throw new IllegalStateException();
// 校验是否会产生并发修改异常,第一次调用不会,因为与其修改次数和实际修改次数一致
checkForComodification();
try {
// 真正删除集合元素的方法,调用方法为ArrayList的方法remove,且将0作为参数进行传递
ArrayList.this.remove(lastRet);
// 将lastRet赋值给cursor
cursor = lastRet;
// 再次等于-1
lastRet = -1;
// 再次将集合实际修改次数赋值给预期修改次数,那么这个时候不管集合自身是否删除成功
// 那么实际修改次数和预期修改次数又一致了,所以并不会产生并发修改异常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

/**
* 对剩余(Remaining)的元素进行循环处理,只能用一次
* forEachRemaining()是Iterator接口在1.8的时候引入的一个默认方法
* @param consumer
*/
@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();
}
}

2.4.2 ListItr内部类

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
/**
* ListItr是ArrayList的私有内部类,是AbstractList.ListItr的优化版本
*/
private class ListItr extends java.util.ArrayList.Itr implements ListIterator<E> {
/**
* 有参构造
* @param index
*/
ListItr(int index) {
super();
cursor = index;
}

/**
* 是否还有上一个
* @return
*/
public boolean hasPrevious() {
// 只要没在数组的第一个位置,表示还有上一个元素
return cursor != 0;
}

/**
* 返回下一个索引
* @return
*/
public int nextIndex() {
return cursor;
}

/**
* 返回上一个元素的索引
* @return
*/
public int previousIndex() {
return cursor - 1;
}

/**
* 获取上一个元素
* @return
*/
@SuppressWarnings("unchecked")
public E previous() {
// 每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
checkForComodification();
// 把上一个元素的索引赋值给i
int i = cursor - 1;
// 判断是否有元素,如果没有抛出NoSuchElementException异常
if (i < 0)
throw new NoSuchElementException();
// 将集合底层存储数据的数组赋值给迭代器的局部变量 elementData
Object[] elementData = ArrayList.this.elementData;
// 再次判断,如果下一个元素的索引大于集合底层存储元素的长度 并发修改异常
// 注意,尽管会产生并发修改异常,但是这里显示不是我们要的结果
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 每次成功获取到元素,上一个元素的索引都是当前索引
cursor = i;
// 返回元素
return (E) elementData[lastRet = i];
}

/**
* set指定元素到lastRet位置
* @param e
*/
public void set(E e) {
// 校验lastRet是否合法
if (lastRet < 0)
throw new IllegalStateException();
// 每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
checkForComodification();

try {
// 替换lastRet的元素为e
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

/**
* 添加元素
* @param e
*/
public void add(E e) {
// 每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
checkForComodification();

try {
// 把元素的索引赋值给i
int i = cursor;
// 添加到指定位置
ArrayList.this.add(i, e);
// 每次成功获取到元素,上一个元素的索引都是当前索引+1
cursor = i + 1;
// 将lastRet设置为-1
lastRet = -1;
// 同步修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}

3. 纯手写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
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
package com.ltmf;

/**
* @projectName: ltmf
* @className: com.ltmf.MyArrayList
* @description: 纯手写ArrayList
* @author: tong.li
* @createTime: 2020/5/18 下午8:42
* @version: v1.0
*/
@SuppressWarnings("all")
public class MyArrayList<E> {


/**
* 定义数组,用于存储集合的元素
*/
transient Object[] elementData;

/**
* 定义变量,用于记录数组的个数
*/
private int size;

/**
* 定义空数组,用于在创建集合对象的时候给elementData初始化
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 定义常量,用于记录集合的容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空参构造
*/
public MyArrayList() {
// 给elementData初始化
this.elementData = EMPTY_ELEMENTDATA;
}

/**
* add方法
* @param e
* @return
*/
public boolean add(E e){
// 将来再调用的时候需要判断是否需要扩容
grow();
// 将元素添加到集合
elementData[size++] = e;
return true;
}


/**
* 简单扩容
*/
private void grow(){
// 判断集合存储元素的数组是否等于emptyArray
if(elementData == EMPTY_ELEMENTDATA){
//第一次扩容
elementData = new Object[DEFAULT_CAPACITY];
}

// 核心算法 1.5倍
// 如果size==集合存元素数组的长度,就需要扩容
if(size == elementData.length){
// 先定义变量记录老容量
int oldCapacity = elementData.length;
// 核心算法 1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 创建一个新的数组,长度就newCapacity
Object[] obj = new Object[newCapacity];
// 拷贝元素
System.arraycopy(elementData, 0, obj, 0, elementData.length);
// 把新数组的地址赋值给elementData
elementData = obj;
}
}

/**
* 重写toString()方法
* @return
*/
@Override
public String toString(){
// 建议对集合进行判断,如果没有内容直接返回 "[]"
if(size == 0){
return "[]";
}

// 创建StringBuilder
StringBuilder sb = new StringBuilder();
sb.append("[");
// 循环遍历数组
for (int i = 0; i < size; i++) {
// 判断i是否等于size-1
if(i == size-1){
// 要追加元素,还需要追加]
sb.append(elementData[i]).append("]");
}else{
sb.append(elementData[i]).append(",").append(" ");
}
}
// 把sb中的所有数据转成一个字符串,且返回
return sb.toString();
}

/**
* 修改方法
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
// 建议先对方法的参数索引进行判断
checkIndex(index);
// 把index索引对应的元素取出来
E value = (E) elementData[index];
// 替换元素
elementData[index] = element;
// 返回之前的元素
return value;
}

/**
* 检查索引
* @param index
*/
private void checkIndex(int index) {
if(index < 0 || index >= size){
// 制造一个异常
throw new IndexOutOfBoundsException("索引越界了!");
}
}

/**
* 根据索引删除元素
* @param index
* @return
*/
public E remove(int index) {
// 校验索引
checkIndex(index);
// 取出元素
E value = (E) elementData[index];
// 计算出要移动元素的个数
int numMoved = size - index - 1;
// 判断要移动的个数是否大于0
if (numMoved > 0){
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
// 把最后一个位置上的元素置为null
elementData[--size] = null;
return value;
}

/**
* 根据索引获取元素
* @param index
* @return
*/
public E get(int index){
// 调用方法校验索引
checkIndex(index);
// 直接从elementData数组中获取元素且返回
return (E) elementData[index];
}

/**
* 获取集合的长度
* @return
*/
public int getSize(){
return 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
package com.ltmf;

/**
* @projectName: ltmf
* @className: com.ltmf.MyArrayListTest
* @description: 自定义ArrayList测试类
* @author: tong.li
* @createTime: 2020/5/18 下午10:10
* @version: v1.0
*/
public class MyArrayListTest {

public static void main(String[] args) {
// 创建自定义集合对象
MyArrayList<String> list = new MyArrayList<>();
// 添加数据
list.add("宋江");
list.add("卢俊义");
list.add("林冲");
// 调用toString方法
System.out.println(list);
// 测试set方法
System.out.println(list.set(1, "李彤"));
System.out.println(list);
System.out.println(list.remove(2));
System.out.println(list);
// 测试get方法
System.out.println(list.get(0));
System.out.println(list.get(1));
// 获取size
System.out.println("size = " + list.getSize());
}
}
1
2
3
4
5
6
7
8
9
# 运行结果
[宋江, 卢俊义, 林冲]
卢俊义
[宋江, 李彤, 林冲]
林冲
[宋江, 李彤]
宋江
李彤
size = 2

4. 面试连环炮

  1. new ArrayList();真的构造一个初始容量为十的空列表?

    new ArrayList();并没有构造一个初始化容量为10的空列表,它的构造方法仅仅是一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA,此时数组大小仍然为0.

  2. ArrayList什么时候扩容?扩容机制是什么?

    当add方法调用的时候,第一次扩容是10,以后每次都是原容量的1.5倍.

    当minCapacity - elementData.length>0,调用grow(minCapacity)进行扩容判断.

    grow方法里先取出 elementData.length,然后计算newCapacity(老容量的1.5倍).

    若newCapacity - minCapacity < 0,则新容量就是minCapacity;

    若newCapacity - MAX_ARRAY_SIZE,则新容量就是最大容量;

    若前面两个条件都不成立,直接按newCapacity扩容.

  3. 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
    package com.ltmf;

    import java.util.ArrayList;
    import java.util.List;

    /**
    * @projectName: ltmf
    * @className: om.ltmf.BatchTest
    * @description: 大数据量批量操作
    * @author: tong.li
    * @createTime: 2020/5/18 下午8:47
    * @version: v1.0
    */
    public class BatchTest {

    public static void main(String[] args) {
    // 创建集合对象
    List<String> list = new ArrayList<>();
    // 添加元素
    list.add("hello");
    list.add("PHP");
    list.add("Java");
    long startTime = System.currentTimeMillis();
    // 需求:还需要添加10W条数据
    for (int i = 0; i < 100000; i++) {
    list.add(i+"");
    }
    long endTime = System.currentTimeMillis();
    // 看起来没什么?但是深度挖掘处理,有很大问题: 扩容N次,性能很低
    System.out.println("未指定容量: "+ (endTime - startTime));


    // 创建集合的时候指定足够大的容量
    List<String> list1 = new ArrayList<>(100000);
    startTime = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
    list1.add(i+"");
    }
    endTime = System.currentTimeMillis();
    // 若指定初始化容量,大数据量下会有性能提升.小数据量下, 没有什么效果
    System.out.println("指定容量: "+ (endTime - startTime));
    }
    }
    1
    2
    3
    # 执行结果
    未指定容量: 40
    指定容量: 15
  4. ArrayList插入或删除元素一定比LinkedList慢么?

    1. 数组删除元素确实要比链表慢,慢在需要创建新数组,还有比较麻烦的数据拷贝,但是在ArrayList
      底层不是每次删除元素都需要扩容,因此在这个方面相对于链表来说数组的性能更好.
    2. LinkedList删除元素之所以效率并不高,其原理在于底层先需要对整个集合进行折半的动作,然后
      又需要对集合进行遍历一次,这些操作导致效率变低.
  5. ArrayList是线程安全的么?

    不是线程安全的,原因是多条线程同时操作一个位置的时候,导致更改了集合的长度,那么造成数据的覆盖,而集合某个位置上又没有数据,所以有可能是null.

    若想线程安全,除过手动加synchronized锁外,我们可以使用JDK中Collections.synchronizedList(list)转同步.

    在多线程环境下,使用迭代器在读取集合元素的同时,还可以保证正常的写入数据的集合,我们可以使用读写分离集合CopyOnWriteArrayList类。

  6. ArrayList 和 LinkList区别?

    1. ArrayList
      1. 基于动态数组的数据结构;
      2. 对于随机访问的get和set,ArrayList要优于LinkedList;
      3. 对于随机操作的add和remove,ArrayList不一定比LinkedList慢 (ArrayList底层由于是动态数组,因此并不是每次add和remove的时候都需要创建新数组)。
    2. LinkedList
      1. 基于链表的数据结构;
      2. 对于顺序操作,LinkedList不一定比ArrayList慢;
      3. 对于随机操作,LinkedList效率明显较低。

5. 参考文档

ArrayList官方文档

支付宝打赏 微信打赏

请作者喝杯咖啡吧