从源码上分析 ArrayList

前言

ArrayListList 接口的一个实现类,那么 ArrayList 的底层是如何实现的呢?让我们来一探究竟。

源码分析

属性

先来看看 ArrayList 中比较重要的两个属性:

1
2
3
transient Object[] elementData; 

private int size;

  • elementData 用来存储 ArrayList 中的元素,其实 ArrayList 的底层是用 Object[] 数组来实现的。
  • size 指的是的逻辑长度,就好像一个水杯,容量是 600 毫升,但杯中只有 200 毫升的水,ArrayList 容器就是水杯, 这个 size 属性表示的就是水杯中水的容积。

构造方法

无参构造方法:

1
2
3
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

很简单,就一行语句,elementData 在上面我们已经知道是什么了,那 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 又是什么呢?

1
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

原来只是一个空的 Object[]

指定容量的构造方法:

1
2
3
4
5
6
7
8
9
10
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 指定初始容量。这里主要对传入的容量做了有效性验证,当传入的参数小于 0 时,抛出异常。当参数等于 0 时,则用一个空的数组常量 EMPTY_ELEMENTDATA 来初始化。

用一个 Collection 对象进行构造的的构造方法:

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

首先将传入的参数转为对象数组赋值给 elementData ,如果传入的 Collection 参数的长度为 0,则就将空的常量数组对象 EMPTY_ELEMENTDATA 赋给了 elementData

常用方法

add

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

调用了 ensureCapacityInternal 函数:

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

这里判断 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示如果如果为没有初始化容量时,用默认容量 DEFAULT_CAPACITY 也就是 10,来开启空间,也就是上面我们说的水杯的容量。

接下来看 ensureExplicitCapacity 方法:

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

继续看 grow 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;

// 对 ArrayList 容量进行 1.5 倍扩容。
int newCapacity = oldCapacity + (oldCapacity >> 1);

// 如果扩容后的容量还不够实际占用的容量,那么需要扩容到实际占用容量的大小。
// 如当前 newCapacity 为 10,扩容后为 15,
// 但现在实际的元素数量为 16 个,那么至少应该先装下这 16 个。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;

// 防止阔中的过大,过大时,则使用 Integer.MAX_VALUE 代替。
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);
}

其实这段代码也很简单,就是动态扩容 ArrayList 的大小,每次扩容都为当前容量的 1.5 倍,当然也进行了扩容过大或过小的限制。
其扩容原理就是创建一个容量为当前容量 1.5 倍的新数组,将旧数组的内容拷贝给新数组。

add(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
public void add(int index, E element) {
// 判断要插入的位置不小于 0 且不大于当前最大位置
rangeCheckForAdd(index);

// 容量扩容检测,具体参见 add(E e) 方法
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

看过了 add(E e) 的源码,这里也就很好理解了,先进行插入位置有效性判断,然后判断容量是否需要扩容,然后先将插入位置开始的所有元素向后移动一位,最后将需要插入的元素插入指定位置。

get

1
2
3
4
5
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

ArrayList 的底层是用数组实现的,那么获取元素也就很方便了,判断获取位置合法后,直接用下标获取即可。

set

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

这个方法其实就是修改指定位置的元素,先拿到要覆盖的元素,然后将新元素赋值上去,最后返回覆盖的元素即可。

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

先进行有效性判断,然后从要删除的元素开始的所有元素都向前拷贝一位,并将最后一位设值为 null

indexOf

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

如果要找的内容 null,则依次用 == 判断是否为要找的元素,如果不为 null,则用 equals 来依次判断。

总结

根据上方的源码分析,我们可以得出 ArrayList 的一些特性:

  • ArrayList 底层数据结构是对象数组,如不指定长度,则初始容量为 10。
  • 底层的对象数组是在第一次添加元素的时候才进行初始化的。
  • 每次扩容为原来容量的 1.5 倍,扩容原理是将原来的数据拷贝到新数组中。

所以我们在使用时要注意:

  • 如知道大概要存多少个数据,最好指定初始化容量,这样可以提高程序性能。
  • ArrayList 查找元素很快,但删除元素和添加元素的效率相对较差。