Java——基于JDK1.8的ArrayList源码分析
1，前言
很久没有写博客了，很想念大家，18年都快过完了，才开始写第一篇，争取后面每周写点，权当是记录，因为最近在看JDK的Collection，而且ArrayList源码这一块也经常被面试官问道，所以今天也就和大家一起来总结一下
2，源码解读
当我们一般提到ArrayList的话都会脱口而出它的几个特点：有序、可重复、查找速度快，但是插入和删除比较慢，线程不安全，那么现在阿呆哥哥就会有这些疑问：为什么说是有序的？怎么有序？为什么又说插入和删除比较慢？为什么慢？还有线程为什么不安全？所以带着这些问题，我们一一的来源码中来找找答案。
一般对于一个陌生的类，我们想使用它，都会先看它构造方法，再看它的属性和方法，那么我们也按照这种方式来读读ArrayList这个类
2.1构造方法
1
2
ArrayList<String> arrayList = new ArrayList();
ArrayList<String> arrayList1 = new ArrayList(2);
一般来说我们常见使用ArrayList的创建方式是上面的这两种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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);
}
}
上面是我们两个构造方法和我们类中基本的属性，从上面的代码上来看，在创建构造基本上都没有做，且定义了两个默认的空数组，默认容器的大小DEFAULT_CAPACITY为10，还有我们真正存储元素的地方elementData数组，所以这就是为什么说ArrayList存储集合元素的底层时是使用数组来实现，OK，上面的代码除了一个transient 修饰符之外我们同学们可能有点陌生之外，其余的应该都能看的懂，transient 有什么作用还有为什么用它修饰elementData字段，这个需要看完整个源码之后，我再来给大家解释的话比较合适，这里只需要留心一下。
还有一个不常用的构造方法
1
2
3
4
5
6
7
8
9
10
11
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;
}
}
第2行：利用Collection.toArray()方法得到一个对象数组，并赋值给elementData
第3行：size代表集合的大小，当通过别的集合来构造ArrayList的时候，需要赋值size
第5-6行：判断 c.toArray()是否出错返回的结果是否出错，如果出错了就利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
第9行：如果c中元素数量为空，则将EMPTY_ELEMENTDATA空数组赋值给elementData
上面就是所有的构造函数的代码了，这里我们可以看到，当构造函数走完之后，会创建出数组elementData和初始化size，Collection.toArray()则是将Collection中所有元素赋值到一个数组，Arrays.copyOf()则是根据Class类型来决定是new还是反射来创造对象并放置到新的数组中，源码如下：
1
2
3
4
5
6
7
8
9
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
这里面System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 这个方法在我们的后面会的代码中会出现，就先讲了，定义是：将数组src从下标为srcPos开始拷贝，一直拷贝length个元素到dest数组中，在dest数组中从destPos开始加入先的srcPos数组元素。相当于将src集合中的[srcPos,srcPos+length]这些元素添加到集合dest中去，起始位置为destPos
2.2 增加元素方法
一般经常使用的是下面三种方法
1
2
3
arrayList.add( E element);
arrayList.add(int index, E element);
arrayList.addAll(Collection<? extends E> c);
让我们一个个来看看
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
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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 = 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;
}
Integer. MAX_VALUE = 0x7fffffff;
MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
第2行：调用ensureCapacityInternal()函数
第8-9行：判断当前是否是使用默认的构造函数初始化，如果是设置最小的容量为默认容量10，即默认的elementData的大小为10（这里是有一个容器的概念，当前容器的大小一般是大于当前ArrayList的元素个数大小的）
第16行：modCount字段是用来记录修改过扩容的次数，调用ensureExplicitCapacity()方法意味着确定修改容器的大小，即确认扩容
第26-30、35-44行：一般默认是扩容1.5倍，当时当发现还是不能满足的话，则使用size+1之后的元素个数，如果发现扩容之后的值大于我们规定的最大值，则判断size+1的值是否大于MAX_ARRAY_SIZE的值，大于则取值MAX_VALUE，反之则MAX_ARRAY_SIZE，也就数说容器最大的数量为MAX_VALUE
第32行：就是拷贝之前的数据，扩大数组，且构建出一个新的数组
第3行：这时候数组扩容完毕，就是要将需要添加的元素加入到数组中了
1
2
3
4
5
6
7
8
9
10
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++;
}
第2-3行：判断插入的下标是否越界
第5行：和上面的一样，判断是否扩容
第6行：System.arraycopy这个方法的api在上面已经讲过了，这里的话则是将数组elementData从index开始的数据向后移动一位
第8-9行：则是赋值index位置的数据，数组大小加一
1
2
3
4
5
6
7
8
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;
}
第2行：将集合转成数组，这时候源码没有对c空很奇怪，如果传入的Collection为空就直接空指针了
第3-7行：获取数组a的长度，进行扩容判断，再将新传入的数组复制到elementData数组中去
所以对增加数据的话主要调用add、addAll方法，判断是否下标越界，是否需要扩容，扩容的原理是每次扩容1.5倍，如果不够的话就是用size+1为容器值，容器扩充后modCount的值对应修改一次
2.3 删除元素方法
常用删除方法有以下三种，我们一个个来看看
1
2
3
arrayList.remove(Object o);
arrayList.remove(int index)
arrayList.removeAll(Collection<?> c)
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
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;
}
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
}
从上面源码可以看出，如果要移除的元素为null和不为空，都是通过for循环找到要被移除元素的第一个下标，所以这里我们就会思考，当我们的集合中有多个null的话，是不是调用remove(null)这个方法只会移除第一个出现的null元素呢？这个需要同学们下去验证一下。然后通过System.arraycopy函数，来重新组合elementData中的值，且elementData[size]置空原尾部数据 不再强引用， 可以GC掉。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
可以看到remove(int index)更简单了，都不需要通过for循环将要删除的元素下边确认下来，整体的逻辑和上面通过元素删除的没什么区别，再来看看批量删除
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
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public static <T> T requireNonNull(T obj) {
if (obj == null)
throw new NullPointerException();
return obj;
}
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;
}
第2、6-10行：对传入集合c进行判空处理
第13-15行：定义局部变量elementData、r、w、modified elementData用来重新指向成员变量elementData，用来存储最终过滤后的元素，w用来纪录过滤之后集合中元素的个数，modified用来返回这次是否有修改集合中的元素
第17-19行：for循环遍历原有的elementData数组，发现如果不是要移除的元素，则重新存储在elementData，且w自增
第23-28行：如果出现异常，则会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。
第29-36行：判断如果w!=size，则表明原先elementData数组中有元素被移除了，然后将数组尾端size-w个元素置空，等待gc回收。再修改modCount的值，在修改当前数组大小size的值
2.3 修改元素方法
1
arrayList.set(int index, E element)
常见的方法也就是上面这一种，我们来看看它的实现的源码
1
2
3
4
5
6
7
8
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;
}
源码很简单，首先去判断是否越界，如果没有越界则将index下表的元素重新赋值element新值，将老值oldValue返回回去
2.4 查询元素方法
1
arrayList.get(int index);
让我们看看源码
1
2
3
4
5
6
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
源码也炒鸡简单，首先去判断是否越界，如果没有越界则将index下的元素从elementData数组中取出返回
2.5 清空元素方法
1
arrayList.clear();
常见清空也就这一个方法
1
2
3
4
5
6
7
8
9
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
源码也很简单，for循环重置每一个elementData数组为空，修改size的值，修改modCount值
2.6 判断是否存在某个元素
1
2
arrayList.contains(Object o);
arrayList.lastIndexOf(Object o);
常见的一般是contains方法，不过我这里像把lastIndexOf方法一起讲了，源码都差不多
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
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
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;
}
通过上面的源码，大家可以看到，不管是contains方法还是lastIndexOf方法，其实就是进行for循环，如果找到该元素则记录下当前元素下标，如果没找到则返回-1，很简单
2.7 遍历ArrayList中的对象（迭代器）
1
2
3
4
Iterator<String> it = arrayList.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
我们遍历集合中的元素方法挺多的，这里我们就不讲for循环遍历，我们来看看专属于集合的iterator遍历方法吧
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
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
// Android-changed: Add "limit" field to detect end of iteration.
// The "limit" of this iterator. This is the size of the list at the time the
// iterator was created. Adding & removing elements will invalidate the iteration
// anyway (and cause next() to throw) so saving this value will guarantee that the
// value of hasNext() remains stable and won't flap between true and false when elements
// are added and removed from the list.
protected int limit = ArrayList.this.size;
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor < limit;
}
@SuppressWarnings("unchecked")
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
第1-3行：在获取集合的迭代器的时候，去new了一个Itr对象，而Itr实现了Iterator接口，我们主要重点关注Iterator接口的hasNext、next方法
第12-16行：定义变量，limit：用来记录当前集合的大小值；cursor：游标，默认为0，用来记录下一个元素的下标；lastRet：上一次返回元素的下标
第18-20行：判断当前游标cursor的值是否超过当前集合大小zise，如果没有则说明后面还有元素
第24-31行：在这里面做了不少线程安全的判断，在这里如果我们异步的操作了集合就会触发这些异常，然后获取到集合中存储元素的elemenData数组
第32-33行：游标cursor+1，然后返回元素 ，并设置这次次返回的元素的下标赋值给lastRet
3，看源码之前问题的反思
ok，上面的话基本上把我们ArrayList常用的方法的源码给看完了。这时候，我们需要来对之前的问题来一一进行总结了
①有序、可重复是什么概念？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args){
ArrayList arrayList = new ArrayList();
arrayList.add("1");
arrayList.add("1");
arrayList.add("2");
arrayList.add("3");
arrayList.add("1");
Iterator<String> it = arrayList.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
输出结果
1
1
2
3
1
可重复是指加入的元素可以重复，有序是指的加入元素的顺序和取出来的时候顺序相同，一般这个特点是List相对于Set和Map来比较出来的，后面我们把Set、Map的源码看了之后会更加理解这两个特点
② 为什么说查找查找元素比较快，但添加和删除元素比较慢呢？
我们从上面的源码得到，当增加元素的时候是有可能会触发扩容机制的，而扩容机制会导致数组复制；删除和批量删除会导致找出两个集合的交集，以及数组复制操作；而查询直接调用return (E) elementData[index]; 所以说增、删都相对低效 而查找是很高效的操作。
③ 为什么说ArrayList线程是不安全
从上面的代码我们都知道，现在add()方法为例
1
2
3
4
5
6
public boolean add(E e) {
//确定是否扩容，这里可以忽略
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
这里我们主要看两点，第一点add()方法前面没有synchronized字段、第二点 elementData[size++] = e;这段代码可以拆开为下面两部分代码
1
2
elementData[size] = e;
size++
也就是说整个add()方法可以拆为两步，第一步在elementData[Size] 的位置存放此元素，第二步增大 Size 的值。我们都知道我们的CUP是切换进程运行的，在单线程中这样是没有问题的，但是一般在我们项目中很多情况是在多线程中使用ArrayList的，这时候比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 ，所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。这样就会得到元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这样就造成了我们的线程不安全了。
大家可以写一个线程搞两个线程来试试，看看size是不是有问题，这里就不带大家一起写了。
④ transient 关键字有什么用？
唉，这个就有点意思了，这个是我们之前读源码读出来的遗留问题，那源码现在读完了，是时候来解决这个问题了，我们来看看transient官方给的解释是什么
1
当对象被序列化时（写入字节序列到目标文件）时，transient阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。
然后我们看一下ArrayList的源码中是实现了java.io.Serializable序列化了的，也就是transient Object[] elementData; 这行代码的意思是不希望elementData被序列化，那这时候我们就有一个疑问了，为什么elementData不进行序列化？这时候我去网上找了一下答案，觉得这个解释是最合理且易懂的
1
在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去,所以需要手动的序列化数组对象,所以使用了transient来禁止自动序列化这个数组
这时候我们是懂了为什么不给elementData进行序列化了，那当我们要使用序列化对象的时候，elementData里面的数据是不是不能使用了？这里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
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();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
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();
}
}
}
通过writeObject方法将数据非null数据写入到对象流中，再使用readObject读取数据
4，总结
上面我们写了这么一大篇，是时候该来总结总结一下了
①查询高效、但增删低效，增加元素如果导致扩容，则会修改modCount，删出元素一定会修改。 改和查一定不会修改modCount。增加和删除操作会导致元素复制，因此，增删都相对低效。而在我们常见的Android场景中，ArrayList多用于存储列表的数据，列表滑动时需要展示每一个Item（element）的数组，所以查询操作是最高频的，且增加操作只有在列表加载更多时才会用到 ，而且是在列表尾部插入，所以也不需要移动数据的操作。而删操作则更低频。 故选用ArrayList作为保存数据的结构
②线程不安全，这个特点一般会和Vector做比较，Vector的源码，内部也是数组做的，区别在于Vector在API上都加了synchronized所以它是线程安全的，以及Vector扩容时，是翻倍size，而ArrayList是扩容50%。Vector的源码大家可以在后面闲下来的时候看看，这里给大家留一个思考题：既然Vector是安全的，那为什么我们在日常开发Android中基本上没有用到Vector呢？大家可以闲下来的时候来寻找一下这个问题的答案
最后再啰嗦一句，写完全篇后发现 ，感觉好久没写博客手很生了，在写的过程总发现大体框架不对也在一点点的修复，后面争取坚持写下来，加油！！！
卓尔山，大地的肌肤