这可能是最详细的ArrayList源码分析

本文内容基于 jdk1.8 环境

本文最先在我的个人博客发布，CSDN为同步发布，如有需要，可以访问腿短快跑的个人博客获取更多内容

源码获取

jdk 源码在我们 jdk 的安装目录下即可找到：

• jdk1.8
  在 jdk1.8 及之前的版本中，jdk的源码均可在安装目录的根目录下找到 src.zip，此包即为 jdk 源码

• jdk11
  从 jdk11 开始，jdk的源码包放在 jdk 安装目录下的 lib 目录下，在 lib 目录下找到 src.zip 即为源码

实现接口

ArrayList 实现了以下接口：

• List
  实现了 List 接口，Java集合框架中常用接口

• RandomAccess
  用于实现随机访问功能，因为底层使用数组实现，可以通过下标实现随机访问

• Cloneable
  克隆接口，用于实现两个 List 之间的克隆

• Serializable
  序列化接口

核心属性

// 定义默认List大小private static final int DEFAULT_CAPACITY = 10;// 用于存储实际 ArrayList 中的数据transient Object[] elementData;// 用于存储当前 ArrayList 的大小private int size;

从上述代码中我们可以得出以下结论：

• ArrayList 默认初始化大小为 10
• ArrayList 实际大小使用 size 变量存储
• ArrayList 底层数据使用 Object 数组存储

为什么数组使用transient关键字

transient关键字用于修饰类成员变量，不能用于修饰方法，用于标记对应的类成员变量不是类持久化状态的一部分。

jvm默认序列化和反序列创建字节流的过程中会忽略 transient 关键字修饰的类成员变量

ArrayList 中底层数组使用 transient 修饰是出于性能考虑，因为底层数据结构是数组，因此必然存在很多数组空间未使用的情况，直接序列化将导致序列化性能大大降低和资源的浪费

虽然因为底层数组使用 transient 修饰导致数组不能由jvm默认序列化，但是通过定义writeObject和readObject方法，自定义实现了列表元素的序列化与反序列化。此内容文章后续讲解

核心方法

构造方法

此处以指定大小为例，其他构造方法类似

用于初始化 ArrayList

// 默认空数组private static final Object[] 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); }    }

1. 如果初始化大小 > 0 ，则创建一个对应大小的 Object 数组
2. 如果初始化大小 == 0，则使用默认的静态空数组，此处是为了减少空间占用，避免多个空数组占用内存
3. 如果初始化大小 < 0，则抛出异常

indexOf(Object o)

查找元素出现的第一个位置

    public int indexOf(Object o) { if (o == null) {     for (int i = 0; i < size; i++)  if (elementData[i]==null)      return i; } else {     for (int i = 0; i < size; i++)  if (o.equals(elementData[i]))      return i; } return -1;    }

1. 判断元素是否为空
2. 遍历数组列表，找到值相同的索引返回，此处比较是否相同使用的 equals 方法
3. 如果未找到对应的元素，返回 -1

lastIndexOf(Object o)

查找元素出现的最后一个位置

    public int lastIndexOf(Object o) { if (o == null) {     for (int i = size-1; i >= 0; i--)  if (elementData[i]==null)      return i; } else {     for (int i = size-1; i >= 0; i--)  if (o.equals(elementData[i]))      return i; } return -1;    }

1. 判断元素是否为空
2. 从数组末尾向前遍历，找到第一个值相同的索引返回，同上，使用 equals 方法
3. 如果未找到对应的元素，返回 -1

clone()

