ArrayList源码分析

接下来的一段时间,重点来学习java中的集合类。List作为一种使用非常广泛的数据结构,在jdk中典型实现有ArrayList、LinkedList等。今天就先来分析一下ArrayList的源码,以下基于jdk7来说明。

首先,先看一下ArrayList的声明。

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

ArrayList扩展AbstractList抽象类,实现List接口,看起来是很自然的。但RandomAccess接口是什么?

查看RandomAccess接口,能够发现其定义如下:

public interface RandomAccess {}

可以发现,RandomAccess接口是一个空接口,并不包含任何函数的定义。其主要的作用是用来标记:List的实现可以用来进行快速的常量时间的随机访问。

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access.

ArrayList还继承了Clonable,表示ArrayList可以执行克隆操作。继承了Serializable,表示ArrayList支持进行序列化,通过序列化来传输。

在ArrayList文件的起始部分,定义了如下的几个字段。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;

分别来说明一下,这几个字段的作用。

  1. DEFAULT_CAPACITY表示了ArrayList的起初默认容量。
  2. EMPTY_ELEMENTDATA表示了一个共享的数组,所有的空ArrayList的内部数组都指向这个共享数组。
  3. elementData表示在ArrayList非空的时候,真实的数据存储的数组。
  4. size表示ArrayList当前存储的数据个数。

ArrayList共有三个构造函数,分别为无参数、接受一个初始容量参数和接受一个Collection类型的参数。

  1. 无参数的构造函数
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

在无参数的构造函数中,ArrayList实例存储数据的数组指向共享的空数组。

  1. 接受初始容量的构造函数
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0) {
        throw new IllegalArugmentException("Illegal Capacity:" + initialCapacity);
    }
    this.elementData = new Object[initialCapacity];
}   

在这个构造函数中,根据给定的容量大小,来构造一个对应大小的数组来存储数据。

  1. 接受Collection类型的参数
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class) {
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
}

在这个版本的构造函数中,使用一个给定的Collection来构造ArrayList,并将size的大小设置为Collection的长度。

说完了构造函数,下面就来看一下一些重要的函数实现吧。

首先是add操作。我们已经知道,在ArrayList中内部是使用一个数组来存储数据,而数组是有着固定容量的。在执行add操作的时候,如果当前数组已满,则需要进行扩容的操作,即先构造一个更大的数组,然后将原来数组中的对象复制到新的数组中。那这些操作,在jdk的源码中是如何实现的呢?

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

在上面的代码中,确保数组大小足够容纳新的元素,以及扩容旧数组的操作都是在辅助函数ensureCapacityInternal中进行的。而ensureCapacityInternal的定义如下

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

从上面的代码中可以发现,当对空的ArrayList执行第一次add操作的时候,会确保构造的数组的最小容量为DEFAULT_CAPACITY。这样,可以确保后续不会频繁的进行数组的扩容。

继续分析上面的ensureExplicitCapacity函数。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

代码中的modCount,主要是用来支持ArrayList的fail-fast机制。fail-fast机制是用于检测在进行元素迭代的过程中,有没有其他的线程对List进行结构性的修改(包括add、remove等)。主要作用原理是,在进行迭代之前,检查modCount的值,如果在迭代的过程中,发现modCount值有了改变,则会抛出ConcurrentModificationException。

grow函数的定义如下

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上面代码中可以发现,执行扩容之后,数组的容量变为原来的1.5倍。

MAX_ARRAY_SIZE的定义如下

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

当需要的新的容量大小大于MAX_ARRAY_SIZE的时候,则由hugeCapacity函数来进行容量的分配。

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

由上可以看出,ArrayList的内部数组elementData最大容量为Integer.MAX_VALUE。

分析了以上辅助函数之后,再回过头来看add函数。逻辑是不是清晰了很多呢。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

总结一下add操作中的判断逻辑。

  1. 判断当前数组能否容纳下size + 1个元素,记位minCapacity。在当前ArrayList是使用无参构造函数构造,并当前内部包含数任何元素的情况下,将minCapacity记为Max(DEFAULT_CAPACITY, minCapacity)。
  2. 如果minCapacity小于当前数组的长度,则需要进行扩容。首先将数组的长度扩充为原来的1.5倍。如果仍小于minCapacity的长度,则新长度则记为minCapacity。
  3. 如果新长度大于MAX_ARRAY_SIZE,则将数组长度设定为Integer.MAX_VALUE。

