死磕-java集合之ArrayList源码分析

30次阅读

共计 9712 个字符，预计需要花费 25 分钟才能阅读完成。

简介

ArrayList 是一种以数组实现的 List，与数组相比，它具有动态扩展的能力，因此也可称之为动态数组。

继承体系

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

ArrayList 实现了 List，提供了基础的添加、删除、遍历等操作。

ArrayList 实现了 RandomAccess，提供了随机访问的能力。

ArrayList 实现了 Cloneable，可以被克隆。

ArrayList 实现了 Serializable，可以被序列化。

源码解析

属性

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

/**
 * 空数组，如果传入的容量为 0 时使用
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储元素的数组【本篇文章由公众号“彤哥读源码”原创】*/
transient Object[] elementData; // non-private to simplify nested class access

/**
 * 集合中元素的个数
 */
private int size;

（1）DEFAULT_CAPACITY

默认容量为 10，也就是通过 new ArrayList()创建时的默认容量。

（2）EMPTY_ELEMENTDATA

空的数组，这种是通过 new ArrayList(0)创建时用的是这个空数组。

（3）DEFAULTCAPACITY_EMPTY_ELEMENTDATA

也是空数组，这种是通过 new ArrayList()创建时用的是这个空数组，与 EMPTY_ELEMENTDATA 的区别是在添加第一个元素时使用这个空数组的会初始化为 DEFAULT_CAPACITY（10）个元素。

（4）elementData

真正存放元素的地方，使用 transient 是为了不序列化这个字段。

至于没有使用 private 修饰，后面注释是写的“为了简化嵌套类的访问”，但是楼主实测加了 private 嵌套类一样可以访问。

private 表示是类私有的属性，只要是在这个类内部都可以访问，嵌套类或者内部类也是在类的内部，所以也可以访问类的私有成员。

（5）size

真正存储元素的个数，而不是 elementData 数组的长度。

ArrayList(int initialCapacity)构造方法

传入初始容量，如果大于 0 就初始化 elementData 为对应大小，如果等于 0 就使用 EMPTY_ELEMENTDATA 空数组，如果小于 0 抛出异常。

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 {
        // 如果传入的初始容量小于 0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity:" + initialCapacity);
    }
}

ArrayList()构造方法

不传初始容量，初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，会在添加第一个元素的时候扩容为默认的大小，即 10。

public ArrayList() {
    // 如果没有传入初始容量，则使用空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 使用这个数组是在添加第一个元素的时候会扩容到默认大小 10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(Collection<? extends E> c)构造方法

传入集合并初始化 elementData，这里会使用拷贝把传入集合的元素拷贝到 elementData 数组中，如果元素个数为 0，则初始化为 EMPTY_ELEMENTDATA 空数组。

/**
* 把传入集合的元素初始化到 ArrayList 中
*/
public ArrayList(Collection<? extends E> c) {
    // 集合转数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {// 检查 c.toArray()返回的是不是 Object[]类型，如果不是，重新拷贝成 Object[].class 类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果 c 的空集合，则初始化为空数组 EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

为什么 c.toArray(); 返回的有可能不是 Object[]类型呢？请看下面的代码：

public class ArrayTest {public static void main(String[] args) {Father[] fathers = new Son[]{};
        // 打印结果为 class [Lcom.coolcoding.code.Son;
        System.out.println(fathers.getClass());

        List<String> strList = new MyList();
        // 打印结果为 class [Ljava.lang.String;
        //【本篇文章由公众号“彤哥读源码”原创】System.out.println(strList.toArray().getClass());
    }
}

class Father {}

class Son extends Father {}

class MyList extends ArrayList<String> {
    /**
     * 子类重写父类的方法，返回值可以不一样
     * 但这里只能用数组类型，换成 Object 就不行
     * 应该算是 java 本身的 bug
     */
    @Override
    public String[] toArray() {
        // 为了方便举例直接写死
        return new String[]{"1", "2", "3"};
    }
}

add(E e)方法

添加元素到末尾，平均时间复杂度为 O(1)。

public boolean add(E e) {
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 把元素插入到最后一位
    elementData[size++] = e;
    return true;
}

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

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

    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    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);
    // 以新容量拷贝出来一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

（1）检查是否需要扩容；

（2）如果 elementData 等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 则初始化容量大小为 DEFAULT_CAPACITY；

（3）新容量是老容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)），如果加了这么多容量发现比需要的容量还小，则以需要的容量为准；

