Java容器深入研究(jdk 1.8)--- ArrayList总结与源码分析_java 容器 扩容

结构： public class ArrayList<E> extends AbstractList<E>  

implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

继承自 AbstractList<E> ，这是一个抽象类对一些基础的list操作做了一些封装，实现了RandomAccess 标记接口，表明可以实现快速随机访问，Cloneable接口的实现表示该容器具有Clone函数操作，Serializable是序列化。

内部存储结构：  

transient Object[] elementData; //transient关键字修饰的一个Object数组，为什么会用到transient后面再解释；
private int 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);
        }
    }
    //构造一个默认的空ArrayList，这里并没有初始化，jdk 1.8之后是在进行add操作后初始化
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //构造一个具有指定元素的ArrayList    
    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;
        }
    }

增加操作：

    /**
     * 在数组末尾加上一个元素
     */
    public boolean add(E e) {
    	
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
 
    /**
     * 在某个位置加入一个元素element
     * @param index
     * @param element
     */
    public void add(int index, E element) {
    	//检查index是否越界
        rangeCheckForAdd(index);
        //进行扩容检查
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //对数据进行复制操作，空出index位置，并插入element，后移index后面的元素
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

扩容检查：

/**
     * 这个扩容方法，内部没有调用，判断ArrayList是否为空
     * @param minCapacity
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0
            : DEFAULT_CAPACITY;
 
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    /**
     * 扩容检查
     * @param minCapacity
     */
    private void ensureCapacityInternal(int minCapacity) {
    	//第一次add操作初始化，如果为空ArrayList，那么初始化容量为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //判断是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }
    /**
     * 判断是否需要扩容
     * @param minCapacity
     */
    private void ensureExplicitCapacity(int minCapacity) {
    	//modCount这个参数运用到了 fail-fast 机制，后面解释
        modCount++;
        //扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
    //最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
    /**
     * 将整个数组size扩容为1.5倍
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //newCapacity为以前的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断容量是否到达long int 最大临界值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 对数组进行复制处理
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //检查是否超过最大容量 0x7fffffff ，是否抛出异常
    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倍

删除元素：

    /**
     * 根据索引删除元素
     * @param index
     * @return
     */
    public E remove(int index) {
    	//数组越界检查
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        //计算数组需要复制的数量
        int numMoved = size - index - 1;
        //将index后的数据都向前移一位
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //let GC
        elementData[--size] = null;
        return oldValue;
    }
 
    /**
     * 根据元素内容匹配并删除，只删除第一个匹配成功的
     * @param o
     * @return
     */
    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 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
    }

数组节约内存空间，缩小容量的方法 :   trimToSize

 /**
     * 数组缩小容量，增加元素会进行扩容，但删除元素没有缩容，
     * 这个方法是用来提供缩小数组容量
     */
    public void trimToSize() {
        modCount++;
        //length是数组长度，size表示数组内元素个数
        //size<length那么就说明数组内有空元素，进行缩小容量操作
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

现在ArrayList的增加和删除，及扩容操作都明白了吧。为什么ArrayList 不适合频繁插入和删除操作？就是因为在ArrayList中我们一直会调用 System.arraycopy 这个效率很低的操作来复制数组，所以导致ArrayList在插入和删除操作中效率不高。

在ArrayList中，还提供了 Iterator 和 ListIterator 这两种迭代器，他们有什么区别呢？

ListIterator 与普通的 Iterator相比，它增加了增、删、设定元素、向前向后遍历的操作。

在结构上面 ：public interface ListIterator<E> extends Iterator<E> ，我们看看他们的结构图就会一目了然了。

                        

关于ModCount ：

我们先说说 容器的“快速失败”机制，它是Java集合中的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。它是一种迭代器检测bug的机制，比如：我们有线程A和线程B，线程A通过Iterator访问集合中的元素，某个时刻，线程B修改了集合中的结构，那么程序就会抛出 ConcurrentModificationException 。

这个fail-fast机制是怎么实现的呢？

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

没错，在迭代器中的 add 、remove 、 next等方法中都调用了此方法，判断 modCount 和 expectedModCount是否相等，来决定是否抛出异常。

在迭代器中，int expectedModCount = modCount; 中定义了 expectedModCount ， 这个值是不会变化的，所以使用迭代器遍历整个ArrayList时，我们只需要判断是否进行了那些会让 ModCount 改变的方法，从而知道了集合是否发生了结构上的变化。注明：在LruCahe当中，因为它的底层是一个 HashLinkedMap 实现，使用了最近最少使用算法，所以迭代器在使用 get 方法的时候，也会抛出这个异常，所以谨慎使用。

还有一个问题，为什么底层数组会有 transient 关键字修饰？貌似 HashMap底层也是这个关键字修饰的 ：transient Node<K,V>[] table ?

我会单独写一篇博客来解释，transient关键字的作用，还有关于 Iterator迭代器模式。

有什么不好的地方还望指正~~~