集合源码学习之路---ArrayList

摘要：虽然迭代器不常用，但是里面的一些知识点，设计模式我们还是要学习以下的。需要注意的是，在使用迭代器期间，若使用非迭代器对容器进行数据结构上的改变，将会通过报错。

ArrayList底层数据结构使用的是数组，也就是线性表的顺序存储结构，是一段连续的存储单元。具有存取快，增删慢的特点。ArrayList不是线程安全的

从类定义上看，arrayList是支持泛型的,继承自AbstractList,实现了List接口。同时实现了Serializable接口，因为它支持序列化，支持序列化传输。实现了Cloneable接口，可以被克隆。实现了RandomAccess接口，可以被快速访问，实际上就是通过下标进行访问,RandomAccess只是一个标记，无任何定义。

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

private static final long serialVersionUID = 8683452581122892189L;

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

serialVersionUID：是实现了Serializable可自动生成的。简单来说，Java的序列化机制是通过在运行时判断类的serialVersionUID来验证版本一致性的。在进行反序列化时，JVM会把传来的字节流中的serialVersionUID与本地相应实体（类）的serialVersionUID进行比较，如果相同就认为是一致的，可以进行反序列化，否则就会出现序列化版本不一致的异常。

EMPTY_ELEMENTDATA & DEFAULTCAPACITY_EMPTY_ELEMENTDATA :其实两个都是一个空数组，只不过再明确长度为0时，会用EMPTY_ELEMENTDATA，无参构造调用会用DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

DEFAULT_CAPACITY:当没有指定容量，第一次添加元素,arraylist的初始容量.

elementData:arraylist的buffer，arrayList的容量就是elementData的容量。当arraylist为空时，elementData就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候，会自动扩容DEFAULT_CAPACITY(10)长度.注意到，它被transient修饰，也就是不参与序列化，只存在调用者的内存当中。

size:arraylist含有元素的个数。

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

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(Collection 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一共定义了三个构造函数。

构造一个指定大小的elementData

初始化一个默认数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA

将一个集合Collection初始化为arrayList

/**
trim就是去除两段空格的意思，这个方法是用来给elementdata瘦身用，将占据的多余的空间给释放掉
*/
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

/**
确保容器容量，若为空,minCapacity去当前值和默认容量的最大值，然后判断是否进行扩容
*/
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

/**
minCapacity大于数组长度，则调用grow函数进行扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
        /**
        modCount:是父类AbstractList的变量。集合中所有用到modCount的都是线程不安全的。在做对线性表结构修改的操作会对modCount进行+1，当我们调用iterator，会检测modCount是不是我们期望的，如果在调用期间modCount又发生了变化，iterator将抛出异常.
        */
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

/**
获取到数组长度，对其进行扩容，增加将近一半的容量，使用Arrays.copyOF进行扩容
*/
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);
    }

//返回容器元素个数
public int size() {
        return size;
    }

//判断是否为空
public boolean isEmpty() {
        return size == 0;
    }

/**
两个方法都是判断索引正否越界
*/
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

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

/**
* 此方法用户往线性表最后一位插入元素，若容器容量足够，则时间复杂度是O（1），若需要扩容，则时间复杂度是O（n）
*/
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
/**
* 此方法用于向指定位置插入元素，时间复杂度为O(n)
*    1.判断角标是否越界  2.保证数组容量足够，不够通过新建数组扩容 3.从数组指定索引复制直到最后一位，全*部加一
*/
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++;
    }

//删除制定索引元素，需算出位移量，将index之后的其他元素提前一位，其复杂度为o(n)
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;
    }
    //遍及elementData，若值相同，则调用fastRemove移除
    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;
    }
    //此方法和remove大致相同，只是少了判断索引越界的问题，因为在被调用前已经通过遍历方式验证了
    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
    }

什么是迭代器呢？其实就是用来遍历容器内部分或全部元素的对象，每个迭代器代表容器中确定的地址，我们把具有类似行为的都叫迭代器。虽然迭代器不常用，但是里面的一些知识点，设计模式我们还是要学习以下的。arraylist迭代器分为Iterator和ListIterator。Iterator接口只定义了遍历和删除的职责，ListIterator继承于Iterator,新增了add和set方法，方便我们在迭代的时候增加删除元素。需要注意的是，在使用迭代器期间，若使用非迭代器对容器进行数据结构上的改变，将会通过checkForComodification()报错。

ListIterator的实现如下:

private class ListItr extends Itr implements ListIterator {
        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();
            }
        }
    }

arraylist源码方法实在是过多，无法一一向大家解释，不过相信大家理解上面的，再去研究剩下的内容应该没有多大问题。通过学习源码，我们可以更清楚的知道arraylist在操作时，底层结构发生了哪些变化，为什么arraylist适合存取，不适合增删.