（4）创建新容量的数组并把老数组拷贝到新数组；

add(int index, E element)方法

添加元素到指定位置，平均时间复杂度为 O(n)。

public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 将 inex 及其之后的元素往后挪一位，则 index 位置处就空出来了
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将元素插入到 index 的位置
    elementData[index] = element;
    // 大小增 1
    size++;
}

private void rangeCheckForAdd(int index) {if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

（1）检查索引是否越界；

（2）检查是否需要扩容；

（3）把插入索引位置后的元素都往后挪一位；

（4）在插入索引位置放置插入的元素；

（5）大小加 1；

addAll(Collection<? extends E> c)方法

求两个集合的并集。

/**
* 将集合 c 中所有元素添加到当前 ArrayList 中
*/
public boolean addAll(Collection<? extends E> c) {
    // 将集合 c 转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 检查是否需要扩容
    ensureCapacityInternal(size + numNew);
    // 将 c 中元素全部拷贝到数组的最后
    System.arraycopy(a, 0, elementData, size, numNew);
    // 大小增加 c 的大小
    size += numNew;
    // 如果 c 不为空就返回 true，否则返回 false
    return numNew != 0;
}

（1）拷贝 c 中的元素到数组 a 中；

（2）检查是否需要扩容；

（3）把数组 a 中的元素拷贝到 elementData 的尾部；

get(int index)方法

获取指定索引位置的元素，时间复杂度为 O(1)。

public E get(int index) {
    // 检查是否越界
    rangeCheck(index);
    // 返回数组 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];
}

（1）检查索引是否越界，这里只检查是否越上界，如果越上界抛出 IndexOutOfBoundsException 异常，如果越下界抛出的是 ArrayIndexOutOfBoundsException 异常。

（2）返回索引位置处的元素；

remove(int index)方法

删除指定索引位置的元素，时间复杂度为 O(n)。

public E remove(int index) {
    // 检查是否越界
    rangeCheck(index);

    modCount++;
    // 获取 index 位置的元素
    E oldValue = elementData(index);
    
    // 如果 index 不是最后一位，则将 index 之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    
    // 将最后一个元素删除，帮助 GC
    elementData[--size] = null; // clear to let GC do its work

    // 返回旧值
    return oldValue;
}

（1）检查索引是否越界；

（2）获取指定索引位置的元素；

（3）如果删除的不是最后一位，则其它元素往前移一位；

（4）将最后一位置为 null，方便 GC 回收；

（5）返回删除的元素【本篇文章由公众号“彤哥读源码”原创】。

可以看到，ArrayList 删除元素的时候并没有缩容。

remove(Object o)方法

删除指定元素值的元素，时间复杂度为 O(n)。

public boolean remove(Object o) {if (o == null) {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素为 null，则以 null 进行比较，使用 ==
            if (elementData[index] == null) {fastRemove(index);
                return true;
            }
    } else {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素不为 null，则进行比较，使用 equals()方法
            if (o.equals(elementData[index])) {fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    // 少了一个越界的检查
    modCount++;
    // 如果 index 不是最后一位，则将 index 之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素删除，帮助 GC
    elementData[--size] = null; // clear to let GC do its work
}

（1）找到第一个等于指定元素值的元素；

（2）快速删除；

fastRemove(int index)相对于 remove(int index)少了检查索引越界的操作，可见 jdk 将性能优化到极致。

retainAll(Collection<?> c)方法

求两个集合的交集。

public boolean retainAll(Collection<?> c) {
    // 集合 c 不能为 null
    Objects.requireNonNull(c);
    // 调用批量删除方法，这时 complement 传入 true，表示删除不包含在 c 中的元素
    return batchRemove(c, true);
}

/**
* 批量删除元素
* complement 为 true 表示删除 c 中不包含的元素
* complement 为 false 表示删除 c 中包含的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;
    // 使用读写两个指针同时遍历数组
    // 读指针每次自增 1，写指针放入元素的时候才加 1
    // 这样不需要额外的空间，只需要在原有的数组上操作就可以了
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 遍历整个数组，如果 c 中包含该元素，则把该元素放到写指针的位置（以 complement 为准）for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {// 正常来说 r 最后是等于 size 的，除非 c.contains()抛出了异常
        if (r != size) {// 如果 c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // 将写指针之后的元素置为空，帮助 GC
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            // 新大小等于写指针的位置（因为每写一次写指针就加 1，所以新大小正好等于写指针的位置）size = w;
            modified = true;
        }
    }
    // 有修改返回 true
    return modified;
}

（1）遍历 elementData 数组；

（2）如果元素在 c 中，则把这个元素添加到 elementData 数组的 w 位置并将 w 位置往后移一位；

（3）遍历完之后，w 之前的元素都是两者共有的，w 之后（包含）的元素不是两者共有的；

（4）将 w 之后（包含）的元素置为 null，方便 GC 回收；

removeAll(Collection<?> c)

求两个集合的单方向差集，只保留当前集合中不在 c 中的元素，不保留在 c 中不在当前集体中的元素。

public boolean removeAll(Collection<?> c) {
    // 集合 c 不能为空
    Objects.requireNonNull(c);
    // 同样调用批量删除方法，这时 complement 传入 false，表示删除包含在 c 中的元素
    return batchRemove(c, false);
}

与 retainAll(Collection<?> c)方法类似，只是这里保留的是不在 c 中的元素。

总结

（1）ArrayList 内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList 不会进行缩容；

（2）ArrayList 支持随机访问，通过索引访问元素极快，时间复杂度为 O(1)；

（3）ArrayList 添加元素到尾部极快，平均时间复杂度为 O(1)；

（4）ArrayList 添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为 O(n)；

（5）ArrayList 从尾部删除元素极快，时间复杂度为 O(1)；

（6）ArrayList 从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为 O(n)；

（7）ArrayList 支持求并集，调用 addAll(Collection<? extends E> c)方法即可；

（8）ArrayList 支持求交集，调用 retainAll(Collection<? extends E> c)方法即可；

（7）ArrayList 支持求单向差集，调用 removeAll(Collection<? extends E> c)方法即可；

彩蛋

elementData 设置成了 transient，那 ArrayList 是怎么把元素序列化的呢？

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非 transient 非 static 属性（会写出 size 属性）s.defaultWriteObject();

    // 写出元素个数
    s.writeInt(size);

    // 依次写出元素
    for (int i=0; i<size; i++) {s.writeObject(elementData[i]);
    }

    // 如果有修改，抛出异常【本篇文章由公众号“彤哥读源码”原创】if (modCount != expectedModCount) {throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    // 声明为空数组
    elementData = EMPTY_ELEMENTDATA;

    // 读入非 transient 非 static 属性（会读取 size 属性）s.defaultReadObject();

    // 读入元素个数，没什么用，只是因为写出的时候写了 size 属性，读的时候也要按顺序来读
    s.readInt();

    if (size > 0) {
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 检查是否需要扩容
        ensureCapacityInternal(size);
        
        Object[] a = elementData;
        // 依次读取元素到数组中
        for (int i=0; i<size; i++) {a[i] = s.readObject();}
    }
}

查看 writeObject()方法可知，先调用 s.defaultWriteObject()方法，再把 size 写入到流中，再把元素一个一个的写入到流中。

一般地，只要实现了 Serializable 接口即可自动序列化，writeObject()和 readObject()是为了自己控制序列化的方式，这两个方法必须声明为 private，在 java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到 writeObject()这个方法。

在 ArrayList 的 writeObject()方法中先调用了 s.defaultWriteObject()方法，这个方法是写入非 static 非 transient 的属性，在 ArrayList 中也就是 size 属性。同样地，在 readObject()方法中先调用了 s.defaultReadObject()方法解析出了 size 属性。

elementData 定义为 transient 的优势，自己根据 size 序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

正文完
发表至： java
2019-10-06
 0
对比讲解lambda表达式与传统接口函数实现方式
关于java:面试官聊聊分布式事务再说说解决方案
关于java:Java8Stream之filter简单介绍
【Android】RxJava的使用（二）Action