Java中ArrayList实现原理

简述：

• ArrayList可以理解为动态数组，与Java中的数组相比，它的容量能动态增长。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组中，因此最好能给出数组大小的预估值；
• 容量大小也可以在程序中通过ensureCapacity(int minCapacity)方法来调整；
• 默认第一次插入元素时创建大小为10的数组（注意，是在插入元素时，而不是new ArrayList时）；
• ArrayList继承了AbstractList，实现了List；实现了RandomAccess接口，即提供了随机访问功能；实现了Cloneable接口，覆盖了clone()方法，能被克隆；实现了Serializable接口，支持序列化；

数据结构：

　　使用Object数组实现

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

构造方法：

　　提供了三种方式的构造器：

1. public ArrayList() 可以构造一个空列表；
2. public ArrayList(int initialCapacity) 构造一个指定初始容量的空列表；
3. public ArrayList(Collection<? extends E> c) 构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列；

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

存储：

　　1.set(int index, E element)

　　该方法首先通过rangeCheck(index)来校验index变量是否超出数组范围，超出则抛出异常。然后取出原index位置的值作为oldValue，并将新的element放入index位置，最后返回oldValue。

　　public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

　　2.add(E e)

　　该方法是将指定的元素添加到列表的尾部。首先判断list是否需要扩容，然后再将元素添加到数组中。

　　public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    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);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 扩展为原来size的1.5倍大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩为1.5倍大小仍不能满足需求，则直接扩为需求值（minCapacity）
        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.public E remove(int index)

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

　　2.public boolean remove(Object o)

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

读取：

　　1.get(int index)

　　该方法会判断输入的index是否越界，然后将数组的index位置的元素返回即可。

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

扩容：

　　扩容代码上边提到过，不再赘述。

　　数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长是原容量的1.5倍。

　　这种操作的代价还是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。

　　如果我们可预知要保存的元素是多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。

　　或者根据实际需求，在程序中通过调用ensureCapacity(int minCapacity)方法来手动调整ArrayList实例的容量，如想调整容量的增长策略，可继承ArrayList，并覆盖ensureCapacity方法。