JCF 集合框架 ArrayList 源码剖析

/ Java / 0 条评论 / 458浏览

拓扑

collection01.png

从图中可以看到,ArrayList 实现了 List 接口,说明其基于 List 这种数据结构,这种结构优点在于可以通过索引精准访问列表元素,并且比数组更加灵活。

ArrayList 也实现 RandomAccess, Cloneable, java.io.Serializable 等接口,分别代表其具有随机访问;允许生成此类的副本;可序列化的能力。

ArrayList 继承自 AbstractList ,这个抽象类提供了迭代器的实现。

概述

Resizable-array implementation of the <tt>List</tt> interface. Implements all optional list operations, and permits all elements, including <tt>null</tt>. In addition to implementing the <tt>List</tt> interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to <tt>Vector</tt>, except that it is unsynchronized.)

就像是源码中说的一样

ArrayList是实现了 List 接口的可调整大小的数组(Resizable-array)

实现了所有可选列表操作,并且允许所有元素,包括 null

除了实现 List 接口外,ArrayList 还提供了操作数组大小的方法被用于内部存储列表。

最后一句很关键:

这个类大致相当于 Vector ,只是线程不安全(unsynchronized)

<p>The <tt>size</tt>,<tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant time. The <tt>add</tt> operation runs in <i>amortized constant time</i>, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the <tt>LinkedList</tt> implementation.

size,isEmpty,get,set,iterator 和 listIterator等方法时间复杂度均为 常数

使用 add 方法添加 n 个元素的时间复杂度是 O(n)

粗略地说,其他所有操作均可在线性时间内完成。

<p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

每个 ArrayList 都有容量(capacity)。

容量(capacity)即为 ArrayList 底层的数组存储大小。

当有元素被添加到列表中时,容量(capacity)会自动增长。

<p>An application can increase the capacity of an <tt>ArrayList</tt> instance before adding a large number of elements using the <tt>ensureCapacity</tt> operation. This may reduce the amount of incremental reallocation.

在添加大量元素之前,使用 ensuacity 方法,这可能会减少增量重新分配的数量。

<p><strong>Note that this implementation is not synchronized.</strong> If multiple threads access an <tt>ArrayList</tt> instance concurrently, and at least one of the threads modifies the list structurally, it <i>must</i> be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list.

前面提到过 ArrayList 是不同步的(unsynchronized)。

如果多个线程同访问 ArrayList 实例,并且至少一个线程修改的其结构,那么它必须在外部进行同步(synchronized)。

这里的 结构修改(structural modification) 指的是 添加(add) 或 删除(remove) 一个或多个元素,或显式调整数组。

注意:修改元素的值不算结构修改

