ArrayList源码解析

相信写 Java 代码不久就会接触到ArrayList,这是个容器类，我们在使用的时候觉得这个容器好像是无限大的一样，我们可以不断的操作它(add、get、remove)，其实它的内部实现是基于数组的，这篇文章就是介绍其内部原理。了解原理后，我们在使用的时候可以根据实际情况来配置它，让它拥有更好的性能和更少的内存占用。

ArrayList类主要字段

private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    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.
     */
    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
     */
    private int size;
    
    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码

从这个字段结构，我们得到以下信息：

• ArrayList内部主要是使用Object[] elementData来存储我们添加的数据。
• size字段记录当前List已经存储的数据的个数。
• DEFAULT_CAPACITY字段标记默认初始化ArrayList时分配的数组的长度。
• EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是定义的两个空数组，为什么要使用两个呢？下面我们会分析原因。

ArrayList相关方法解析

下面我们通过我们使用ArrayList时常用的方法来慢慢分析它的源码。

构造函数

/**
     * 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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_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();
        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;
        }
    }
复制代码

ArrayList构造函数一共有3个：

• 我们最常用的new ArrayList()其实只是把elementData指向了默认空数组而已(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)。
• initialCapacity容量的构造函数源码也很简单，如果initialCapacity>0就创建一个initialCapacity容量的数组，如果initialCapacity==0，elementData只是指向EMPTY_ELEMENTDATA。
• 最后的构造函数是使用Collection集合来初始化ArrayList。先将Collection集合转化成数组，然后根据size来执行不同的操作。如果转化后的数组不是Object类型的，就重新创建一个size大小的数组。
  下面我们就从常用的方法来一步步解读ArrayList的源码。

add方法

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

    /**
     * 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++;
    }
复制代码

从上面我们看到，add(E e)方法直接将元素添加到数组末尾。而add(int index,E element)方法将元素添加到指定的index位置，当然原先index后面的元素需要调整位置(都往后挪一个位置)。

我们从上面的源码中看到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);
    }

    /**
     * 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：

我们先看ensureCapacityInternal方法。第一步：如果elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么就扩容数组到DEFAULT_CAPACITY(10)。通过这一步我们知道只有我们new ArrayList()的时，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA条件才会成立。第二步：我们根据流程ensureCapacityInternal-->ensureExplicitCapacity-->grow，我们知道这种情况下ArrayList会创建一个长度为10的数组。 情况2：

上面分析ArrayList构造器时，elementData也会指向EMPTY_ELEMENTDATA空数组。只有new ArrayList(0)或者new ArrayList(空集合)才会成立。这种情况下，我们根据ensureCapacityInternal-->ensureExplicitCapacity-->grow流程来看，这时候分配的数组很小(占用内存小),这是保守的内存分配策略。 总结：

通过上面的分析，我们知道了DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA两个空数组的不同用途。前者默认创建10个元素的数组，然后在这个基础上进行扩容。后者是比较保守的内存分配策略，数据扩容比较缓慢。

grow方法解析

grow方法是整个ArrayList扩容的核心，下面我们来看下其源码：

/**
     * 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;
    }
复制代码

我们看到ArrayList默认扩容大小是原大小的1.5倍。下面逻辑依次是判断一些边界的情况：

• 如果newCapacity小于minCapacity，那么就将数组大小调整为minCapacity大小。
• 如果minCapacity的值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间，那么新数组分配Integer.MAX_VALUE大小，否则分配MAX_ARRAY_SIZE。

contains,indexOf,lastIndexOf相关检索方法

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

    /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest 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 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;
    }
复制代码

这些方法逻辑都比较清晰，就是循环遍历，找出符合条件的元素而已。

toArray方法

这个方法有时我们需要用到，它是将ArrayList转化成数组。下面我们来看其源码：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:'
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}
复制代码

通过Arrays.copyOf和System.arraycopy方法，ArrayList将elementData数组中的数据拷贝到新数组，然后返回。System.arraycopy方法效率很高，其内部使用C/C++(设置会使用汇编)，我们平时开发的时候，有数组拷贝，也应该使用这些方法。

get/set方法

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[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);
}

/**
 * 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;
}
复制代码

逻辑比较简单，不做详细介绍。

remove方法

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

    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    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 remove method that skips bounds checking and does not
     * return the value removed.
     */
    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
    }
复制代码

逻辑还是比较清晰的，只是remove(index)/或者remove(object)后，需要调用System.arraycopy来高效的移动index后面的数组，让其可以填充位置。

