0%

ArrayList详解

ArrayList详解

List中使用最多的就是ArrayList,基本上大家在实例化一个List的时候都是

1
List list = new ArrayList();

所以在这里了解一下ArrayList的实现过程(以java8为例)

主要特点

  • 有序存储元素
  • 允许元素重复,允许存储null值
  • 支持动态扩容
  • 非线程安全

继承关系

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

继承了AbstractList类,实现了List接口、RandomAccess接口、Cloneable接口和Serializable接口,所以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
/**
* 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 默认的空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 默认无参构造器使用的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* ArrayList底层用来存储数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* ArrayList实际的长度
*/
private int size;

/**
* 可分配的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 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
/**
* 自定义初始化容量,根据传入的初始化容量来确定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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
* 通过集合来进行初始化,使用了Arrays.copyOf来将集合中的数据copy到数组中
*/
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}

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
public boolean add(E e) {
// 在添加元素之前先确认一下容量是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

// minCapacity为当前所需要的最小容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果在进行初始化的时候使用的无参构造器,此时才会给赋初始容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
// 计算修改次数
modCount++;

// 需要的容量大于数组容量的话,需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 当原数组为空数组时,newCapacity为0,是小于minCapacity 10 的
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);
}

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E remove(int index) {
// 数组下标检查
rangeCheck(index);
// 计算修改次数
modCount++;
// 获取该所索引位置下原来的的元素
E oldValue = elementData(index);
// 所要移动的数量
int numMoved = size - index - 1;
if (numMoved > 0)
// 第一个参数为源数据
// 第二个参数为从源数据的哪个位置开始复制
// 第三个参数为目标数据
// 第四个参数为从目标数据的哪个位置开始被复制
// 第五个参数为被复制的元素数量
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // index所对应的元素被删除,后续所有的元素向前移动一位
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

其他的方法都是中规中矩的操作数组

如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// get
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

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

迭代器

在使用foreach循环遍历的时候实际上是使用的迭代器,对于ArrayList而言,使用普通的for循环会比使用foreach效率更高

接下来看一下ArrayList的迭代器

1
2
3
public Iterator<E> iterator() {
return new Itr();
}

Itr是ArrayList的内部类,实现了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
72
73
74
75
76
77
private class Itr implements Iterator<E> {
// 游标
int cursor; // index of next element to return
// 最后一次返回的索引位置
int lastRet = -1; // index of last element returned; -1 if no such
// 当Itr被实例化的时候,记录一下迭代器被实例化时ArrayList的修改次数(在用ArrayList进行add/remove操作时modCount每次都加一)
int expectedModCount = modCount;

Itr() {}

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;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 游标加一,指向下一个元素位置
cursor = i + 1;
return (E) elementData[lastRet = i];
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 检查是否被修改了
checkForComodification();

try {
// list移除元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 移除之后会将修改次数modCount重新赋给expectedModCount
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();
}

// 检查是否被修改了
final void checkForComodification() {
// 当修改次数与Itr被实例化时的修改次数不一致时,说明在进行迭代操作的时候其他线程进行了ArrrayList的add/remove操作,此时抛出ConcurrentModificationException,即为fast-fail快速失败机制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

使用说明

  • 由于ArrayList的默认初始值为10,扩容为1.5倍,如果集合中所需要存储的元素数量多的话,需要进行多次扩容,重新申请内存并进行赋值,比较耗时,所以如果在进行实例化时指定初始容量,可以减少扩容次数,提升性能

  • 在遍历删除的时候注意了,不要使用foreach来循环遍历list删除数据,最好使用iterator进行遍历删除