ArrayList

ArrayList集合是我们平时使用相当多的集合了，本文是我学习ArrayList的源码，对于ArrayList源码相关方法实现的记录。

ArrayList继承结构

ArrayList初始化

其实ArrayList底层就是一个数组。

private transient Object[] elementData;

对这个数组（也就是ArrayList）的初始化一共有三种方式，分别如下。

/**
* 第一种方式，设定初始大小。
**/
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

/**
* 第二种方式，初始化为空的数组。
**/
private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

/**
* 第三种方式，使用现有的集合，对ArrayList进行初始化
**/
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

ArrayList底层原理

ArrayList底层就是一个数组，所有add进去的对象都会存储在elementData这个数组中。

private transient Object[] elementData;        //存储对象的数组

首先先来看add方法，这里有重载的add方法允许我们分别在index位置和集合最后一个对象后面添加对象。

在调用add方法添加对象的时候，会先调用ensureCapacityInternal方法，该方法会判断elementData是否是空的数组，如果是的话，那么将会把最小容量设置为10，否则最小容量为size + 1。之后调用ensureExplicitCapacity方法，如果最小容量大于elementData的长度，那么代表数组存不下了，那么则进行grow方法进行数组的扩容操作。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //插入新元素，判断size+1是否超过了数组的大小，如果超过了则进行扩容
        elementData[size++] = e;
        return true;
    }

private static final int DEFAULT_CAPACITY = 10;    //集合的默认长度

private void ensureCapacityInternal(int minCapacity) {
        //判空操作，如果elementData是{}的话，则minCapacity将变成默认长度10。
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //如果size +1大于elementData的长度，那么就代表数组不够存了，就要调用grow对数组进行扩容。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//elementData扩容方法
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //新的容量为旧容量的1.5倍。
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);    //将旧数组中的元素拷贝到新容量的新数组中
    }

/**
* 在集合指定位置插入对象，与上面的add方法原理相同。
**/
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++;
    }

add方法总结：调用方法时，则判断size+1是否还小于elementData的长度，也就是数组是否还能存的下，如果存不下，则将数组扩容为原来的1.5倍长度，将旧数组中的所有对象拷贝到新长度的数组中，从而先实现了ArrayList可以无限存入对象。

toArray方法

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

public <T> T[] toArray(T[] a) {          //普遍使用这个
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

get方法

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

private void rangeCheck(int index) {          //判断是否会发生数组越界
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

E elementData(int index) {
        return (E) elementData[index];
    }

检查index是否数组越界了，之后返回对应位置的对象。

remove方法（容易遇坑的方法）

这里容易遇到两个坑

坑一，使用for循环时删除元素。
下面代码是为了删除集合中2的倍数的元素。

public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(2);
        arrayList.add(4);
        arrayList.add(5);
        arrayList.add(4);
        arrayList.add(0);
        arrayList.add(1);
        arrayList.add(8);

        for(int i = 0; i < arrayList.size(); i++){
            if((arrayList.get(i) % 2) == 0){
                arrayList.remove(i);
            }
        }

        System.out.println(Arrays.toString(arrayList.toArray()));
    }

最后运行结果为 [4, 5, 0, 1]
那么问题来了，4也是2的倍数，怎么没被删除？

观察remove的代码

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);    //删除index位置的元素，所有元素向前移动。
        elementData[--size] = null; 

        return oldValue;
    }

这里使用 System.arraycopy（）方法，将index位置后的元素向前移动。那么此时i指向的位置还是index的位置，但是i+1指向的却是删除之前index+2的位置了，也就是说下一次循环，就会跳过一个元素。所以每一次删除之后要将i--。

坑二，使用foreach循环的时候进行remove操作。

public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(2);
        arrayList.add(4);
        arrayList.add(5);
        arrayList.add(4);
        arrayList.add(0);
        arrayList.add(1);
        arrayList.add(8);

        for(Integer integer : arrayList){
            if((integer % 2) == 0){
                arrayList.remove(integer);
            }
        }

        System.out.println(Arrays.toString(arrayList.toArray()));
    }

这是会报ConcurrentModificationException异常
观察源码

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
    }

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

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

原因：foreach使用的是迭代器，每一次remove，modCount都会+1，之后iterator调用next方法，会执行checkForComodification方法，就会发现modCount和expectedModCount值不同就会出现异常。
解决办法，获得迭代器对象，使用迭代器的remove方法。

Java集合 - ArrayList