读源码之ArrayList

简单剖析下常用的ArrayList类的源码

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
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
//实现了Serializable接口,因此它支持序列化,能够通过序列化传输
//实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问
//实现了Cloneable接口,能被克隆。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//提供序列化用的
private static final long serialVersionUID = 8683452581122892189L;

//默认的初始容量为10
private static final int DEFAULT_CAPACITY = 10;

//...
private static final Object[] EMPTY_ELEMENTDATA = {};

//arraylist用来保存对象的数组,transient告诉序列化的时候不要管这个数组
transient Object[] elementData;

//arraylist的大小
private int size;

//构造函数,不能传入负数,否则报错,然后初始化elementData数组的大小
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}

/*
空构造函数,以前的代码直接初始化容量为10的容量数组:this(10)
现在api25中,这里直接初始化一个空数组,等add的时候再设置容量为10
懒加载模式
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}

//构造函数,将c集合里面的东西放array里面
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

/*
将array的size设为实际size大小
modCount表示修改的次数,给迭代器iterator用的,实现fail-fast机制
用于多线程的时候modCount不一致,快速抛出异常
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}

//这个方法就是确保array的容量至少为minCapacity
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA)
// any size if real element table
? 0
// larger than default for empty table. It's already supposed to be
// at default size.
: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

//接上面的方法,增加修改次数,判断需要的最小容量大于实际容量再操作
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/*
以前增加的容量为old的三分之二再加一:
int newCapacity = (oldCapacity * 3)/2 + 1
现在增加的容量为old的二分之一:
int newCapacity = oldCapacity + (oldCapacity >> 1)
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//右移一位表示除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//这个newCapacity < minCapacity的代码下面这样写有什么优势?
//下面主要是判断oldCapacity=1的情况下,newCapacity其实等于oldCapacity的情况?
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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 int size() {return size;}

public boolean isEmpty() {return size == 0;}

//判断包含
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

//这里先判断null对象,非null的对象是通过equals()来判断的
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;
}

//反过来查询返回第一个的i
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;
}

//浅拷贝,并且将修改次数置0
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);
}
}

//转化为数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

/*
返回ArrayList元素组成的数组
如果数组a的容量小于list,则新建一个数组,反之直接复制到数组
*/
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;
}

//取出列表中指定的元素
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

return (E) elementData[index];
}

//替换指定位置的元素
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}

//添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
//和ensureExplicitCapacity的区别在这里
//如果是一开始没有指定大小的初始化list,则比较默认的容量和传入的值哪个大,就用哪个
//反正不要小于10即DEFAULT_CAPACITY
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

//添加元素到指定位置,指定位置和之后的元素后移一个位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

//删除指定位置的元素,就是将指定位置后面的元素都往前挪一个位置,再把最后一个元素置空,交给垃圾回收器处理
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

modCount++;
E oldValue = (E) 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;
}

//移除指定元素对象
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;
}

//上面的内部方法,原理主要还是找出那个对象的位置,然后跟remove(index)类似
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
}

//将所有元素置空,交给gc处理
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

//将c集合转化为数组,然后拷贝到list数组后面
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;
}

//上面一个方法指定位置的拷贝
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

//保护方法,不是供程序员调用的,核心还是拷贝方法,将移除的那些置空
protected void removeRange(int fromIndex, int toIndex) {
// Android-changed : Throw an IOOBE if toIndex < fromIndex as documented.
// All the other cases (negative indices, or indices greater than the size
// will be thrown by System#arrayCopy.
if (toIndex < fromIndex) {
throw new IndexOutOfBoundsException("toIndex < fromIndex");
}

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;
}

//序列化的写入,读取,迭代器部分
...

}

其他注意的就是ArrayList基于数组实现,可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,插入删除元素的效率低;在查找给定元素索引值等的方法中,源码都将该元素的值分为null和不为null两种情况处理,ArrayList中允许元素为null。

自己先看一遍源码再看别人的分析效果棒棒的。

参考

ArrayList源码剖析