烟霞志

【Java容器】ArrayList源码解读

前言

首先推荐一个特别好的git仓库：https://github.com/wupeixuan/JDKSourceCode1.8
有比较详细的中文注释，大家可以git下来或者fork到自己的仓库仔细研读。

正文

在解读List源码之前，需要对数据结构中的数组、链表有一定的认识。
如有需要，可以参考本人的博客：
数组

ArrayList简介

  • 概述：List接口可调整大小的数组实现。实现所有可选的List操作，并允许所有元素，包括null，元素可重复。
  • 时间复杂度：方法size、isEmpty、get、set是常数时间的。添加删除的时间复杂度为O(N)。
  • 容量：每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10。也可以通过带初始容量的构造器初始化这个容量。容量可以自动增长。
  • ArrayList是线程不安全的。如果需要应用到多线程中，需要在外部做同步。
  • 快速失败： modeCount，定义在AbstractList中：protected transient int modCount = 0;已从结构上修改此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。在并发环境下，每次迭代时会比较modeCount的值是否与当前相等，如果不相等说明有别的线程修改了数组，则会抛出异常，这就是快速失败。

ArrayList属性

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

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

    /**
     * 空的对象数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 默认的空数组
     * 无参构造函数创建的数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存放数据的数组的缓存变量，不可序列化
     */
    transient Object[] elementData;

    /**
     * 元素数量
     *
     * @serial
     */
    private int size;
    // 省略方法
}

ArrayList构造方法

无参构造方法

  • 如果不传入参数，则使用默认无参构建方法创建ArrayList对象
  • 此时elementData 的size为0，当第一次add()时会变为默认的长度：10
public ArrayList() {
    // 直接将空数组赋给elementData
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

带有容量initialCapacity的构造方法

  • 传入参数代表ArrayList的初始长度，如果大于0，new一个指定大小的Object数组赋值给elementData，如果等于0，则默认将空数组EMPTY_ELEMENTDATA赋值给elementData，小于0则抛出IllegalArgumentException，参数不合法。
public ArrayList(int initialCapacity) {
    // 如果初始化时ArrayList大小大于0
    if (initialCapacity > 0) {
        // new一个该大小的object数组赋给elementData
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {// 如果大小为0
        // 将空数组赋给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {// 小于0
        // 则抛出IllegalArgumentException异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

带参数Collection的构造方法

  • 将集合对象转换为数组，然后将数组的地址的赋给elementData。
  • 更新size的值，同时判断size的大小，如果是size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData。
  • 如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toarray可能（错误地）不返回对象[]（见JAVA BUG编号6260652）
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // 使用空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

add(E e)，添加到ArrayList末尾

  • 首先需要判断数组是否能够存储下这个元素
  • 如果是第一次添加，则会将数组长度初始化为默认长度：10
  • 如果存储得下，直接将元素e赋值给elementData的size+1的位置
  • 如果存储不下，则调用grow方法，将数组长度扩容为原来的1.5倍

实现代码：

方法入口：
public boolean add(E e) {
    // 根据情况扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将e赋值给elementData的size+1的位置
    elementData[size++] = e;
    return true;
}

// 扩容
private void grow(int minCapacity) {
    // 获取到ArrayList中elementData数组的内存空间长度
    int oldCapacity = elementData.length;
    // 扩容至原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，
    // 不够就将数组长度设置为需要的长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //若预设值大于默认的最大值检查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
    // 并将elementData的数据复制到新的内存空间
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add(int index, E element) 添加元素到指定位置

  • 先判断指定的位置是否数组越界
  • 根据情况扩容
  • 将elementData从index位置后的数组，复制到elementData的index+1开始的连续空间
  • 在elementData的index位置赋值element

代码：

public void add(int index, E element) {
    // 判断index是否越界
    rangeCheckForAdd(index);
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
    //src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度
    // 将elementData从index位置开始，复制到elementData的index+1开始的连续空间
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 在elementData的index位置赋值element
    elementData[index] = element;
    // ArrayList的大小加一
    size++;
}

remove(int index)删除指定位置的元素

  • 判断index是否数组越界
  • 将elementData数组index+1后的数组拷贝到elementData从index开始的空间
  • 使size-1 ，设置elementData的size位置为空，让GC来清理内存空间
  • 返回之前的值

代码如下：

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

    modCount++;
    // 读取旧值
    E oldValue = elementData(index);
    // 获取index位置开始到最后一个位置的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    // 使size-1 ，设置elementData的size位置为空，让GC来清理内存空间
    elementData[--size] = null; //便于垃圾回收器回收

    return oldValue;
}

省略get、set。

烟霞志

© 2024 烟霞志