removeAll/retainAll方法

有的朋友可能没有用过这两个方法，下面我们通过一个小栗子来看一下这两个方法到底是什么，请看代码：

ArrayList<String> list=new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
list.add("F");

ArrayList<String> list1=new ArrayList<>();
list1.add("C");
list1.add("D");

//list.removeAll(list1);
//[A, B, E, F]
System.out.println(list);

list.retainAll(list1);
//[C，D]
System.out.println(list);
复制代码

从结果我们可以看出，removeAll方法是计算两个集合的差集，retainAll计算两个集合的交集。下面我们通过源码来分析：

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}
复制代码

我们看到，这边设计比较精妙，通过一个boolean值，将取差值和取交集的方法整合为一个方法。batchRemove方法的代码设计实现还是很不错的，核心的逻辑就是try语句块里面的for循环，finally语句块里面主要是数据拷贝及特殊值的处理。

迭代器

Java集合在设计的时候就是支持迭代器的。下面我们来看看ArrayList里面迭代器的相关部分。

获取迭代器对象

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}
复制代码

我们看到默认返回的是一个Itr对象，熟悉Java集合层次结构(类继承结构)的朋友，可能知道ArrayList的基类AbstractList里面就有一个内部类Itr。现在ArrayList内部重新实现了一个优化版本的Itr类，我们来看源码：

/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

从上面的源代码中，迭代器只提供基本的向后遍历、删除等功能。这样我们在遍历ArrayList的时候，还可以使用迭代器来进行遍历(当然for(E e : elements)这种写法会被编译期自动转化成迭代器的调用)。

ListItr迭代器

继续往下研究ArrayList的源代码，我们会发现ArrayList内部还实现了ListItr的迭代器。这个迭代器除了提供向后遍历功能外，还提供了向前遍历，增加、设置等功能。是一个功能比较全的迭代器实现。我们看下源码：

/**
     * An optimized version of AbstractList.ListItr
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
复制代码

我们看到ListItr这个迭代器里面很多操作都是直接调用的ArrayList类的方法，它只是做了一层封装。

ConcurrentModificationException异常出现的原因及解决方法

有的朋友在遍历ArrayList集合的时候可能遇到过这个异常，这个异常时ArrayList类设计的快速失败机制导致的，这个异常认为集合在遍历的时候，做出了修改。我下面这个例子就出现了这个异常，一起来看下：

ArrayList<String> list=new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
list.add("F");

for(String item : list) {
	System.out.println(item);
	list.remove(item);
}
//或者
/*
Iterator<String> iterator=list.iterator();
while (iterator.hasNext()) {
	String string = (String) iterator.next();
	System.out.println(string);
	list.remove(string);
}
*/

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
	at java.util.ArrayList$Itr.next(Unknown Source)
	at com.learn.example.RunMain.main(RunMain.java:42)
复制代码

下面两种遍历方式都会导致异常的发生，下面我们来看下原因。上面介绍过第一种foreach循环写法编译后就是迭代器。我们直接看迭代器。

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

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

我们看到next()方法第一行会调用checkForComodification()方法，我们看到如果modCount和expectedModCount不相等的话，就会抛出这个异常。我们上面再看Itr源码的时候看到expectedModCount刚开始赋值的是ArrayList类里面的modCount变量。下面list.remove(o)这个方法里面会让modCount++。源码如下：

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
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
}
复制代码

这样的话就会导致Itr内部的expectedModCount和ArrayList的modCount不一致，从而抛出这个异常。那么我们如何解决呢？只需要让modCount不增加，让它的值与expectedModCount同步即可。Itr内部也有remove方法，我们调用这个方法即可。

Iterator<String> iterator=list.iterator();
while (iterator.hasNext()) {
	String string = (String) iterator.next();
	System.out.println(string);
	iterator.remove();
}
复制代码

总结

• ArrayList内部是Object[]数组，然后使用的时候进行动态扩容。
• ArrayList默认会分配10个元素的数组，然后在此基础上进行扩容，每次新的扩容后的数组长度是原数组长度的1.5倍。如果你大概知道集合的容量，可以指定初始化值，减少扩容带来性能损耗。
• ArrayList适合查询多，操作少的场景(因为操作过后，绝大部分情况下需要挪动数组位置)。
• ArrayList集合不是线程安全的，在多线程环境下需要加锁或者使用并发安全的容器。