荐 深深的码丨Java ArrayList 源码透析

ArrayList 本质是通过一个可变长的数组来存储不定量的元素，且当元素通过不同方式被添加存储时，总是先计算自身容量，若符合扩容标准则对数组进行扩容并拷贝原有元素

本文将基于 JDK8 对 ArrayList 源码中的构造ArrayList()、存储add()、删除remove()、扩容grow()、序列化（writeObject()、readObject()） 等过程中所涉及 JDK 源码做行级解释

若您有遇到其它相关问题，非常欢迎在评论中留言，我和其他读者小伙伴们将帮助解决并持续更新至此文，达到帮助更多人的目的。若感本文对您有所帮助请点个赞吧！

---

ArrayList 的结构定义

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    // 略···
}

定义 ArrayList 时继承 AbstractList 抽象类表示这是一个数组队列，含有增删改查遍历等常用操作。实现 RandomAccess 接口表示此对象可进行随机访问。实现 Cloneable 接口表示此对象可被克隆。实现 Serializable 接口表示此对象可被序列化与反序列化，接下来开始进入正题！

---

ArrayList 实例化

ArrstList 共提供了 3 种 构造方法，支持指定长度和指定元素内容，满足各种常见场景下对容量的需求

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 若初始化时指定了长度或添加集合，但长度为0，则赋值为此对象。若elementData等于此对象，表示有参实例化，首次add时数组仅扩容至1
    // 如：ArrayList<Integer> mArrayList = new ArrayList<Integer>(0);
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
    
    // 若初始化时不指定长度或添加集合则赋值为此对象。若elementData等于此对象，表示是无参实例化，首次add时数组默认扩充容量至10
    // 如：ArrayList<Integer> mArrayList = new ArrayList<Integer>(); 
    // 区别赋值的原因猜测是因为后者实例方式更符合实际开发需要，所以首次就给了较多容量，减少多次扩容的资源开支
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    
    // elementData 是用来保存元素的数组。因为他的容量通常大于实际使用量，会产生空余空间，所以被修饰为transient ，
    // 表示不可被序列化，避免序列化时时间与空间的浪费，而 ArrayList 的序列化与反序列化通过writeObject和readObject完成
    transient Object[] elementData;
    
    // 当前数组长度
    private int size;
    
    // 最大数组长度
    private static final int MAX_ARRAY_SIZE = 2147483639;

    // 第1种：初始化一个长度为0的空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 第2种：初始化时指定数组长度
    public ArrayList(int var1) {
        // 检查长度参数 var1 是否合法，若合法则按需创建数组
        if (var1 > 0) {
            this.elementData = new Object[var1];
        } else {
            // 若 var1 非零则表示为负数，抛出非法参数异常
            if (var1 != 0) {
                throw new IllegalArgumentException("Illegal Capacity: " + var1);
            }
            // 若 var1 为零，则创建长度为0的数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    // 第3种：初始化时批量添加元素
    public ArrayList(Collection<? extends E> var1) {
        // 将传入的集合转为数组，并将结果进行赋值
        this.elementData = var1.toArray();
        // 若转换结果不为空，则继续处理
        if ((this.size = this.elementData.length) != 0) {
            if (this.elementData.getClass() != Object[].class) {
                this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
            }
        } else {
            // 若传入的集合为空，则仅仅只是初始化一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

---

ArrayList 添加元素

ArrstList 共提供 4 种添加元素方法，支持指定位置、批量添加，在此检查是否符合扩容条件

    // 第1种：添加一个在数组创建时指定类型的元素
    public boolean add(E var1) {
        // 检查是否需要扩容
        this.ensureCapacityInternal(this.size + 1);
        // 向数组尾部插入新元素（size表示当前数组中最后一个被插入元素的下标）
        this.elementData[this.size++] = var1;
        return true;
    }

    // 第2种：在指定位置，添加一个在数组创建时指定类型的元素
    public void add(int var1, E var2) {
        // 检查下标边界是否合法
        this.rangeCheckForAdd(var1);
        // 检查是否需要扩容
        this.ensureCapacityInternal(this.size + 1);
        // 移动当前数组内元素位置
        System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
        // 向指定位置插入新元素
        this.elementData[var1] = var2;
        // 更新尾元素下标位置
        ++this.size;
    }

    // 第3种：添加一组指定类型的元素
    public boolean addAll(Collection<? extends E> var1) {
        // 转化为数组
        Object[] var2 = var1.toArray();
        // 记录数组长度
        int var3 = var2.length;
        // 检查是否需要扩容
        this.ensureCapacityInternal(this.size + var3);
        // 向数组尾部插入一组新元素
        System.arraycopy(var2, 0, this.elementData, this.size, var3);
        // 更新尾元素下标位置
        this.size += var3;
        // 返回批量添加结果
        return var3 != 0;
    }

    // 第4种：指定起始位置，添加一组指定类型的元素，
    public boolean addAll(int var1, Collection<? extends E> var2) {
        // 检测起始位置是否合法
        this.rangeCheckForAdd(var1);
        // 转化为数组
        Object[] var3 = var2.toArray();
        // 记录数组长度
        int var4 = var3.length;
        // 检查是否需要扩容
        this.ensureCapacityInternal(this.size + var4);
        // 计算所需插入区间的下标
        int var5 = this.size - var1;
        if (var5 > 0) {
            // 移动当前元素位置
            System.arraycopy(this.elementData, var1, this.elementData, var1 + var4, var5);
        }
        // 将新数组插入指定位置
        System.arraycopy(var3, 0, this.elementData, var1, var4);
        // 更新尾元素下标位置
        this.size += var4;
        // 返回批量添加结果
        return var4 != 0;
    }

相关方法源码解析

    // 计算数组长度
    private void ensureCapacityInternal(int var1) {
        // 若当前数组长度为 0 ，则比较 (10) 与 (目标长度) ，结果取大并更新目标数组长度值
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            var1 = Math.max(10, var1);
        }
        // 根据目标数组长度值，检查是否需要扩容
        this.ensureExplicitCapacity(var1);
    }

    // 检查是否需要扩容
    private void ensureExplicitCapacity(int var1) {
        // fail-fast 机制用到的修改次数计数（ArrayList非线程安全，所以在使用迭代器过程中被修改的话，会抛出 ConcurrentModificationExceptions）
        ++this.modCount;
        // 如果计算出来的目标数组长度 大于 当前数组的长度，则表示数组需要扩容
        if (var1 - this.elementData.length > 0) {
            this.grow(var1);
        }
    }

    // 数组扩容
    private void grow(int var1) {
        // 当前数组长度
        int var2 = this.elementData.length;
        // 扩容数组长度（默认1.5倍，也就是增加当前长度的50%）
        int var3 = var2 + (var2 >> 1);
        // 如果扩容数组长度 小于 传入的目标数组长度，则更新扩容目标
        if (var3 - var1 < 0) {
            var3 = var1;
        }
        // 扩容最大边界检查
        if (var3 - 2147483639 > 0) {
            var3 = hugeCapacity(var1);
        }
        // 数组扩容至目标长度，且保存现有元素
        this.elementData = Arrays.copyOf(this.elementData, var3);
    }

    // 检查目标插入下标边界是否合法
    private void rangeCheckForAdd(int var1) {
        if (var1 > this.size || var1 < 0) {
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
        }
    }

    // 扩容长度检查
    private static int hugeCapacity(int var0) {
        if (var0 < 0) {
            // 非法参数则抛出异常
            throw new OutOfMemoryError();
        } else {
            // 如果扩容目标大于 最大允许数组长度，则比较 是否大于 2147483639，大于的话 扩容目标=2147483647，反之扩容目标=2147483639
            return var0 > 2147483639 ? 2147483647 : 2147483639;
        }
    }

---

ArrayList 删除元素

ArrstList 共提供 3 种删除元素方法，支持通过下标或对象删除

    // 第1种：删除指定下标的元素(从0开始)
    public E remove(int var1) {
        // 检测下标是否合法
        this.rangeCheck(var1);
        // fail-fast 机制用到的修改次数计数（ArrayList非线程安全，所以在使用迭代器过程中被修改的话，会抛出 ConcurrentModificationExceptions）
        ++this.modCount;
        // 获取即将被删除的元素
        Object var2 = this.elementData(var1);
        // 计算需要移动的元素数量
        int var3 = this.size - var1 - 1;
        if (var3 > 0) {
            // 移动元素（被删除的元素，将被它后一个元素直接覆盖）
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
        }
        // 将尾部元素置空，因为它已被复制到前一个下标位置
        this.elementData[--this.size] = null;
        // 返回处理结果
        return var2;
    }

    // 第2种：删除指定对象
    public boolean remove(Object var1) {
        // 遍历起始下标
        int var2;
        // 如果需要删除空对象
        if (var1 == null) {
            // 遍历当前数组中的空对象（但仅仅删除首个符合要求的元素）
            for(var2 = 0; var2 < this.size; ++var2) {
                // 发现目标
                if (this.elementData[var2] == null) {
                    // 删除
                    this.fastRemove(var2);
                    return true;
                }
            }
        } else {
            // 遍历数组中的目标对象（但仅仅删除首个符合要求的元素）
            for(var2 = 0; var2 < this.size; ++var2) {
                // Object 的 equals 和 == 比较的均是地址值
                // String 的 == 比较的是值，equals 则先比较地址，再顺序比较字符
                if (var1.equals(this.elementData[var2])) {
                    // 若相等则删除
                    this.fastRemove(var2);
                    return true;
                }
            }
        }
        return false;
    }

    // 第3种：清空
    public void clear() {
        ++this.modCount;

        for(int var1 = 0; var1 < this.size; ++var1) {
            this.elementData[var1] = null;
        }
        this.size = 0;
    }

相关方法源码解析

    // 检查下标是否合法
    private void rangeCheck(int var1) {
        // 若删除的元素下标大于数组内最后一个元素的下标，抛出 IndexOutOfBoundsException
        // var1 是下标，从0开始 ; this.size 是数组长度，从1开始，所以最后一个元素的下标最大也只能是 this.size - 1
        if (var1 >= this.size) {
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
        }
    }

    // 执行 remove() 的删除操作（也可以讲是覆盖）
    private void fastRemove(int var1) {
        // 执行了删除操作，计数更新（用于 Fail-Fast 机制）
        ++this.modCount;
        // 计算需要移动的元素数量
        int var2 = this.size - var1 - 1;
        if (var2 > 0) {
            // 移动元素（被删除的元素，将被它后一个元素直接覆盖）
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var2);
        }
        // 将尾部元素置空，因为它已被复制到前一个下标位置
        this.elementData[--this.size] = null;
    }

---

System.arraycopy() 数组复制

在对 ArrayList 进行操作的的过程中，System.arraycopy() 这个 native 方法被频繁使用，它的作用是实现高效的数组间复制，在此标注下各项参数含义，避免产生困扰

public static native void arraycopy(Object var0, int var1, Object var2, int var3, int var4);

Object var0 ：源数组
int var1 ： 源数组复制起始下标
Object var2 ： 目标数组
int var3 ： 目标数组存储起始下标
int var4 ： 需复制长度

---

ArrayList 序列化

通过源码我们可以看到这项定义： transient Object[] elementData;，这表示被 transient 修饰的数组不可被序列化，但 elementData 又是实际存储了元素的数组，且 ArrayList 肯定可以序列化传输，那么这么操作的原因是为什么？

很简单，当 Arraylist 被定以后，每次添加元素都需检查当前容量是否符合扩容标准，而扩容并不会在数组长度被用完时进行，所以数组的长度总是大于实际使用长度，而在这种情况下直接序列化对象，必然造成时间成本与空间资源的浪费，所以 ArrayList 内提供了 writeObject 与 readObject 两个方法，以 this.size 为循环条件，只处理有效元素

	transient Object[] elementData;
	
	// 略···

    private void writeObject(ObjectOutputStream var1) throws IOException {
        int var2 = this.modCount;
        var1.defaultWriteObject();
        var1.writeInt(this.size);

        for(int var3 = 0; var3 < this.size; ++var3) {
            var1.writeObject(this.elementData[var3]);
        }

        if (this.modCount != var2) {
            throw new ConcurrentModificationException();
        }
    }

    private void readObject(ObjectInputStream var1) throws IOException, ClassNotFoundException {
        this.elementData = EMPTY_ELEMENTDATA;
        var1.defaultReadObject();
        var1.readInt();
        if (this.size > 0) {
            this.ensureCapacityInternal(this.size);
            Object[] var2 = this.elementData;

            for(int var3 = 0; var3 < this.size; ++var3) {
                var2[var3] = var1.readObject();
            }
        }
    }

---

若您有遇到其它相关问题，非常欢迎在评论中留言，我和其他读者小伙伴们将帮助解决并持续更新至此文，达到帮助更多人的目的。若感本文对您有所帮助请点个赞吧！

本文地址：https://blog.csdn.net/qq_15609303/article/details/107180861