ArrayList简介(jdk1.8)

ArrayList就是动态数组,其容量能够自动增长。如下为ArrayList的继承体系结构:

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

ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable接口,且不是线程安全的,因此只能用在单线程环境下。

属性

ArrayList主要有elementData和size两个属性:

1
2
transient Object[] elementData; 
private int size;

elementData数组是用来存储元素的,而size表示ArrayList中已有的元素数量(不等于elementData.length)。

构造方法

ArrayList共有三种构造方法:

  • 指定容量的构造函数
1
2
3
4
5
6
7
8
9
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);
}
}

此方法接受一个初始化容量来初始化底层数组elementData,如果初始化容量值为0则将其初始化为一个空的常量数组:private static final Object[] EMPTY_ELEMENTDATA = {}; ,如果值小于零,则抛出异常。

  • 无参构造函数
1
2
3
4
5
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

此方法中的DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别于EMPTY_ELEMENTDATA,通过将数组设为前者,在添加元素的时候会将容量设置为默认值10。

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

此方法接受一个Collection,并且将其转换为数组赋给elementData,如果被赋值后的elementData长度为0,则将空的常量数组赋值给它。相反,则再判断Collection是否转化为了Object数组,如果没有则将其进行转化。

这里用到了Arrays.copyof()方法:

1
2
3
4
5
6
7
8
9
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

可以看出,该方法构造了一个新的长度为newLength的Object类型数组,并且将原数组复制到新的数组中 。而此处的复制用了System.arraycopy()方法,该方法被标记了native,调用了系统的C/C++代码,可以在openJDK中查看到源码。

get

1
2
3
4
5
6
7
8
9
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

E elementData(int index) {
return (E) elementData[index];
}

此方法可以得到指定下标的元素,先对下标进行越界检查,然后再通过一个间接方法获取到elementData的index下标的元素。

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

此方法用于设置指定下标的元素,并将该下标原有的元素返回。

add

add方法比较复杂,也是ArrayList核心所在,有下面两种形式:

  • 将元素加入到列表末尾
1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
1
2
3
4
5
6
7
8
9
10
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

此处的calculateCapacity正是与上文DEFAULTCAPACITY_EMPTY_ELEMENTDATA常量相照应的方法。如果ArrayList是默认构造函数构造的话,在添加元素的时候此方法将返回DEFAULT_CAPACITY也就是10。而size已经大于10的情况,该方法便也失去了意义。

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

private void ensureExplicitCapacity(int minCapacity) {
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);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

从源码可以看出,当需要的容量大于elementData数组的长度时,就需要对其进行扩张。而扩张的大小则根据if条件判断。一般情况下,会将长度扩张为原来的1.5倍,但是当1.5倍仍小于所需的容量时,会将长度直接设为所需容量。而新容量如果大于最大数组长度MAX_ARRAY_SIZE ,则根据所需容量分配Integer.MAX_VALUE或者MAX_ARRAY_SIZE。

ensureExplicitCapacity方法的第一行语句modCount++;的作用是记录修改次数。我们知道,ArrayList不是线程安全的,因此在迭代ArrayList的时候如果有其它线程修改了内容,那么就会导致modCount与迭代器初始化时的modCount不同,从而抛出异常ConcurrentModificationException。说白了,就是防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。

  • 将元素添加到指定位置上
1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

在此方法中,先对index进行越界检查,然后再进行扩容。这里用了System.arraycopy方法,j将包括index在内的之后的所有元素均向右移动一位,再将要添加的元素放置在elementData的index下标下。

addAll

  • 将集合中的元素全部添加到ArrayList末尾
1
2
3
4
5
6
7
8
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;
}

将Collection对象转化为Object数组后,先根据其长度进行扩容,再同样利用System.arraycopy函数把数组中的所有元素添加到elementData数组末尾。

  • 将集合中的元素全部添加到ArrayList指定位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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(int index, E element)类似,都是通过将已有元素右移实现,此处将不再阐述。

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

在这里,移除操作是将要移除的元素后面的所有元素均向左移动一位,并将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
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
}

先找到指定元素的下标,再根据下标进行移除。指定的元素有可能为null,而不为null的情况下将根据元素内容进行比较,因此将分为两种情况遍历数组。fastRemove的实现与remove(int index)基本一致,区别在于fastRemove不需要对下标进行检查,也不返回被移除的元素。

indexOf

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

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

public boolean contains(Object o) {
return indexOf(o) >= 0;
}

由源码可以看出,indexOf和lastIndexOf与remove(Object o)方法类似,并且找到元素时返回下标,没找到时返回-1,而contains方法正是通过indexOf判断是否找到元素实现的。

遍历时删除

ArrayList循环遍历并删除元素的常见陷阱

ArrayList总结

  • ArrayList底层是通过数组实现的,随机访问速度快,但插入和移除由于要移动大量的元素,所以性能较差。
  • ArrayList不是线程安全的,在多线程环境下,通过modCount域检测是否出现问题。
  • ArrayList每次扩容为原本的1.5倍,若依然不够,则会直接设置为所需容量大小。