克隆出一个新的 List

    public Object clone() { try {     ArrayList<?> v = (ArrayList<?>) super.clone();     v.elementData = Arrays.copyOf(elementData, size);     v.modCount = 0;     return v; } catch (CloneNotSupportedException e) {     // this shouldn't happen, since we are Cloneable     throw new InternalError(e); }    }

1. 底层是使用 System.arraycopy 实现的
2. System.arraycopy 是native方法
3. System.arraycopy 当数组是基础数据类型或者是 String 类型的时候是深拷贝
4. System.arraycopy 当数组是非基础数据类型且非 String 类型的时候是浅拷贝
5. System.arraycopy 是不安全的

get(int index)

获取指定位置的元素

    public E get(int index) { rangeCheck(index); return elementData(index);    }

1. 进行范围检查，如果出现数组越界，直接抛出异常
2. 返回数组对应下标位置的数据

set(int index, E element)

设置指定位置的元素

    public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;    }

1. 进行范围检查，如果出现数组越界，直接抛出异常
2. 获取对应索引位置的值
3. 将对应索引位置的值设置为新值
4. 返回旧值

add(E e)

在 ArrayList 的末尾添加元素

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

1. 当前大小+1作为最小数组容量
2. 检查容量是否需要扩容，如果需要扩容，则执行扩容操作
3. 设置数组后面一个元素为对应的元素
4. 返回结果

扩容操作

数组扩容操作

    /**     * 检查容量，不满足则扩容     */    private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));    } /**     * 计算应该扩容到的容量     */    private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {     return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;    } /**     * 判断是否需要扩容     */    private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0)     grow(minCapacity);    } /**     * 扩容操作     */    private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0)     newCapacity = minCapacity; 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);    }

1. 计算当前应该扩容到的容量
   a. 数组是否是默认的空数组，是则返回当前最小容量和默认容量(10)的最大值
   b. 否则，返回当前最小容量
2. 判断是否需要扩容
   a. 先对 modCount 增加，modCount 用于标识数组是否被修改过，用于提供快速失败的实现
   b. 判断应该扩容到的容量是否超过了当前底层数组的实际大小，如果超过了才需要扩容
3. 如果需要扩容则执行扩容
   a. 计算出新的数组大小 = 旧的数组的大小 + 旧的数组的大小 / 2，即，扩容后的大小为原数组大小的 1.5 倍，采用 >> 1 的写法是为了提升性能
   b. 如果新的数组的大小 < 应该扩容的数组的大小，则新的数组的大小设置为应该扩容的数组的大小
   c. 如果新的数组的大小超出了最大数组的大小(Integer.MAX_VALUE - 8 = 2147483639)，则新数组的大小设置为 Integer.MAX_VALUE，否则为数组的最大大小(Integer.MAX_VALUE - 8 = 2147483639)
   d. 如果扩容的数组的大小出现了数据溢出，则会抛出 OutOfMemoryError 内存溢出异常
   e. 创建新的数组，将旧数组数据复制到新的数组中

add(int index, E element)

在指定索引位置插入元素

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

1. 范围检查，如果出现数组越界，抛出异常
2. 当前大小+1作为数组最小容量
3. 检查容量是否需要扩容，如果需要扩容，则执行扩容操作
4. 将指定位置的数组内容向后移动一位
5. 在指定位置设置数组的元素值
6. 数组size+1

remove(int index)

移除指定位置的元素

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

1. 进行范围检查，如果出现数组越界，直接抛出异常
2. 获取对应索引位置的数据
3. 计算出需要移动的位置的索引，如果索引 > 0，则将后面的数组的内容向前移动一位
4. 将数组的最后一个元素设置为null
5. 返回旧数据

remove(Object o)

移除指定元素，仅会移除第一次出现的元素

    public boolean remove(Object o) { if (o == null) {     for (int index = 0; index < size; index++)  if (elementData[index] == null) {      fastRemove(index);      return true;  } } else {     for (int index = 0; index < size; index++)  if (o.equals(elementData[index])) {      fastRemove(index);      return true;  } } return false;    } /**     * 快速移除指定位置的元素     */     private void fastRemove(int index) { 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. 判断要移除的元素是否为null
2. 从开始位置遍历数组元素，判断元素是否相等，如果相等，则执行快速移除(同 remove(int index) 方法的实现)，移除后返回结果

clear()

清空 ArrayList

    public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++)     elementData[i] = null; size = 0;    }

