JDK 源码阅读002：ArrayList

· 2019-03-05 ·

ArrayList 源码阅读~

1 引言
2 继承关系
3 初始化
4 核心方法
- 4.1 set
- 4.2 add
- 4.3 get
- 4.4 remove
5 扩容机制
6 Fail-Fast
- 参考

1 引言

首先，我们要对 ArrayList 的特点有一个基本的认识，比如说：

ArrayList 底层是用什么实现的？
缺点是什么？有点又是什么？
扩容机制了解吗

其实 ArrayList 底层是基于数组来实现的，随机读的时间复杂度为 O(1)，对于删除的的时间复杂度为O(N)。所以 ArrayList 的优势在于随机读，缺点有两个地方，一个是不断地添加元素的时候，会扩容，扩容会导致性能较差，另一个删除元素的时候，会导致大量元素的拷贝，性能也较差。

2 继承关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。

ArrayList实现了List，提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess，提供了随机访问的能力。
ArrayList实现了Cloneable，可以被克隆。
ArrayList实现了Serializable，可以被序列化。

3 初始化

一共 3 个构造函数

不指定初始大小，默认为 10

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定初始大小

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

传入指定集合初始化

    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

4 核心方法

4.1 set

public E set(int index, E element) {
        // 判断是否数组越界
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
}

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.2 add

在末尾插入

	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
 }

在指定下标插入

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

// 添加时判断数据越界
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.3 get

直接通过索引下标获取元素

public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    return ArrayList.this.elementData(offset + index);
}

4.4 remove

调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)。

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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

5 扩容机制

在添加元素的时候，可能会触发扩容机制，新容量的大小为 oldCapacity + (oldCapacity >> 1)，大约是旧容量的 1.5 倍左右。

6 Fail-Fast

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

参考

ArrayList