Java集合之List---ArrayList解析

Java集合之List---ArrayList篇

本章节主要讲述ArrayList集合知识，主要包括ArrayList结构类型，集合特点，源码解析等。

 

欢迎持续关注阅读，一起学习，共同交流(477819525君羊)。

 

 

 

1)   ArrayList类层次结构：

 

 

 

 

2) ArrayList特性：

a) ArrayList是基于数组实现的，是一个动态数组，可以动态的增加和减少元素，灵活的设置数组大小。

b) ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

注：concurrent并发工具包相关类，会在之后文章中做具体讲解，本文不做赘述，如需了解请查阅相关文章。

c) 每个ArrayList实例都有一个容量(初始容量默认为10)。随着向ArrayList中不断添加元素，其容量也自动增长。

   注:此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

d)对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

e)注意扩充容量的方法ensureCapacityInternal。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的右移一位+旧容量，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。

f)  ArrayList是稳定，无序的。稳定性(Order)指集合每次遍历的元素次序是一定的。有序性(Sort)是指遍历的结果按某种比较规则依次排序的。

 

 

3) ArrayList源码分析(不同jdk版本源码结构有所不同，本文参考jdk7)：

a)ArrayList类

ArrayList类实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口(接口没有定义任何内容)，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

b)  私有属性：

   ArrayList只定义两个私有属性：elementData存储ArrayList内的元素，size表示它包含的元素的数量。

    private transient Object[] elementData;

 

    /**

     * The size of the ArrayList (the number of elements it contains).

     *

     * @serial

     */

    private int size;

有个关键字需要解释：transient。 

 Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。（比如，保存用户对象信息，用户包括name,age,sex属性信息，如果不想保存age到数据库，可以对age加上关键字transient,被标记为transient的属性在对象被序列化的时候不会被保存）。

c)  构造方法：

   ArrayList提供了三种方式的构造器，第一个构造方法使用initialCapacity初始化elementData数组的大小，第二个构造方法，可以构造一个默认初始容量为10的空列表，第三个构造方法则将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]）。

    public ArrayList(int initialCapacity) {

        super();

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        this.elementData = new Object[initialCapacity];

    }

 

    /**

     * Constructs an empty list with an initial capacity of ten.

     */

    public ArrayList() {

        super();

        this.elementData = EMPTY_ELEMENTDATA;

    }

 

    /**

     * Constructs a list containing the elements of the specified

     * collection, in the order they are returned by the collection's

     * iterator.

     *

     * @param c the collection whose elements are to be placed into this list

     * @throws NullPointerException if the specified collection is null

     */

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

    }

d) 重点看一下add（E e）方法:

    public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

    }

   可以看到，add方法，先调用一个确保(调整)内部容量的方法，之后将元素赋给elementData数组，然后size自增，将元素赋给elementData[size]不是会出现下标越界吗，关键就在ensureCapacityInternal(size + 1)中。

    private void ensureCapacityInternal(int minCapacity) {

        if (elementData == EMPTY_ELEMENTDATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

        }

 

        ensureExplicitCapacity(minCapacity);

    }

 

    private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

 

        // overflow-conscious code

        if (minCapacity - elementData.length > 0)

            grow(minCapacity);

    }

在ensureCapacityInternal方法中判断elementData数组是否为空数组，如果为空，根据Max.max()得到初始容量和当前size两者之间的最大值。

在ensureExplicitCapacity方法对modCount自增，modCount是记录list结构被改变的次数（每次调用ensureExplicitCapacity方法，modCount的值都将增加，但未必数组结构会改变，所以感觉对modCount的解释不是很到位）。如果添加新元素后，当前size+1大于数组容量，就执行grow方法。

 

    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;

    }

 

在grow方法中，具体完成扩容实现和数组的copy，可以看出容量扩充的方式是数组容量+数组容量右移一位，基本上等于扩容为原来的1.5倍。数组容量的极限是Integer.MAX_VALUE。

 

数组拷贝通过Arrays.copyof()和System.arraycopy()方法完成。

首先来看Arrays.copyof()方法。它有很多个重载的方法，但实现思路都是一样的，我们来看泛型版本的源码：

    public static <T> T[] copyOf(T[] original, int newLength) {

        return (T[]) copyOf(original, newLength, original.getClass());

    }

很明显调用了另一个copyof方法，该方法有三个参数，最后一个参数指明要转换的数据的类型，实现如下：

 

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {

        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的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中。

下面来看System.arraycopy()方法。

    public static native void arraycopy(Object src,  int  srcPos,

                                        Object dest, int destPos,

                                        int length);

该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。