ArrayList源码分析

1 先看属性

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

//当用户指定ArrayList容量为0时，返回该空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 当用户没有指定ArrayList的容量时，返回的是该数组
 * 当与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回的
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 当用户没有指定ArrayList的容量时，返回的是该数组
 * 当该数组为DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，首次元素添加到ArrayList中时，数组将 
 * 扩容至DEFAULT_CAPACITY大小
 */
transient Object[] elementData;

/**
 * ArrayList实际存储的数据数量
 */
private int size;

2 构造方法

2.1 ArrayList(int initialCapacity)

构造一个具有指定初始容量的空列表

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //如果从参数大于0，创建对应大小的数组。
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果等于0，返回EMPTY_ELEMENTDATA。
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果是负数，抛异常。
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

2.2 ArrayList()

/**
 * 无参构造函数
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2.3 ArrayList(Collection<? extends E> c)

public ArrayList(Collection<? extends E> c) {
    //将集合转换为Object[]数组
    elementData = c.toArray();
    //把转化后的数组长度赋值给size属性，并判断是否为0
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //这句话的意思是：c.toArray可能不会返回Object[]，可以查看java官方编号为6260652的bug
        if (elementData.getClass() != Object[].class)
            //若c.toArray()返回的数组类型不是Object[]，则利用Arrays.copyOf来构造一个大小为size的Object[]数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果为0替换空数组，防止创建过多的空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

3 方法

3.1 boolean add(E e)

将指定的元素添加到此列表的尾部

public boolean add(E e) {
    //将size + 1传递到这个方法，保证资源不浪费
    ensureCapacityInternal(size + 1);  // Increments modCount!!()
    //size存放的是长度，不是下标，先利用原来size修改下标值，再将size++
    elementData[size++] = e;
    return true;
}

/**
 * 扩容方法（后面会经常见到）
 */
private void ensureCapacityInternal(int minCapacity) {
    //如果elementData是空数组，则取默认容量和minCapacity的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的
    modCount++;

    // overflow-conscious code
    //防止溢出代码，确保指定的最小容量 > 数组缓冲区当前的长度
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 扩容，确保minCapacity至少能存储minCapacity个元素
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //运算符>>是带符号右移，如果oldCapacity = 2， newCapacity = 2 + (2 >> 1) = 2 + 1 = 3
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果newCapacity依旧小于minCapacity则将minCapacity赋值给newCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果newCapacity大于最大容量，则直接分配Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //Arrays.copyOf()：将原来的数组扩容到newCapacity大小，扩容的部分用null填充
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 这个比较简单，如果是负数则报错，传入的参数大于最大容量返回int最大值，否则返回最大容量。
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

3.2 void add(int index, E e)

将指定的元素插入此列表中的指定位置。

public void add(int index, E element) {
    //判断角标是否越界（看下面的比较的方法，意思就是角标最大是size，也就是当前最大下标 + 1，
    //如果index == size，那就跟add(E e)效果一样）
    rangeCheckForAdd(index);
    //这个方法上面有
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这个方法的意思是将原来的数组下标从index到最后，往后都移动一位
    //比如index是2，原数组是[1, 2, 3, 4, null] 执行完后 [1, 2, 3, 3, 4]
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //修改数组下标为index的值
    elementData[index] = element;
    size++;
}

/**
 * 添加时检查索引是否越界
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3.3 boolean addAll(Collection<? extends E> c)

按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

public boolean addAll(Collection<? extends E> c) {
    //将集合类变成数组
    Object[] a = c.toArray();
    //获取数组大小（这个大小也是扩容的大小，同时是System.arraycopy()的长度）
    int numNew = a.length;
    //扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将数组a复制到现有数组，
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

3.4 boolean addAll(int index, Collection<? extends E> c)

从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

public boolean addAll(int index, Collection<? extends E> c) {
    //检查index是否越界
    rangeCheckForAdd(index);
    
    //转换成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount

    //这个值是需要移动的长度
    int numMoved = size - index;
    //判断是否是从末尾插入
    if (numMoved > 0)
        //将原数组的index位置到最后的数组移动，预留出来numNew长度
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    //将数组a从下标0开始，插入到原数组，原数组从index开始插入，长度为a.length
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

3.5 void clear()

移除此列表中的所有元素。

public void clear() {
    modCount++;

    // clear to let GC do its work
    //循环把数组中的每个地址都指向null，gc会把每个对象进行回收
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    //size置为0，但其实数组长度还是那么多
    size = 0;
}

3.5 boolean contains(Object o)

public boolean contains(Object o) {
    //结果大于0返回true
    return indexOf(o) >= 0;
}

/**
 * 循环比较数组中每个元素的值，返回列表中首次出现的指定元素的下标，如果此列表不包含则返回-1
 */
public int indexOf(Object o) {
    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]))
                return i;
    }
    return -1;
}

3.6 E get(int index)

返回此列表中指定位置上的元素。

public E get(int index) {
    //检查数组下标是否越界
    rangeCheck(index);

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    //返回数组中对应下标元素
    return (E) elementData[index];
}

3.7 int indexOf(Object o)

返回列表中首次出现的指定元素的下标，如果此列表不包含则返回-1（其实contains就是利用了该方法）

/**
 * 循环比较数组中每个元素的值，返回列表中首次出现的指定元素的下标，如果此列表不包含则返回-1
 */
public int indexOf(Object o) {
    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]))
                return i;
    }
    return -1;
}

3.8 int lastIndexOf(Object o)

返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。

/**
 * 换汤不换药，从后往前遍历
 */
public int lastIndexOf(Object o) {
    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;
}

3.9 E remove(int index)

移除此列表中指定位置上的元素。

public E remove(int index) {
    //判断下标是否越界
    rangeCheck(index);

    modCount++;
    //获取被移除的元素，最后返回用
    E oldValue = elementData(index);

    //判断移除的元素是否是数组中最后一个元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //如果不是，则将原数组index位置之后的元素都往前移动
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //将最后一个元素设置为null，size--
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

3.10 boolean remove(Object o)

移除此列表中首次出现的指定元素（如果存在）。

public boolean remove(Object o) {
    //如果需要移除的值是null，那么就循环数组通过==null比较。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    //如果移除的值是对象，那么就循环数组通过equals进行比较。（这也是为什么说写一个
    //类要重写equals方法，因为默认的equals比较的是地址，如果不重写这种集合类的方法就会失效）
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/**
 * 私有的remove方法，与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
}

3.10 E set(int index, E element)

用指定的元素替代此列表中指定位置上的元素。（这个注释就不一行一行加了，相信看到这里大家就都能看懂了）

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}