Java源码分析之ArrayList

@author StormMa

@date 2017-06-01

生命不息，奋斗不止！

基于jdk1.8的ArrayList源码分析。

实现List接口最常见的大概就四种，ArrayList, LinkedList, Vector, Stack实现，今天就着重看一下ArrayList的源码实现。ArrayList的底层结构就是最简单的数组,数据结构导致了它查询快，但是增删慢。另外官方也说了，ArrayList是线程不同步的。我觉得我有必贴一下官方文档的描述。

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null . In addition to implementing the List 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 Vector , except that it is unsynchronized.)

开始阅读

声明

/**
     * Default initial capacity.//初始化容量=10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.//空数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     * 也是空数组，但是第一次add的时候会自动调整容量为DEFAULT_CAPACITY
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     * 数组声明，不参与序列化。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     * 包含元素的个数，不一定等于elementData.length。。
     */
    private int size;

看完了类的属性声明，我们趁热打铁接着就去看一下构造方法！一探初始化ArrayList的究竟。

构造方法

空参数构造方法

默认的构造方法创建的elementData中的长度是1, size=0第一次add的时候会自动调整elementData.length=10。补充一点，我们要知道elementData.length != size。

/**
     * Constructs an empty list with an initial capacity of ten
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

初始化指定容量的构造函数

这个构造函数没什么说的，判断传入的参数如果>0就初始化指定参数的数组，如果等于0，就是一个空数组咯，<0，对不起，抛出异常!

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @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);
        }
    }

创建包含指定Collection的构造函数

这个构造函数也没什么好说的，开始吧Collection转换成数组并且elementData引用数组地址(浅拷贝)，然后判断数组的长度(并修改size的值)，如果不为0就深拷贝数组的内容到elementData中去，如果size还等于0的话，就创建一个空数组就行了。

/**
     * 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
     * 创建一个包含指定Collection的数组
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        //如果传入的Collection不为空
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)， c.toArray()错误时候不返回Object[]
            if (elementData.getClass() != Object[].class)
            //拷贝
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {//如果为空创建一个空数组
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add*()

add(E e)

大致思路

1. 确保在成功添加元素之后，数组的size不超过阈值。
2. 添加元素
3. 返回成功标志

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

我们继续看一下ensureCapacityInternal的实现

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_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);
    }

我想我应该补充一下add()方法思路的描述的第一条。确保成功添加元素之后的size不超过阈值。首先在ensureCapacityInternal方法中先判断elementData的类型，如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA(这个就和我们上面所述的DEFAULTCAPACITY_EMPTY_ELEMENTDATA初始化elementData.length=1, size=0, 第一次add会自动扩容成10，添加成功size变成1)。那么此时取DEFAULT_CAPACITY(10)和当前假设添加元素成功之后的size(其实就是未添加之前的size+1)的最大值。然后进行ensureExplicitCapacity的判断。在ensureExplicitCapacity中，先自增修改次数标识(我们无需关注这个属性)。然后开始判断if， if的主体翻译过来就是: 数组已使用的数组长度+1大于当前数组长度(也就是比较size+1和element.length的大小，我们之前不是说过size != element.length吗？size+1和element.length的比较说明了什么呢？其实很简单，因为size代表的始终是已添加的元素的个数，而element.length就是数组的最大长度，如果添加成功的元素的个数(size+1) > 数组最大长度(element.length)了，那岂不jj了，所以此时要扩容了，那调用grow方法吧)，我们接着看一下grow方法。

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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;
    }

代码中，我们很容易看出扩容是按照1.5被的oldCapacity进行扩容的，如果1.5oldCapacity 还小于我们需要的最小的minCapacity(也就是size+1)，那直接按照minCapacity进行扩容算了。如果newCapacity大于数组允许的最大值(Integer.MAX_VALUE-8)了，那就试着缩小一下扩容的范围。判断内存是否溢出，不然返回最大整型值，继续扩容。如果这一切没问题，那就进行数组的深拷贝，此时完成扩容并拷贝了数据。

add(int index, E element)

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    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++;
    }

    /**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

这个方法，和add(E e)没什么差别，唯一多了的就是越界检查。没什么好分析的。

addAll(Collection

/**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    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;
    }

因为我们之前详细分析了add(E e)这个方法，然后看addAll这个方法就很简单(其实本来也不难哈(玩笑脸))。要添加的Collection的长度加上size判断容量，然后进行深拷贝，修改size，返回添加的结果，完了，就这么简单！另外还有一个addAll(int index, Collection

get()

E get(int index)

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

没啥好说的吧。

if index 越界: 
    throw exception
else: 
    return elementData[index]

set

E set(int index, E element)

/**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);

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

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

contains()

contains(Object o)

/**
     * Returns <tt>true</tt> if this list contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this list contains
     * at least one element <tt>e</tt> such that
     * <tt>(o==null ? e==null : o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return <tt>true</tt> if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    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;
    }

这个也不作分析了，很简单的代码。

remove()

E remove(int index)

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @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) {
        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;
    }

删除我就稍作一下分析吧，因为我们都知道数组的特点就是查询快，增删慢的数据结构。 remove先检查index，然后计算要移动的元素的个数，然后调用System.arraycopy方法

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

clear()

clear()

/**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

结束

本文来自我的个人博客: http://blog.stormma.me ，转载请注明出处！