If no such object exists, the list should be "wrapped" using the {@link Collections#synchronizedList Collections.synchronizedList} method. This is best done at creation time, to prevent accidental unsynchronized access to the list:<pre> List list = Collections.synchronizedList(new ArrayList(...));</pre>

如果没有任何对象存在于 ArrayList ,则其应该被 "包装" 起来。

最好是在创建 ArrayList 时就这么做:

List list = Collections.synchronizedList(new ArrayList(...));

<p><a name="fail-fast"> The iterators returned by this class's {@link #iterator() iterator} and {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a> if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator will throw a {@link ConcurrentModificationException}. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

这个类和方法返回的迭代器是 快速失败(fail—fast) :

如果 ArrayList 在创建迭代器之后无论何时进行 结构修改(structurally modified) ,除了通过iterator自己的remove()方法删除 或add(Object)方法添加之外,迭代器将会抛出__ConcurrentModificationException__。

因此,在并发修改的情况下,迭代器会快速而干净地失败,而不是在将来某个未确定的时间出现冒险的、任意的、不确定的行为。

Note that the fail-fast behavior of an iterator cannot be guaranteedas it is, >generally speaking, impossible to make any hard guarantees in the presence of >unsynchronized concurrent modification. Fail-fast iterators throw {@code >ConcurrentModificationException} on a best-effort basis. Therefore, it would be >wrong to write a program that depended on this exception for its correctness: ><i>the fail-fast behavior of iterators should be used only to detect bugs.</i>

迭代器的 fail-fast 行为是不能被保证的。一般来说,在不同步的并发修改存在的情况下不可能做出任何硬的保证。

故障快速迭代器在最佳工作基础上抛出{@code ConcurrentModificationException}。因此,编写一个依赖于这个异常的程序是错误的: 迭代器的故障快速行为应该仅用于检测错误。

属性

    /**
     * ArrayList 版本号
     */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 定义初始化容器大小为10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 这是一个共享的空的数组实例.
     * 当使用 ArrayList(0) 或者 ArrayList(Collection<? extends E> c) 
     * 并且 c.size() = 0 的时候将 elementData 数组指向这个实例对象。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 另一个共享的空数组实例,默认使用无参构造方法时 elementData 指向这个对象
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区,ArrayList的容量是这个数组缓冲区的长度。
     * Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * (ArrayList 为空时,指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
     * 
     * 注意:这个方法是非私有的,目的是让简化内部类访问
     */
    transient Object[] elementData; 

    /**
     * ArrayList 的大小
     */
    private int size;

这里还需要介绍一个属性 modCount ,这个属性继承自 List

List 对象有一个成员变量 modCount ,它代表该 List 对象被修改的次数,每对 List 对象修改一次,modCount 都会加 1。

这个属性用于迭代器遍历集合中的元素,因为在使用迭代器遍历集合的时候同时修改集合元素都会使得代码抛出 ConcurrentModificationException,因为 ArrayList 被设计成非同步的。

构造器

可以看到 ArrayList有三个构造器:

    /** 
     * 构造一个具有指定初始容量的空列表
     *
     * @param  列表的初始容量
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * 构造一个初始容量为 10 的空列表
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造一个包含指定集合元素的列表,顺序由集合的迭代器返回。
     *
     * @param 指定集合元素,其元素将被放置到这个列表中。
     * @throws NullPointerException 当指定的集合为 null 时抛出空指针异常
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray 不一定返回 Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                // 返回若不是 Object[] 将调用 Arrays.copyOf 方法将其转为 Object[]
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

自动扩容

ArrayList 的自动扩容机制是 ArrayList 的核心,所以这个数据结构也被称作动态数组。

下面解析其源码:

    /**
     * 如果需要,增加这个 ArrayList 实例的容量。
     * 以确保它至少能容纳最小容量(minCapacity)指定的元素的数量。
     * @param   minCapacity   指定的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // 不是默认元素的任何大小
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    /**
     * 计算 ArrayList 实例的实际容量。
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    // 根据实际容量进行扩容检查
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 扩容检查方法
    private void ensureExplicitCapacity(int minCapacity) {
        // 修改次数+1
        modCount++;

        // 当最小容量大于实际容量时,对数组进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * 数组可分配的最大大小。
     * 因为一些虚拟机会在数组中保存一些头文字(header words)
     * 所以分配更大的数组会导致内存泄漏。
     * 
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 增加容量,以确保它至少能容纳最小容量(minimum capacity)指定的元素个数。
     *
     * @param minCapacity 所需的最小容量
     */
    private void grow(int minCapacity) {
        // 获取 List 的实际容量
        int oldCapacity = elementData.length;
        // oldCapacity >> 1 等价于 oldCapacity / 2  所以新容量为当前容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩容后 List 容量仍小于所需的最小容量,直接将最小容量作为 List 的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果扩容后的 List 容量大于数组可分配的最大大小。    
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 将最小容量和 MAX_ARRAY_SIZE 作比较
            newCapacity = hugeCapacity(minCapacity);
        // 复制数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 如果最小容量超过 MAX_ARRAY_SIZE 的大小
     * 就直接将 Integer.MAX_VALUE 作为 List 的容量。
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();    
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

数组拷贝

接下的文章来将会介绍 ArrayList 中添加元素和删除元素的方法,而这些操作都是通过数组拷贝(arraycopy)来完成的。

如果数据量较大的话,相比 for 循序,这个方法的执行效率很高,因为其使用的是内存复制,省去了大量的数组寻址访问等时间。

    /**
     *
     * @param      src      源数组.
     * @param      srcPos   源数组中的起始下标.
     * @param      dest     目标数组.
     * @param      destPos  目标数组中的起始下标.
     * @param      length   源数组中被拷贝的长度.
     * @exception  IndexOutOfBoundsException  if copying would cause
     *               access of data outside array bounds.
     * @exception  ArrayStoreException  if an element in the <code>src</code>
     *               array could not be stored into the <code>dest</code> array
     *               because of a type mismatch.
     * @exception  NullPointerException if either <code>src</code> or
     *               <code>dest</code> is <code>null</code>.
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

添加元素

ArrayList 添加元素的方法。

    /**
     * 将指定的元素追加到列表的末尾。
     *
     * @param e 需要添加的元素
     * @return  true
     */
    public boolean add(E e) {
        // 添加元素前扩容检查
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将元素插入列表尾部
        elementData[size++] = e;
        return true;
    }

    /**
     * 将指定的元素插入该列表中的指定位置。将当前位置的元素(如果有)和任何后续元素移到右边
     * (将一个元素添加到它们的索引中)。
     *
     * @param index   插入位置的下标
     * @param element 需要插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        // 当指定插入位置的下标大于 List 的大小时,抛出 IndexOutOfBoundsException
        rangeCheckForAdd(index);

        // 扩容检查
        ensureCapacityInternal(size + 1); 

        // 对数组进行复制处理,
        // 目的就是空出index的位置插入 element,并将 index 后的元素位移一个位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);

        // 将下标为 index 位置赋值为 element                 
        elementData[index] = element;

        // List 容量 +1
        size++;
    }

删除元素

ArrayList 删除元素的方法。

    /**
     * 在这个列表中删除指定位置的元素。
     * 将任何后续元素移到左边(从它们的索引中减去一个)。
     *
     * @param  index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        // 对 index 的合法性做检查
        rangeCheck(index);
        // 修改次数+1
        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;
    }

    /**
     * 如果它存在的话,从这个列表中删除第一次出现的指定元素。
     * 如果列表中不包含元素,那么它是不变的。
     *
     * @param o 需要删除的元素
     * @return  如果这个元素存在于列表中则返回 true
     */
    public boolean remove(Object o) {
        // 如果需要删除的元素为 null
        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);
        // 提醒GC可以回收这个对象了
        elementData[--size] = null;
    }