Java集合源码学习笔记（二）ArrayList分析
1.关于ArrayList
ArrayList直接继承AbstractList，实现了List、 RandomAccess、Cloneable、Serializable接口，
为什么叫"ArrayList"，因为ArrayList内部是用一个数组存储元素值，相当于一个可变大小的数组，也就是动态数组。
（1）继承和实现
继承了AbstractList，实现了List：ArrayList是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
实现RandmoAccess接口：即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
实现了Cloneable接口：即覆盖了函数clone()，能被克隆。
实现java.io.Serializable接口：这意味着ArrayList支持序列化，能通过序列化去传输。
（2）线程安全
ArrayList中的操作不是线程安全的。建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
2.常用的方法
（1）方法说明
boolean add(E e)
将指定的元素添加到此列表的尾部。
void add(int index, E element)
将指定的元素插入此列表中的指定位置。
boolean addAll(Collection<? extends E> c)
按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。
boolean addAll(int index, Collection<? extends E> c)
从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。
void clear()
移除此列表中的所有元素。
Object clone()
返回此 ArrayList 实例的浅表副本。
boolean contains(Object o)
如果此列表中包含指定的元素，则返回 true。
void ensureCapacity(int minCapacity)
如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。
E get(int index)
返回此列表中指定位置上的元素。
int indexOf(Object o)
返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
boolean isEmpty()
如果此列表中没有元素，则返回 true
int lastIndexOf(Object o)
返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
E remove(int index)
移除此列表中指定位置上的元素。
boolean remove(Object o)
移除此列表中首次出现的指定元素（如果存在）。
protected void removeRange(int fromIndex, int toIndex)
移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
E set(int index, E element)
用指定的元素替代此列表中指定位置上的元素。
int size()
返回此列表中的元素数。
Object[] toArray()
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。
void trimToSize()
将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。
（2）遍历方式
ArrayList支持3种遍历方式
1.通过迭代器遍历。即通过Iterator去遍历
2.随机访问，通过索引值去遍历，
ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素
3.for循环遍历
下面比较这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
|
public
static
void
main(String[] args){
ArrayList<Object> list=
new
ArrayList<>();
for
(
int
i=
0
;i<
10000
;i++){
list.add(i);
}
useIterator(list);
useRandomAccess(list);
useForeach(list);
}
public
static
void
useIterator(List<Object> list){
Long startTime = System.currentTimeMillis();
Iterator iter = list.iterator();
while
(iter.hasNext()) {
iter.next();
}
System.out.println(System.currentTimeMillis()-startTime);
}
public
static
void
useRandomAccess(List<Object> list){
Long startTime = System.currentTimeMillis();
for
(
int
i=
0
; i<list.size(); i++) {
list.get(i);
}
System.out.println(System.currentTimeMillis()-startTime);
}
public
static
void
useForeach(List<Object> list){
Long startTime = System.currentTimeMillis();
for
(Object obj:list) {
;
}
System.out.println(System.currentTimeMillis()-startTime);
}
|
输出结果没放，不过结论是遍历ArrayList时，使用随机访问(即通过索引序号访问)效率最高，而使用迭代器的效率相对较低。
3.源码分析
在几个常用的集合实现类中，ArrayList的实现代码是最短的，比较简单。
（1）构造方法
ArrayList提供了三个构造方法：
//初始默认大小为10
|
1
2
3
|
public
ArrayList() {
this
(
10
);
}
|
//可以直接设置ArrayLi的初始大小
|
1
2
3
4
5
6
7
8
9
|
public
ArrayList(
int
i){
if
(i <
0
) {
throw
new
IllegalArgumentException((
new
StringBuilder())
.append(
"Illegal Capacity: "
).append(i).toString());
}
else
{
elementData =
new
Object[i];
return
;
}
}
|
//使用Collettion作为参数初始化
|
1
2
3
4
5
6
7
|
public
ArrayList(Collection collection)
{
elementData = collection.toArray();
size = elementData.length;
if
(((Object) (elementData)).getClass() != [Ljava/lang/Object;)
elementData = Arrays.copyOf(elementData, size, [Ljava/lang/Object;);
}；
|
一个是无参数的构造方法，另外一个是拥有单个参数（类型为Collettion）的构造方法。
ArrayList还提供了第三个构造方法，其接受一个int值，用于设置ArrayLi的初始大小（默认大小为10）。
（2）数据结构
|
1
2
|
private
transient
Object elementData[];
private
int
size;
|
ArrayList内部维护了一个Object数组，可以通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，size 则是动态数组的实际大小。
（3）elementData[]为什么使用 transient 修饰？
被transient（）定义的变量不可序列化，但是注意ArrayList同时实现了Serializable接口接口，这是为什么?
主要是为了提高序列化时的效率。
序列化有2种方式：
1.只是实现了Serializable接口。
序列化时，调用java.io.ObjectOutputStream的defaultWriteObject方法，将对象序列化。
注意：此时transient修饰的字段，不会被序列化。
2.实现了Serializable接口，同时提供了writeObject方法。
序列化时，会调用该类的writeObject方法。而不是java.io.ObjectOutputStream的defaultWriteObject方法。
注意：此时transient修饰的字段，是否会被序列化，取决于writeObject。
假如现在实际有了5个元素，而elementData的大小可能是10，那么在序列化时只需要储存5个元素，数组中的最后五个元素是没有实际意义的，不需要储存。
所以ArrayList的设计者将elementData设计为transient，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。
（4）源码注释
|
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
|
/**
* 使用一个Collection进行构造
* Arraylist中大量使用了Arrays的相关方法
*/
public
ArrayList(Collection collection)
{
elementData = collection.toArray();
size = elementData.length;
if
((Object) (elementData).getClass() != Object.
class
){
elementData = Arrays.copyOf(elementData, size, (elementData).getClass());
}
}
/**
* 如果当前数组的容量大于数组实际存储的数据元素数量，重新调整数组大小
* 用于把ArrayList的容量缩减到当前实际大小，减少存储容量。
* 其中的变量modCount由AbstracList继承而来，记录List发生结构化修改（structurally modified）的次数。
* @Title: trimToSize
*/
public
void
trimToSize() {
modCount++;
int
i = elementData.length;
if
(size < i)
elementData = Arrays.copyOf(elementData, size);
}
/**
* 确保ArrayList的大小
* @Title: ensureCapacity
* @param i
*/
public
void
ensureCapacity(
int
i) {
modCount++;
int
j = elementData.length;
if
(i > j) {
Object aobj[] = elementData;
int
k = (j *
3
) /
2
+
1
;
if
(k < i)
k = i;
elementData = Arrays.copyOf(elementData, k);
}
}
/**
* 返回指定元素的下标，要区分参数是否为null
* 注意ArrayList可以是可以存储null的
*/
public
int
indexOf(Object obj) {
if
(obj ==
null
) {
for
(
int
i =
0
; i < size; i++)
if
(elementData[i] ==
null
)
return
i;
}
else
{
for
(
int
j =
0
; j < size; j++)
if
(obj.equals(elementData[j]))
return
j;
}
return
-
1
;
}
/**
* 使用了系统的System.arraycopy方法
* 这是一个native的方法
*/
public
Object[] toArray(Object aobj[]) {
if
(aobj.length < size)
return
(Object[]) Arrays.copyOf(elementData, size,(aobj).getClass());
System.arraycopy(((Object) (elementData)),
0
, ((Object) (aobj)),
0
,
size);
if
(aobj.length > size)
aobj[size] =
null
;
return
aobj;
}
/**
* 和序列化以及transient的处理有关系
*/
private
void
writeObject(ObjectOutputStream objectoutputstream)
throws
IOException {
int
i = modCount;
objectoutputstream.defaultWriteObject();
objectoutputstream.writeInt(elementData.length);
for
(
int
j =
0
; j < size; j++)
objectoutputstream.writeObject(elementData[j]);
if
(modCount != i)
throw
new
ConcurrentModificationException();
else
return
;
}
|
4.总结
在Java中应用静态数组很容易发生一些错误，相比较来说，
ArrayList可以动态的增加和减少元素，灵活的设置数组的大小，提供了多种遍历方式，在设计时就尽可能的考虑了性能，大多数工程开发中数组都会使用ArrayList。