1. 修改数量+1，用于提供快速失败机制
2. 从开始位置遍历数组，将数组中的元素全部设置为null
3. 设置 size 大小为 0

addAll(Collection c)

添加集合元素至 ArrayList 结尾

    public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew);  // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0;    }

1. 将集合转换为数组
2. 当前大小+新数组的大小作为最小容量
3. 根据最小容量判断是否需要扩容，如果需要扩容，执行扩容操作
4. 将新数组复制到数组的末尾
5. size大小更新为当前新的大小
6. 返回新增结果

addAll(int index, Collection c)

在指定位置添加集合元素

    public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew);  // Increments modCount int numMoved = size - index; if (numMoved > 0)     System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;    }

1. 进行范围检查，如果出现数组越界，直接抛出异常
2. 将集合转换为数组
3. 当前大小 + 新数组的大小作为最小容量
4. 根据最小容量判断是否需要扩容，如果需要扩容，执行扩容操作
5. 将当前数组从index开始位置的元素全部向后移动新数组大小的位置
6. 将新数组的元素从index位置开始复制
7. size大小更新为当前新的大小
8. 返回新增结果

removeRange(int fromIndex, int toIndex)

移除指定区间内的元素

    protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex,    numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) {     elementData[i] = null; } size = newSize;    }

1. 修改数量+1，用于提供快速失败机制
2. size-toIndex是需要移动的元素的个数
3. 将需要移动的元素移动至 fromIndex 位置
4. size - (toIndex-fromIndex) 是现在新的数组的实际大小
5. 从新的大小位置开始，将后面的元素全部设置为null
6. size设置为新的大小

removeAll(Collection c)

移除包含集合中的所有元素

    public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false);    } /**     * 批量移除元素     */    private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try {     for (; r < size; r++)  if (c.contains(elementData[r]) == complement)      elementData[w++] = elementData[r]; } finally {     // Preserve behavioral compatibility with AbstractCollection,     // even if c.contains() throws.     if (r != size) {  System.arraycopy(elementData, r,     elementData, w,     size - r);  w += size - r;     }     if (w != size) {  // clear to let GC do its work  for (int i = w; i < size; i++)      elementData[i] = null;  modCount += size - w;  size = w;  modified = true;     } } return modified;    }

注意 complement 参数值为 false

1. 检查集合元素是否为空，为空则抛出异常
2. 遍历数组，如果集合中不包含当前元素(通过 complement 值来判断)，则将当前元素依次从 r 位置排列
3. 当 r != size 的时候说明 c.contains 可能出现了异常，做了一个兼容操作，此处不详细讲述
4. w表示移动后的集合的元素的长度，如果 w != size 则证明存在元素被修改，将 w 位置后面的元素全部设置为 null， 并将 size 设置为 w
5. 返回修改结果

retainAll(Collection c)

ArrayList 和 集合取交集

    public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true);    }

注意 complement 参数值为 true

步骤和上面 removeAll 方法实现逻辑一样，只是 complement 参数值不一样，通过 complement 参数来控制是保留包含的元素还是不包含的元素

writeObject & readObject

序列化使用，上面内容我们讲到为了保证性能和避免资源浪费，底层数组使用了 transient 关键字修复，导致无法使用 jvm 的序列化，通过 writeObject 和 readObject 方法实现了 ArrayList 的序列化和反序列化

    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. 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; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) {     // be like clone(), allocate array based upon size not capacity     int capacity = calculateCapacity(elementData, size);     SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);     ensureCapacityInternal(size);     Object[] a = elementData;     // Read in all elements in the proper order.     for (int i=0; i<size; i++) {  a[i] = s.readObject();     } }    }

总结

从上述源码中我们可以得出以下结论：

• ArrayList也是List 的一种
• ArrayList底层使用 Object 数组实现
  • ArrayList比较适合读多写少的情况(写需要挪动元素)
• ArrayList初始容量大小为10
• ArrayList每次扩容大小为原容量的 1.5 倍

书法艺术字体