本篇博客主要的内容是介绍ArrayList的使用和对其源码进行分析，并比较ArrayList不同迭代器之间的性能
1. ArrayList 简介
ArrayList是一个有序集合，底层是通过数组来实现的，可以动态的改变大小，相当于动态数组。与Java中的数组相比，它的容量能动态增长。他继承于AbstractList，实现了List，RandomAccess，Cloneable，java.io.Serializable接口。
类如如下：
ArrayList继承AbstractList，实现List接口。因此就具有相关的添加、删除、修改、遍历等功能。
ArrayList实现RandmoAccess接口，即提供随机访问功能，注意这个接口内部并没有任何方法，只是起到标记的作用。
ArrayList实现Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
注意的一点是：ArrayList不是线程安全的！所以不要再并发程序中使用
ArrayList源码分析
下面所有源码都是基于Java8来进行的分析：按照add，remove，get，Iterator，ListIterator的顺序来进行源码分析
首先看一下一些比较重要的属性，可以方便后面理解源码：
1 | //默认初始容量 |
- elementData 是”Object[]类型的数组”，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
- size则是动态数组的实际大小。
构造函数
1 | //设置ArrayList的初始容量，当时负数时抛出错误 |
从上面可知，提供了三个默认构造函数，分别是默认构造函数，将会初始化一个空数组，指定长度的构造函数，根据指定的长度来初始化数组，添加一个集合来初始化数组，这个会初始化一个和集合长度相等的数组，并把数据添加进去。
这里补充一点，就是上面第三个构造函数，为什么还要在判断下数组元素的类型是否是Object类型的数组，主要的原因是因为，java标准库中提供了一个Arrays.asList的函数，这个函数会返回一个list，但是没有用ArrayList来实现，而是在其内部单独实现了一个ArrayList，其内部实现将底层数组定义成了T[] ，而不是Object[]，所以如果传递的是这种list创建ArrayList，就会出现类型不一致的问题，这里判断的也是为了防止这一点，详细的内容可以参考利用Jdk 6260652 Bug解析Arrays.asList（学习笔记）
添加（add）
这里先总结下具体的添加过程
- 添加元素时，首先会检测数组是否已满，如果未满，则直接添加元素。否则进入下一步。
- 如果已经满了，则创建一个更长的数组，将原先数组的数据拷贝过来，然后在添加元素。
具体源码如下
1 | public boolean add(E e) { |
这里需要注意的一点是，重新设置容量大小按照下面这个公式来设置的：新的容量=原始容量*3。并且如果数组长度超过整型的最大值，则会抛出异常。
指定下标添加元素
即add(int index, E element) ，大体上和add差不多。在指定位置添加元素，需要将原先位置的元素以及后面的元素往后順移一位，大概过程如下
1 | public void add(int index, E element) { |
删除（remove）
具体源码如下
1 | public E remove(int index) { |
remove(object)
1 | public boolean remove(Object o) { |
get
这个操作就比较简单，检查index范围是否正确，然后返回指定下标的元素
1 | public E get(int index) { |
Iterator和ListIterator
这俩个是通过内部维持一个当前操作的下标来实现的，当判断hashNext的时候判断当前下标是否超过size即可。
不过要注意的一点是，每一此next操作，都会进行如下操作
1 | final void checkForComodification() { |
会检测modCounrt和迭代器保存的modCount是否相等，如果相同，则说明有其他线程修改了集合，会抛出并发修改异常。
ArrayList 遍历方式
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。
2
3
4
5
>Iterator iter = list.iterator();
>while (iter.hasNext()) {
value = (Integer)iter.next();
>}(02) 第二种，随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
2
3
4
5
>int size = list.size();
>for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
>}(03) 第三种，for循环遍历。如下：
2
3
4
>for (Integer integ:list) {
value = integ;
>}下面通过一个实例来演示效率问题
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
>import java.util.ArrayList;
>import java.util.Iterator;
>import java.util.List;
>/**************************************
* Author : zhangke
* Date : 2018/1/18 19:37
* Desc : 测出ArrayList三种哪一种遍历最快
***************************************/
>public class StudyArrayList {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
iteratorThroughFor(list);
iteratorThroughFor2(list);
iteratorThroughRandomAccess(list);
}
public static void iteratorThroughRandomAccess(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
endTime = System.currentTimeMillis();
System.out.println("iteractorRandomAccess interval: " + (endTime - startTime));
}
public static void iteratorThroughFor2(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (Object object : list) {
}
endTime = System.currentTimeMillis();
System.out.println("iteractorfor interval: " + (endTime - startTime));
}
public static void iteratorThroughFor(List list) {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
iterator.next();
}
endTime = System.currentTimeMillis();
System.out.println("iteractor interval: " + (endTime - startTime));
}
>}结果如下
2
3
>iteractorfor2 interval: 4
>iteractorRandomAccess interval: 4我测试了几次，感觉java8里面随机访问和foreach访问比较快，不过相差也不是太大。不过数据量大的话，还是推介使用随机访问。
toArray 异常
有俩种方法可以将list转换成数组，具体的方法如下
1 |
|
有时调用toArray()函数会抛出“java.lang.ClassCastException”异常，这时就需要调用toArray(T[] contents)来解决这中异常。
toArray() 会抛出异常是因为toArray()返回的是Object[]数组，将 Object[] 转换为其它类型(类如，将Object[]转换为的Integer [])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。具体的可以参考前面ArrayList.java的源码介绍部分的toArray()。
解决该问题的办法是调用 <T> T[] toArray(T[] contents) 。
ArrayList基本使用
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
>public class ArrayListTest {
public static void main(String[] args) {
// 创建ArrayList
ArrayList list = new ArrayList();
// 将“”
list.add("1");
list.add("2");
list.add("3");
list.add("4");
// 将下面的元素添加到第1个位置
list.add(0, "5");
// 获取第1个元素
System.out.println("the first element is: "+ list.get(0));
// 删除“3”
list.remove("3");
// 获取ArrayList的大小
System.out.println("Arraylist size=: "+ list.size());
// 判断list中是否包含"3"
System.out.println("ArrayList contains 3 is: "+ list.contains(3));
// 设置第2个元素为10
list.set(1, "10");
// 通过Iterator遍历ArrayList
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
System.out.println("next is: "+ iter.next());
}
// 将ArrayList转换为数组
String[] arr = (String[])list.toArray(new String[0]);
for (String str:arr)
System.out.println("str: "+ str);
// 清空ArrayList
list.clear();
// 判断ArrayList是否为空
System.out.println("ArrayList is empty: "+ list.isEmpty());
}
>}