Java 数据结构实现原理之 ArrayList

概述

ArrayList 是基于数组实现的一种数据结构,准确来讲是一个动态数组,其容量可以自动增长,类似 C 语言中的动态申请内存,动态增长内存。

ArrayList 是线程不安全,允许元素的值为 null .

底层实现为数组,实现了 List<E>, RandomAccess, Cloneable, java.io.Serializable 接口,RadomAccess 接口代表其支持随机快速访问, ArrayList 可以以时间复杂度为 O(1) 访问元素,原理为类似数组访问方式,可以通过下标进行快速访问,Cloneadle 接口为可“克隆”,实现 java.io.Serializable 接口表示 ArrayList 是支持序列化,数据序列化在 Android 中使用是很广泛的,不管是在进程通信、本地数据存储还是网络数据传输中。

其底层数据结构为数组,所以根据数组的实现可知,它占据一个以数组的 Length 为大小的连续内存区域 ,所以容量为数组的 Length ,同时也具有数组的缺点,空间效率不高

由于数组内部的内存是连续的,所以可以通过 O(1) 的时间来读写 ArrayList 里的数据,具有较高的时间效率

当集合中的元素超出这个容量,便会进行扩容操作。扩容操作也是 ArrayList 的一个性能消耗比较大的地方,所以若可以提前预知数据的规模前提下,可以通过 public ArrayList(int initialCapacity) {}构造方法,指定集合的大小,去构建ArrayList实例,以减少扩容次数,提高效率

或者在需要扩容的时候,手动调用public void ensureCapacity(int minCapacity) {}方法扩容。
不过该方法是 ArrayList 的API,不是List接口里的,所以使用时需要强转:
((ArrayList)list).ensureCapacity(30);

当每次修改结构时,增加导致扩容,或者删,都会修改 modCount 。modCount 是一个由 transient 关键字修饰的 int 类型变量, 主要作用是用来做线程安全检查,在 ArrayList 内部使用迭代器(Iterator、for each)遍历的时候,用来检查列表中的元素是否发生结构性变化(列表元素数量发生改变),主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。相关运行时异常:ConcurrentModificationException .

异常相关拓展:

Java_Arraylist_ConcurrentModificationException.jpg

由于实现了 Serilizable 接口,对象会自动序列化,而 transient 关键字的作用是将数据存放在内存中而不是持久化,transient 只能修饰变量,不能修饰类和方法,被 transient 修饰的变量不能再被序列化,一个静态变量不管是否被 transient 修饰,均不能被序列化。

原理分析

分析思路为从构造方法入手,主要梳理增删查改等操作的逻辑。

构造方法
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
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认构造函数里的空数组, 与上述空数组区分的原因为知道当第一个元素
// 添加过来的时候需要扩展多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储集合元素的底层实现:真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
// 当前元素数量
private int size;
// 默认构造方法
public ArrayList() {
// 将 空数组 赋值给了 elemtData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 带初始容量的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 当初始容量 > 0
// 新建一个长度为 初始容量 的 Object 数组 并赋值给 elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 从其他集合类来构建 ArrayList 的构造方法
public ArrayList(Collection<? extends E> c) {
// 直接从 Collection.toArray() 方法中得到一个对象数组,并赋值给 elementData
elementData = c.toArray();
// 这里区别与上一个构造方法, 因为从其他集合类延伸过来,需要给 size 赋值
// size 表示的是元素的数量
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 {
// 长度为 0 ,直接赋一个空数组
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

小结

构造方法执行完毕,会构建出一个数组 elementData 和数量值 size

关于 Collection.toArray() 方法,在 Collection 子类的各大结合方法中,高频使用了这个方法来获得某 Collection 的所有元素。

关于 Arrays.copyOf(elementData, size, Object[].class) 方法,是根据 class 的类型来决定 new 一个还是反射去构造一个泛型数组,同时利用 native 函数,批量复制到新数组中。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//根据 class 的类型来决定是 new 还是反射去构造一个泛型数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 利用 native 函数,批量赋值元素至新数组中。
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
return copy;
}
// System.arraycopy 函数
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
……
常用 API

1. 增删查改

:add 之前,判断 add 之后的容量,是否需要扩容

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
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//在数组末尾追加一个元素,并修改size
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 利用 == 判断数组是否是用默认构造函数初始化的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
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;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 如果确定要扩容,会修改 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);
}
// 带 index 的 add
public void add(int index, E element) {
rangeCheckForAdd(index);// 越界判断 如果越界抛异常
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //将 index 开始的数据 向后移动一位
elementData[index] = element;
size++;
}
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
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) {
rangeCheckForAdd(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;
}

小结

add、addAll 方法会先判断是否越界,是否需要扩容,如果需要扩容就复制数组,而后设置对应下标值的数据。

Notes

1. 如果需要扩容的话,默认扩容一半。如果扩容一半不够,就用目标的size作为扩容后的容量。
2. 在扩容成功后,会修改modCount

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
public E remove(int index) {
rangeCheck(index); // 判断是否越界
modCount++; // 修改 modCount 因为结构改变了
E oldValue = elementData(index);// 读出要删除的值
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);;// 用复制 覆盖数组数据
//置空原尾部数据 不再强引用, 可以GC掉
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// elementData 是根据数组下标取值,并强制类型转换
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
// 删除该元素在数组中第一次出现的位置上的数据。 如果有该元素返回true,如果false。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index); //根据index删除元素
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 私有方法 fastRemove 不进行越界判断,不取出元素,直接删
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 // 置空
}
// 批量删除
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);// 判空
return batchRemove(c, false);
}
// 私有方法 批量移动
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; // w 代表批量删除后 数组还剩多少元素
boolean modified = false;
try {
// 高效 保存两个集合公有元素的算法
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)// 如果 c 里不包含当前下标元素
elementData[w++] = elementData[r];// 则保留该元素
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) { // 发生异常会导致 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; // 修改 modCount
size = w; // 修改 size
modified = true;
}
}
return modified;
}

