ArrayList源码分析（JDK1.8）

1. ArrayList的成员变量分析。

    private static final Object[] EMPTY_ELEMENTDATA = {}; 

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  //空构造器时，默认为容量为0的空数组

    transient Object[] elementData;//集合实际 存放数据的数组，不需要序列化，故用transient来修饰

    private int size;// list实际大小

    private static final int DEFAULT_CAPACITY = 10;// 默认list容量

    protected transient int modCount = 0;// 这个在迭代遍历并发删除的的时候就可以显露问题

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2. ArrayList的常见创建方式。
   2.1 空构造函数

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;// 空构造器时，默认为容量为0的空数组
    }

2.2 初始化集合大小的构造函数（如果已知集合需要容纳元素大小，建议此方法创建）

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

3 集合操作：增加元素
3.1 添加元素（依次在数组最后一个元素添加）

public boolean add(E e) {
        // 第一步：确认list是否已满，如果未满，直接添加，如果已满则看是否需要扩容
        ensureCapacityInternal(size + 1);
        // 第二步：添加元素
        elementData[size++] = e;// 添加元素
        return true;
    }

我们知道集合优于数组的其中一个原因就是数组在声明的时候大小就确定了，不可变。而集合在添加元素可以自动扩容的。那么究竟集合是如何实现自动扩容的呢？
第一步：先来确定一下当前集合容量是否满足添加一个元素需求。

/**
     * 开始扩容，扩容的时候就需要考虑到什么时候开始扩容，扩容多大比较合适。实际上问题归根于解决扩容多大的问题。
     * 
     * @param minCapacity
     */
    public void ensureCapacityInternal(int minCapacity) {
        // 解决第一个问题：什么时候需要扩容?
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

第二步：什么时候需要扩容？

    /**
     * 开始扩容
     * 
     * @param minCapacity
     */
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity > elementData.length) {
            // 如果扩容大于新建数组的长度（数组的长度，非集合中元素的大小），这个时候需要扩容。
            grow(minCapacity);
        }
    }

第三步：如何扩容？

/**
     * 实际扩容操作
     * 
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; // 原来数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容新数组大小，为什么选择扩容原来的1.5倍？难道是这是为了节省空间最佳方案。
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity; // 从这里可以看出来，实际扩容大小，有可能不止1.5倍大小。
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            // 如果MAX_ARRAY_SIZE大小都不能满足扩容之后的新容量大小，则需要进一步扩容
            newCapacity = hugeCapacity(minCapacity);
        }

        elementData = Arrays.copyOf(elementData, newCapacity);// 最后一步最重要的是，把原来数组复制到扩容之后的数组中。这里需要使用到jdk本地库，
                                                                // 不可避免需要IO操作，如果频繁的扩容，会影响ArrayList的性能，因此如果我们知道list大小，可以直接构造出指定容量的数组
    }

/**
     * 当扩容MAX_ARRAY_SIZE都不能满足新的容量时
     * 
     * @param minCapacity
     * @return
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // 溢出
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE
                : MAX_ARRAY_SIZE;// 从这里可以看出list能够存储的最大容量是整型范围内的最大容量。
    }

3.1 指定位置添加元素

@Override
    public void add(int index, E element) {
        //第一步：查看index是否越界
        rangeAddCheck(index);
        //第二步：扩容
        ensureCapacityInternal(size + 1);
        //第三步：移动index位置（包含index）之后的元素，本质是将index往index+1的元素开始往后移动，然后将新值赋予到index位置处。
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        //第四步：添加index新值
        elementData[index] = element;
        size ++;
    }

总结一下添加的思路：检查ArrayList是否有足够的容量来存储待添加元素，如果容量不够需要扩容操作。然后创建一个扩容之后新容量的数组，并将原来数组复制到新数组中，原来数组引用指向新的数组。
3.2 删除指定位置元素

@Override
    public E remove(int index) {
        rangeCheck(index);
             
        modCount ++;
        
        int movedNum = size - index -1;//需要移动多少个元素
        E oldValue = elementData(index);
        if (movedNum > 0) {
            System.arraycopy(elementData, index+1, elementData, index, movedNum);//从index+1开始复制elementData，然后放入elementData的index位置，总共复制movedNum个元素
        }
        
        elementData[size--] = null;//把最后一个元素置空，便于垃圾回收
        return oldValue;
    }

主要思路就是，将index之后的位置统一向前移动一位，并将数组最后一个元素置null,以便于垃圾回收器回收。
3.3 修改指定位置元素

@Override
    public E set(int index, E element) {
        rangeCheck(index);
        
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;//返回的是原来index位置上的值
    }

3.4 获取元素

@Override
    public E get(int index) {
        rangeCheck(index);
        
        return elementData(index);
    }

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

/**
     * 检查是否越界
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("越界啦！");
        }
    }
    
    private void rangeAddCheck(int index){
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("越界啦！");
        }
    }

3.5 查找元素

    @Override
    public int indexOf(Object o) {
        //由于ArrayList可以放置null元素，因此在查找的时候需要分情况讨论
        if (o == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i]==null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (o.equals(elementData[i])) {//这里使用的object的equals()方法，如果又必须要需重写
                    return i;
                }
            }
        }
        
        return -1;
    }

@Override
    public int lastIndexOf(Object o) {
        // ArrayList允许null，因此通过循环遍历查找元素时，需要分为null，非null值,主要区别就是根据相等判断方法不一致。
        //如何才能这个元素最后出现的位置呢？那么我们遍历该数组的时候，需要从后面往前面遍历，这样第一次遇见的这个元素位置就是该元素最后出现的位置
        if (o == null) {
            for (int i = size-1; i >= 0; i--) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = size-1; i >= 0; i--) {
                if (o.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

其实，分析到这里我们就可以看出ArrayList的特点了：

• 自动扩容机制保证操作ArrayList时容量大小可变。
• 可通过数组下标访问元素，查询快，增删操作慢，涉及扩容，数组复制等操作。
• 线程不安全，效率高。

• 元素有序，且可为null。

  
  图片.png