上述的add函数,是在List的末尾插入元素。如果需要在给定的index上插入新元素,则需要使用add(int index, E e)。函数的实现如下

public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

rangeCheckForAdd函数的作用是判断给定的index是否合法,合法的index的范围为[0, size]。函数定义如下

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

System.arrayCopy函数需要来说一下。arrayCopy函数是一个native函数,即不是使用java来实现的函数。其函数声明如下

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

src和dest为源数组和目标数组自不必说。srcPos为源数组中开始的序号,destPos为目标数组的开始序号,length为需要复制的长度。回到上面add函数中的调用,即使将elementData中从index序号开始的size - index个元素复制到elementData中,从第index + 1个序号开始。需要复制的元素的计算方法为 (size - 1 - index + 1)。

System.arrayCopy(elementData, index, elementData, index + 1, size - index);

这个函数很关键,在ArrayList的实现中发挥了巨大的作用。涉及到数组复制的操作,都使使用的它,应该好好的理解。

说完了add,接下来看一下remove。

public E remove(int index) {
    rangeCheck(index);
    
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - 1 - index;
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null;
    return oldValue;
}

参考上面所说的System.arraycopy函数的使用说明,remove函数中没有别的需要着重说明的地方。

除此之外,remove还有另外一个版本,参数为Object o。其实现为

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

在上面remove的实现中,使用了fastRemove函数。其实,fastRemove函数的实现方式和remove(int index)的实现如出一辙,只不过去除了rangeCheck的调用,无序在函数内部进行index是否合法的判断。因为,在调用上可以保证index一定合法。种种的小细节,保证了jdk的高效。

前面说到了ArrayList实现了RandomAccess接口,支持随机的、常量时间的访问,主要是从如下的接口函数中体现出的。

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

public E set(int index, E element) {
    rangeCheck(index);
    
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

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

rangeCheck函数的作用主要是用于检测给定的index是否合法,合法的index数值应该处于[0, size - 1]。之所以没有判断index是否是负数,是因为接下来的操作总是一个数组访问。如果是负数的话,接下来的操作也会抛出ArrayIndexOutOfBoundsExcepiton。

private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

除了以上提到的add和remove,在ArrayList中还存在着addAll、removeAll 等相关操作,在此不再进行说明。

ArrayList中存在三个返回迭代器的方法,分别为

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

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index:" + index);
    }
    return new ListItr(index);
}

其中,Itr类继承了Iterator接口,而ListItr扩展了Itr类,继承了ListIterator接口。Iterator只允许从前向后遍历,而ListIterator接口则可以向两个方向来进行遍历。listIterator(int index)则指定了迭代器开始迭代的起始序号。

在Itr类的实现中,有一个函数checkForComdification()。其实现为

final void checkForComodification() {
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

这就是上文中提到的fail-fast机制。在对ArrayList进行遍历的时候,如果有别的线程对List进行了结构性的修改,则会抛出ConcurrentModificationException异常。不过,用户的代码不能依赖此机制,因为jdk并不保证此异常抛出的时机。但通常意义上,会很快。

下面来说一下subList函数。其实现如下

public List<E> subList(int fromIndex, int toIndex) {
    subListRnageCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

可以看出,调用subList之后,返回的结果并不是ArrayList,而是另外的一个类SubList。SubList是ArrayList的内部类,可以将subList操作返回的结果,看作是ArrayList的一个视图。两者之间是联动的,对于subList操作结果的操作,都会反映到ArrayList中去。

最后,再着重的说一下toArray(T[] a)函数。这个函数的使用频率较高,可以方便的来完成ArrayList到数组的转换。在不了解其实现的情况下,可能会写出如下的调用代码。

List<String> names = new ArrayList<>();
names.add("feng");
// some other adds
String[] nameArrays = names.toArray(new String[names.size()]);

不过实际上,最简单的调用代码应该是如下的方式。

String[] nameArrays = names.toArray(new String[0]);

这是为何呢?还是从其实现上来发现吧。

public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        return (T[]) Arrays.copy(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
        a[size] = null;
    }
    return a;
}

可以看出,在其实现中,首先进行了数组长度的判断。在长度小于ArrayList的size情况下,也是会按照ArrayList的size来进行数组的复制。因此,通常情况下,只要传入长度为0的数组即可。当然了,如果需要得到一个长度大于size的数组,则仍需要手动的来设定。

ArrayList中的其它一些操作函数,如size()、isEmpty()、contains()、indexOf()、lastIndexOf()等比较简单,不再赘述。

Comments
Write a Comment