重温JDK源码之ArrayList

重温集合源码系列 之 ArrayList 篇(基于 JDK1.8)

重温 JDK 源码之 ArrayList

一、ArrayList 定义


1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

ArrayList 是一个动态数组队列,其特点就是能够动态扩展数组容量。

  • 继承了 AbstractList 类,实现了 List 接口,提供了相关的增删查改等操作,并且其操作对象为包括 null 在内的所有类。

  • 实现了 RandomAccess 接口,提供了快速随机访问的功能(可以通过元素序号快速获得元素对象)。

  • 实现了 Cloneable 接口,覆盖了 clone() 方法。

  • 实现了 Serializable 接口,支持 Java 序列化传输。

  • 对于 ArrayList 的操作不是线程安全。所以在多线程中使用 ArrayList 时,需要注意一下线程控制。如:

    List<Integer> list = Collections.synchronizedList(new ArrayList<>());

二、ArrayList 重要属性


1
2
3
4
5
6
// 初始化默认数组大小
private static final int DEFAULT_CAPACITY = 10;
// 记录动态数组实际大小
private int size;
// Object[] 类数组,用于存储真实的元素对象
transient Object[] elementData; // non-private to simplify nested class access

三、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
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);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}

ArrayList 类提供了三个构造方法。

构造方法一 : 调用默认的共享数组实例,一个初始容量为10 的空数组。

构造方法二 : 根据initialCapacity 来初始化 elementData 数组的大小。

构造方法三 : 将提供的集合转换为数组并返回给 elementData。

  • 调用 toArray() 方法将集合转换为数组。
  • 若数组不为0,并且 toArray() 返回不是 Object[] 类,则调用 Arrays.copyOf() 方法将其转换为 Object[]。

四、ArrayList 重要方法解析


1、增加

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
// 添加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 数组容量检查
elementData[size++] = e; //将元素添加至List数据尾部,容量+1
return true;
}
// 在指定位置添加一个元素
public void add(int index, E element) {
rangeCheckForAdd(index); //检查添加范围,判断索引是否越界
ensureCapacityInternal(size + 1); // 数组容量检查
// 对数组进行复制处理,目的就是空出index的位置插入element,并将index后的元素位移一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; // 将指定的index位置赋值为element
size++; //容量+1
}
// 添加一个集合
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); //转化为数组,并一定是 Object[] 数组
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 动态检查容量
// 将整个数组复制到List数据尾部
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; // 计算需要移动的长度
// 数组复制,空出第index到index+numNum的位置,即将数组index后的元素向右移动numNum个位置
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 将要插入的集合元素复制到数组空出的位置中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//检查添加范围,判断索引是否越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 数组容量检查,不够时进行扩容
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) {
int oldCapacity = elementData.length; //当前数组长度
// 加上0.5倍容量:>> 右移运算符,相当于除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新扩容的数组长度还是比最小需要的容量小,则以最小需要的容量为长度进行扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新扩容的数组长度比数组最大容量还要大,重新检查扩容最小标准,并将结果返回给新扩容数组长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 进行数据拷贝,Arrays.copyOf底层实现是System.arrayCopy()
elementData = Arrays.copyOf(elementData, newCapacity);
}

2、删除

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
// 根据索引位置删除元素
public E remove(int index) {
rangeCheck(index); // 数组越界检查
modCount++;
E oldValue = elementData(index); // 取出要删除的元素
int numMoved = size - index - 1;
// 数组复制,将index之后的元素前移一个位置
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将数组最后一个元素置空并数量-1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 根据元素内容删除,只删除匹配的第一个
public boolean remove(Object o) {
// 对要删除的元素进行null判断
if (o == null) { // 因为 null 需要使用 == 来比较
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else { // 非 null 需要使用 equals 来比较
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
}
// 边界检查
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3、更新

1
2
3
4
5
6
7
// 更新指定索引位置的元素
public E set(int index, E element) {
rangeCheck(index); // 数组越界检查
E oldValue = elementData(index); // elementData(index)就是elementData[index]
elementData[index] = element; // 重置为新元素
return oldValue;
}

4、寻找

1
2
3
4
5
// 根据索引获取元素
public E get(int index) {
rangeCheck(index); // 数组元素越界检查
return elementData(index); // 获取元素
}

5、是否包含

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
// 检查集合是否包含某个元素
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 从头到尾遍历查询数组中元素
public int indexOf(Object o) {
if (o == null) { // 需要判断是否是 null 主要是使用 == 与 equals 的区别
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else { // 若目标元素非 null
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;
}

6、释放空间

1
2
3
4
5
6
7
8
9
// 将容量空间调整为当前实际元素数量大小,从而释放空间
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

7、其他

  • ArrayList 是一个动态扩展数组,其默认容量为10。
  • ArrayList 扩容 : 新容量 = 旧容量 + 旧容量>>2,并且扩容伴随着开辟新空间、进行数组复制。
  • ArrayList 的 clone() 方法就是将所有的元素都克隆到一个新数组。

五、ArrayList 遍历方式


ArrayList 支持三种遍历方式。

1通过迭代器(Iterator)遍历

1
2
3
4
5
Object value = null;
Iterator it = list.Iterator();
while(it.hasNext()){
value = (Object) it.next();
}

2、通过索引值遍历

1
2
3
4
5
Object value = null;
int size = list.size();
for(int i=0; i<size; i++){
value = (Object) list.get(i);
}

3、Foreach 循环遍历

1
2
3
4
object value = null;
for(Object obj : list){
value = obj;
}

4、三种遍历的效率比较

RandomAccess 遍历方法效率最高;在数量较小的情况下,Iterator 和 Foreach 的效率较为暧昧;随着数量增加,Iterator 的效率要高于 Foreach。

  • RandomAccess 遍历方法效率最高。

    ArrayList 实现 RandomAccess 接口。查看 RandomAccess 接口注释可以看到一段有趣的解释 :

    1
    2
    3
    4
    5
    6
    7
    8
    9
    * <pre>
    * for (int i=0, n=list.size(); i &lt; n; i++)
    * list.get(i);
    * </pre>
    * runs faster than this loop:
    * <pre>
    * for (Iterator i=list.iterator(); i.hasNext(); )
    * i.next();
    * </pre>
  • Iterator 的效率要高于 Foreach。

    Foreach 是调用 Iterator 来实现的,同时附带其他辅助性操作(如,赋值等),所以Iterator 的效率要高于 Foreach。

    Foreach 语法糖经过编译器处理成了Iterator的遍历,有关foreach语法糖的细节可以参考《Java语法糖之foreach》。

评论