Java源代码阅读——ArrayList实现原理

一  概述

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

可见它实现List接口，其底层使用数组保存所有元素，其操作基本上是对数组的操作。

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

二 具体实现

2.1 原始数组

PRivate transient Object[] elementData;transient关键字表示变量不会被序列化。为何使用该关键字？
由于在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去,所以需要手在调用writeObject()时手动序列化数组对象。
2.2 构造方法
public ArrayList(int initialCapacity) {        super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        this.elementData = new Object[initialCapacity];    }    public ArrayList() {        this(10);    }    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);    }总共3个构造方法，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。
2.3 trimToSize()
调用copyOf返回有效长度的ArrayList();
public static int[] copyOf(int[] original, int newLength) {        int[] copy = new int[newLength];        System.arraycopy(original, 0, copy, 0,                         Math.min(original.length, newLength));        return copy;    }使用一个临时数组暂存，再返回该临时数组。copyOf后得到的数组与原数组存储地址不同。修改后相互不影响。
2.4  ensureCapacity()
调用grow();
2.5 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);    }每次增长为原来的1.5倍，调用Arrays.copyOf()完成。
2.6  indexOf()
调用equals()方法。
2.7 clone()和toArray()
public Object clone() {        try {            @SuppressWarnings("unchecked")                ArrayList<E> v = (ArrayList<E>) super.clone();            v.elementData = Arrays.copyOf(elementData, size);            v.modCount = 0;            return v;        } catch (CloneNotSupportedException e) {            // this shouldn't happen, since we are Cloneable            throw new InternalError();        }    }
public Object[] toArray() {        return Arrays.copyOf(elementData, size);    }调用Arrays.copyOf();