死磕Jdk源码之ArrayList

死磕Jdk源码之ArrayList:

本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8版本。

简介

List接口的可调整大小的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现List接口之外，该类还提供了一些方法来操作数组的大小，该数组在内部用于存储List。(这个类大致相当于Vector，只是它是不同步的。)
size、isEmpty、get、set、iterator和listIterator操作在常数时间内运行。添加操作在平摊常数时间内运行，也就是说，添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行(粗略地说)。与LinkedList实现相比，常量因子较低。

以上是官方docs对ArrayList的描述

特性

1. ArrayList实现List，得到了List集合框架基础功能
2. ArrayList实现RandomAccess，获得了快速随机访问存储元素的功能，RandomAccess是一个标记接口，没有任何方法
3. ArrayList实现Cloneable，得到了clone()方法，可以实现克隆功能
4. ArrayList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。

它具有如下特点：

• 容量不固定，随着容量的增加而动态扩容（阈值基本不会达到）
• 有序集合（插入的顺序 == 输出的顺序）
• 插入的元素可以为null
• 增删改查效率更高（相对于LinkedList来说）
• 线程不安全

数据结构

ArrayList的底层数据结构就是一个数组，对ArrayList的所有操作底层都是基于数组的。

线程安全性

如果非要在多线程的环境下使用ArrayList，就需要保证它的线程安全性，通常有两种解决办法：

1. 使用synchronized关键字
2. 使用Collections类中的静态方法synchronizedList()对ArrayList进行调用即可。

成员变量

ArrayList有两个关键的成员变量

还有一个记录集合修改次数的变量，由iterator和listIterator，如果在迭代过程中，modCount的值变更，就会抛出ConcurrentModificationException异常。

protected transient int modCount = 0;

• elementData

存储ArrayList元素的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。任何空ArrayList与elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,将在添加第一个元素时扩展为DEFAULT_CAPACITY。

elementData就是实际维护的数组,对于一个空ArrayList来说,elementData就是一个空数组。会在第一次add元素时扩容为长度为DEFAULT_CAPACITY的数组。

• size

ArrayList的大小(它包含的元素的数量)。这里的size指的是元素的个数，而不是数组的大小。

死磕源码

构造函数

无参构造函数，elementData 等于默认的空数组

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

根据给定的初始化容量大小创建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);
    }
}

从一个Collection集合创建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;
    }
}

添加元素

ArrayList提供两个方法添加单个元素，一个可以指定索引的添加元素方法，一个不需要指定索引的添加元素方法。

• add(E e)

将指定的元素追加到此列表的末尾。

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

在ensureCapacityInternal方法中对modCount成员变量 +1,表示集合的修改次数，检查数组容量，是否需要扩容。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity方法是为了计算最小扩容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 也就是当前数组是个默认空数组,集合内无元素,此时返回 DEFAULT_CAPACITY 和 minCapacity 的最大值,否则就返回 minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity方法需要判断数组是否需要扩容

private void ensureExplicitCapacity(int minCapacity) {
    // modCount + 1 记录修改次数
    modCount++;

    // 判断数组容量是否溢出
    if (minCapacity - elementData.length > 0)
        // 这里对数组进行扩容
        grow(minCapacity);
}

grow方法，ArrayList扩容的核心方法。

private void grow(int minCapacity) {
    // 获取当前数组大小
    int oldCapacity = elementData.length;
    // 计算新的容量大小  =  oldCapacity * 1.5 (右移一位 相当于 oldCapacity / 2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 计算的新容量小于 minCapacity，就取 minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于 MAX_ARRAY_SIZE,取 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• add(int index, E element)

将指定元素插入其中的指定位置列表。移动当前处于该位置的元素(如果有)并向右的任何后续元素(将一个元素添加到它们的索引中)。

public void add(int index, E element) {

    // 检查 index 是否合法
    rangeCheckForAdd(index);

    // 同 add(E e)
    ensureCapacityInternal(size + 1);  // Increments modCount!!

    // 这里使用数组拷贝，把添加位置后的元素往后移，目的是为了空出当前索引位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 将元素插入指定的索引位
    elementData[index] = element;
    size++;
}

移除元素

• remove(int index)

根据指定索引移除元素

public E remove(int index) {

    // 检查索引是否合法
    rangeCheck(index);

    // modCount 修改次数 +1
    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;
}

• remove(Object o)

从列表中删除指定元素的第一个匹配项

public boolean remove(Object o) {
    // 如果 o 为 null，就删除第一个空元素
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } 
    // 否则就移除第一个 equals o 的元素
    else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

与remove(int index)方法逻辑相同,只是这里没有进行索引检查，因为索引本来就是从数组中遍历出来的

private void fastRemove(int index) {
    // modCount 修改次数 +1
    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
}

总结

1. ArrayList底层维护一个数组
2. ArrayList默认数组是一个空数组 {}
3. ArrayList第一次添加元素时才会扩容到 capacity 大小
4. ArrayList扩容为原容量到 1.5 倍
5. ArrayList通过索引添加元素可能会导致内存拷贝
6. ArrayList移除元素可能需要内存拷贝

所以尽量不要使用索引去添加元素，索引添加元素的效率取决于索引的位置。理论上 size - index 的值越大，效率越低，因为需要拷贝的元素越多。(移除元素同理)