浅学——ArrayList机制

本文章使用的jdk源码版本为1.8

ArrayList的几个关键字段：
elementData是ArrayLlist底层存放元素的数组；
length是elementData的数组大小；
size是elementData中有实际元素的数量；
modCount是容器的修改次数；

容器初始化

一般我们初始化ArrayList是这样子的~

List<Integer> list = new ArrayList();

阅读过一些博客的小伙伴都知道ArrayList的初始容量是10.

    /**
     * Default initial capacity.
     * 默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;    //嗯~初始化容量的确是10呢~

    /**
     * Constructs an empty list with an initial capacity of ten.
     * 初始化一个容量为10的数组
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    //等等?DEFAULTCAPACITY_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 = {};

可以看到，ArrayList默认初始化后是一个空数组，实际上当ArrayList第一次调用add()函数后，容量才会扩容到10.

扩容机制

ArrayList扩容的触发条件是 往list中添加一个元素后的size > elementData.length，进行扩容

ArrayList的扩容的大致过程：list调用add()后，如果list的实际容量（size）是否大于list的长度（length），就扩容1.5倍。ArrayList的最大容量是 Integer.MAX_VALUE。

@Native public static final int   MAX_VALUE = 0x7fffffff;

具体过程看代码：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!! 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;
        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. 调用add()后，调用了扩容方法，再进行添加元素。
2. ensureCapacityInternal()主要判定了elementData是否为初始化后的空数组，然后比较ArrayList的默认数组大小和newSize，继续往下调用。
3. ensureExplicitCapacity()中，modCount++是判定修改数据结构的次数。如果newSize大于现有数组大小，进行grow扩容。
4. 对list进行扩容，newCapacity = oldCapacity + (oldCapacity >> 1)即新容量为原来的1.5倍。如果数组容量大于ArrayList最大容量，无法再进行扩容。

迭代器（Iterator）

为什么要使用迭代器？

Iterator主要的作用是为容器提供一个遍历元素的方式并且屏蔽容器的底层实现。如果没有迭代器，遍历ArrayList就需要访问其底层数组，遍历LinkedList就需要访问它的节点，暴露内部细节。Iterator屏蔽了底层细节：

    List list = new ArrayList();
    //List list = new LinkedList();
    //添加元素
    Iterator<Object> it = list.iterator();

看看Iterator接口有什么方法：

    public interface Iterator<E> {
        boolean hasNext();
        E next();
        void remove();
        default void forEachRemaining(Consumer<? super E> action);
    }

iterator的使用

List<Object> list = new ArrayList<>();
Iterator<Object> it = list.iterator<Object>();
while(it.hasNext()) {
    Object ele = it.next();
    //doSomething
}

迭代器移动

iterator的注意事项

• iterator是被看做在两个元素之间的，调用next方法越过下一个元素并返回该元素的引用。
• next方法和remove方法互相依赖，未调用next方法就调用remove方法会抛出错误，代码在下面：Itr有一个lastRet变量，每次调用next方法就会给lastRet赋值，调用remove方法会置为-1，当lastRet为-1时调用remove方法就会抛出错误IllegalStateException.所以调用next方法后连续调用两次remove方法，第一次会置为-1，第二次会报错。
  iterator在ArrayList中的实现

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

线程安全

未完成