从这里可以看出,当用来作为删除元素的集合里的元素多余被删除集合时,只会删除它们共同拥有的元素,并不会出现异常

小结:
1 删除操作一定会修改modCount,且可能涉及到数组的复制相对低效
2 批量删除中,涉及高效的保存两个集合公有元素的算法

改 :

不会修改 modCount

1
2
3
4
5
6
public E set(int index, E element) {
rangeCheck(index);//越界检查
E oldValue = elementData(index); //取出元素
elementData[index] = element;//覆盖元素
return oldValue;//返回元素
}

查 :

不会修改 modCount

1
2
3
4
5
6
7
public E get(int index) {
rangeCheck(index);//越界检查
return elementData(index); //下标取数据
}
E elementData(int index) {
return (E) elementData[index];
}

清空:

会修改 modCount

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

包含 contain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// for 循环寻找值,会根据目标对象是否为 null 分别循环查找。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// for 循环寻找值,会根据目标对象是否为 null 分别循环查找。
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;
}

判空 isEmpty()

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

迭代器 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return // 默认是 0
//上一次返回的元素 (删除的标志位)
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; // 是否修改过结构
public boolean hasNext() {
return cursor != size; // 游标是否移动至尾部
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size) // 判断是否越界
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
// 再次判断是否越界,在 我们这里的操作时,有异步线程修改了 List
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i]; //返回元素 ,并设置上一次返回的元素的下标
}
public void remove() { // remove 掉上一次 next 的元素
if (lastRet < 0) // 先判断是否 next 过
throw new IllegalStateException();
checkForComodification();// 判断是否修改过
try {
//删除元素 remove方法内会修改 modCount 所以后面要更新Iterator里的这个标志值
ArrayList.this.remove(lastRet); //要删除的游标
cursor = lastRet; //不能重复删除 所以修改删除的标志位
lastRet = -1;
expectedModCount = modCount;// 更新 判断集合是否修改的标志
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//判断是否修改过了 List 的结构,如果有修改,抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

总结

  1. 增删改查中, 增导致扩容,则会修改modCount删一定会修改改和查一定不会修改modCount
  2. 扩容操作会导致数组复制,批量删除会导致 找出两个集合的交集,以及数组复制操作,因此,增、删都相对低效。 而 改、查都是很高效的操作。
  3. 因此,结合特点,在使用中,以Android中最常用的展示列表为例,列表滑动时需要展示每一个Item(element)的数组,所以 查 操作是最高频的。相对来说,增操作 只有在列表加载更多时才会用到 ,而且是在列表尾部插入,所以也不需要移动数据的操作。而删操作则更低频。 故选用ArrayList作为保存数据的结构。
  4. 另与Vector的区别,大致浏览Vector的源码,内部也是数组做的,区别在于Vector在API上都加了 synchronized所以它是线程安全的,以及 Vector扩容时,是翻倍 size,而 ArrayList是扩容50%。
坚持原创技术分享,您的支持将鼓励我继续创作!
0%