JDK集合源码阅读二:ArrayList

ArrayList定义

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • 继承了抽象类AbstractList,AbstractList中有绝大部分的方法实现;实现了List接口,其实AbstractList已经实现了List接口,这里可以不用实现List的,对于这个网上有很多说法;实现RandomAccess,快速随机访问集合中的元素;实现Cloneable,可克隆;实现Serializable,可序列化

成员变量

1
2
//默认容量是10
private static final int DEFAULT_CAPACITY = 10;
1
2
//空元素数组
private static final Object[] EMPTY_ELEMENTDATA = {};
1
2
//默认空元素数组,在第一次添加元素的时候,会初始化容量10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
//ArrayList就是基于数组的,它的所有操作,其实就是在操作这个数组,transient 标识不需要序列化
//因为elementData是内部维护的一个数组,它的扩容机制使它的容量是大于实际集合的大小的,所以会有很多空元素,空元素是没必要序列化的
transient Object[] elementData;
1
2
//这个size标识当前集合的实际个数,和elementData的length不是一个
private int size;
1
2
//默认的数组最大容量值,为什么要默认最大值 Integer.MAX_VALUE - 8 ,看作者的注释:Some VMs reserve some header words in an array.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

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
//指定容量的构造器,初始化elementData为指定容量
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);
}
}
//默认的构造器,只是将默认空元素数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给了elementData数组,注意这里其实还只是一个空数组,在第一次执行add操作的时候,才会扩容10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 接收Collection集合的构造器,会将传入的集合转成数组elementData。注意这里有个容错判断elementData.getClass() != Object[].class, 因为toArray方法可能返回的不是一个Object[],参考JDK BUG。当toArray返回的不是Object[]时,比如是String[],把它赋值给elementData后,之后的操作就会类型转换错误了,比如add(Object o),所以这里进行了判断,并对数组进行了拷贝
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

容量操作函数

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
//此函数用于释放自动扩容导致多余的空间
public void trimToSize() {
//继承于父类AbstractList,记录着集合的修改次数,这个变量用来在迭代集合的时候,保证集合没有被修改
modCount++;
//释放的前提是自动扩容的数组elementData的长度,大于实际集合的size
if (size < elementData.length) {
//如果当前集合是空的,直接将数组赋值空元素数组,否则执行指定长度的数组拷贝
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 最底层的扩容方法
* 1.先计算扩容值为 (目前数组length + 目前数组length的一半)
2.如果传参的容量大于这个,则使用传参的容量,否则就增量扩容原来容量的一半
3.判断前两步计算出来的扩容值大于默认的最大容量值(Integer.MAX_VALUE - 8),这时需要判断传参的容量值是不是就是大于默认的最大容量值,如果是,则赋值Integer.MAX_VALUE,否则还是使用默认的最大容量
总结: 大致思路是:默认就是扩原来容量的一半,如果你要的更多,再看你要的是不是比默认最大值还大,如果是,就给你一个Integer的最大值,如果你没要那么多,给一个默认最大值。
注意这里的扩容值,并不是说在原来的大小上加X,而是直接扩容到X
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
//拷贝一个指定长度的数组,赋值给elementData
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;
}
//确保得到指定值的容量: public修饰符,说明这个方法是对外开放的,可以调用这个方法手动扩容
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
//这里校验两个情况,一是负值传参,不进行扩容;二是刚执行完默认构造器初始化,这种情况下所需容量必须大于默认的初始化容量10,才给扩容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//内部扩容方法,用于内部调用,比如add,addAll执行时的确保容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//前两个方法都是调的这个方法
private void ensureExplicitCapacity(int minCapacity) {
//每次扩容修改次数都会加1
modCount++;
//所需容量必须比当前数组长度大
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用底层扩容方法
grow(minCapacity);
}

集合操作函数

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
//获取指定索引的值 内部调用
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//数组越界检查 内部方法
//这里没有对index进行<0判断,当传入负值的时候,会在数组里抛异常
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//数组越界检查 内部方法 用于add 和 addAll的越界检查
//这里index是可以等于size的,等于size相当于在数组末端追加
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//获取指定索引的值,对外开放,先会进行越界检查
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//替换指定位置的值,对外开放,先会进行越界检查
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//插入元素,会先进行确保容量操作,然后在数组末端追加元素,在ensureCapacityInternal方法中有修改次数的增加
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//在指定位置插入元素,先进行越界检查,再确保容量操作
//扩容之后 elementData 数组长度增长; 以保证下一步System.arraycopy数组拷贝不会数组越界
//拷贝完,将指定位置的值替换
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//合并集合,在内部数组后面追加传入的集合
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//移除指定位置的元素,并返回指定位置的元素, 也是System.arraycopy操作
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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;
}
//内部方法,跳过数组越界检查,不返回移除的元素
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
}
//移除指定元素,equals判断
public boolean remove(Object o) {
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;
}
//清空集合: 将内部数组中的元素全部赋值null,集合size赋值0
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//没有对外开放,避免冗余,因为已经有subList方法了
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
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;
}
//移除元素和合并元素,通过一个boolean标识,封装成了一个方法batchRemove
//也是用到了System.arraycopy
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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++)
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;
}
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;
}

序列化/反序列化

ArrayList实现了Serializable,但是数据是基于内部维护的elementData数组,这个数组是瞬态的,不会被序列化,所以提供了writeObject/readObject

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
//将集合实际大小的size,来写入对象流中
//写完会判断modCount,是否在并发环境下,当前集合有被操作
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}

其它

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
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//可以找出null值的位置,这里匹配是对象equals,默认是比对对象引用,如果要比较对象的属性值,可以重写equals和hashcode方法
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;
}
//集合拷贝,调用的是Arrays.copyOf,属于浅拷贝,只是拷贝了对象引用,注意当操作拷贝后的集合中的对象时,原集合中的对象也会变化,因为指向的是同一个地址
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
//重置了记录修改次数值
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
//这里没有直接返回elementData,因为elementData是内部操作数组,包括自动扩容后产生的空元素,size才是实际集合的长度
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//将当前数组拷贝到传入的数组中
//如果传入的数组长度小于当前数组,会创建一个新的对当前数组的拷贝返回
//否则会从第一位开始,拷贝当前数组的长度,到源数组,并返回源数组
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

总结

  • ArrayList的底层其实就是内部维护一个elementData数组,所有的增删改查操作都是基于这个数组的;
  • elementData数组的length和集合实际的size不一样,扩容机制使elementData的length会大于集合的size,可以调用trimToSize方法释放空元素,使length和size保持一致;
  • 集合所有的操作,底层都是用的Arrays.copyOf和System.arraycopy,Arrays.copyOf底层也是System.arraycopy,这个方法有5个参数:Object src, int srcPos, Object dest, int destPos, int length,分别代表 源数组、源数组要复制的起始位置、目标数组、目标数组放置的起始位置、复制的长度,如果数组越界会抛异常,所以ArrayList在进行增删改操作时,会进行数组越界检查;
  • 集合内元素的判断是否是同一个元素,是通过equals判断的,默认是判断引用地址是否是同一个,可以重写元素的equals和hashcode方法,改变判断条件
  • 为不让elementData数组中的空元素序列化,提供了序列化和反序列化方法;
坚持原创技术分享,您的支持将鼓励我继续创作!
分享