Java ArrayList源码浅析

简介

ArrayList 是集合中最常见一个实现类,ArrayList继承AbstractList抽象类,实现List接口。

ArrayList UML图

ArrayList

ArrayList 定义

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

ArrayList简单而言就是一个动态数组,它的容量是动态增长的,默认容量是10。它继承了AbstractList,实现了List、RandomAccess、Cloneable及Serializable接口。

  1. RandomAccess:支持随机访问标记
  2. Serializable:支持序列化

ArrayList属性

1
2
3
4
// 保存元素的数组
transient Object[] elementData;
// 数组实际大小(元素总数)
private int 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
// 构造一个默认容量(10)的ArrayList
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 构造一个指定容量的ArrayList
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);
}
}
// 构造一个包含指定集合元素的ArrayList,这些元素的是按照Collection的迭代器返回的顺序排列的
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;
}
}

方法摘要

返回类型 方法名称 描述
boolean add(E e) 增加指定的元素
void add(int, index, E e) 在指定位置元素
boolean addAll(Collection<? extends E> c) 增加指定集合的所有元素
boolean addAll(int index, Collection<? extends E> c) 在指定位置开始增加集合的所有元素
void clear() 清空所有元素
Object clone() 克隆副本
boolean contains(Object o) 判断是否包含指定的元素。如存在返回true,否则返回false
void ensureCapacity(int minCapacity) 如有必要增加容量,确保至少能容纳指定的(minCapacity)元素
void forEach(Consumer<? super E> action) 迭代执行每个元素的业务逻辑直至完成或抛出异常
E e get(int index) 返回指定位置的元素
int indexOf(Object o) 返回列表中首次出现指定元素的位置,不存在返回-1
boolean isEmpty() 判断集合是否为空
Iterator iterator() 返回此集合元素的迭代器
ListItrator listIterator() 返回列表中元素的列表迭代器(按适当的顺序)。
ListItrator listIterator(int index) 返回从指定位置开始的列表迭代器(按适当的顺序)。
boolean remove(Object o) 删除指定的元素
E remove(int index) 删除列表指定位置的元素
boolean removeAll(Collection<?> c) 删指定集合的所有元素
boolean removeIf(Predicate<? super E filter) 删除满足条件的所有元素
void removeRange(int fromIndex, int toIndex) 删除列表中fromIndex(含)到toIndex(含)之间的所有元素
E set(int index, E e) 用指定的元素替换列表中指定位置的元素
int size() 解析 返回集合元素大小
void sort(Comparator<? super E> c) 排序
List subList(int fromIndex, int toIndex)
Object[] toArray()
T [] toArray(T [])
void trimToSize() 容量调整为当前元素大小

核心源码(基于1.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
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
/**
* 增加一个元素
*/
public boolean add(E e) {
// 扩容检查
ensureCapacityInternal(size + 1); // Increments modCount!!
// 添加元素到数组末尾
elementData[size++] = e;
return true;
}
/**
* index位置增加一个元素
*/
public void add(int index, E element) {
// 越界检查
rangeCheckForAdd(index);
// 扩容检查
ensureCapacityInternal(size + 1); // Increments modCount!!
// 拷贝数组,目的就空出index位置插入element,并将index之后的元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将数组index位置赋值
elementData[index] = element;
// 实际大小+1
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;
}
/**
* 在指定位置增加一个集合
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 越界检查
rangeCheckForAdd(index);
// 转换为数组
Object[] a = c.toArray();
int numNew = a.length;
// 扩容检查
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算要移动的长度(index之后元素个数)
int numMoved = size - index;
if (numMoved > 0)
// 拷贝数组,目的就空出index~index + numNew,位置插入element,并将index之后的元素后移一位
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) {
// 如果当前数组为空,取minCapacity与缺省容量(10)较大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 扩容
ensureExplicitCapacity(minCapacity);
}
/**
* 扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果minCapacity大于当前数据容量增进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容
*/
private void grow(int minCapacity) {
// 当前数组容量
int oldCapacity = elementData.length;
// 扩容后数组容量。即原来的1.5倍, oldCapacity>>1相当于oldCapacity/2取整
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后比需要的最小容量还小,则用最小需要容量扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果扩容后大于Integer.MAX_VALUE - 8,则用Integer.MAX_VALUE扩容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 进行数据拷贝,Arrays.copyOf底层实现是System.arrayCopy()
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;
}
扩容过程
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9
插入元素过程
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5
0 1 2 3 4 5 6 7 8 9
0 1 2 9 3 4 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
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
/**
* 删除指定位置的元素
*/
public E remove(int index) {
// 越界检查
rangeCheck(index);
modCount++;
// 取出要删除的元素
E oldValue = elementData(index);
// 计算要复制(移动)的数量
int numMoved = size - index - 1;
if (numMoved > 0)
// index之后的元素前移一位
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) {
// 非空判断
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
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 容量缩小为实际元素大小
*/
public void trimToSize() {
modCount++;
// 实际元素数小于数组容量
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

ArrayList遍历元素

1. 通过迭代器遍历

1
2
3
4
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}

2. 随机访问,然后通过索引值遍历

1
2
3
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
}

####3. foreach

1
2
3
for(Integer i : list) {
System.out.println(list.get(i));
}

总结

  1. ArrayList是基于动态数组实现的数据结构
  2. 扩容时会扩充为原容量的1.5倍
  3. 删除元素时不会自动缩容,但提供了trimToSize()方法缩容为实际元素大小
  4. 随机(下标)访问效率高
  5. 插入删除要移动数组,效率较低
  6. 非线程安全

本系列文章是为团队内部分享参考网络资料及个人理解整理而成

-------------本文结束感谢您的阅读-------------