当前位置：首页 > news >正文

Java集合框架之ArrayList源码分析

news 2025/6/28 13:30:55

文章目录

- 简介
- ArrayList底层数据结构
- 初始化
- 集合操作
- - 追加元素
  - 插入数据
  - 删除数据
  - 修改数据
  - 查找
- 扩容操作
- 总结

简介

ArrayList是Java提供的线性集合，本篇笔记将从源码(java SE 17)的角度学习ArrayList：

什么是ArrayList？
ArrayList底层数据结构是怎么实现的？
作为一个容器，分析增删改查的过程
ArrayList的扩容机制

ArrayList底层数据结构

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{@java.io.Serialprivate static final long serialVersionUID = 8683452581122892189L;/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access/*** The size of the ArrayList (the number of elements it contains).** @serial*/private int size;...}

由ArrayList的定义可知，ArrayList继承了AbstractList抽象类，实现了List、RandomAccess、Cloneable、Serializable接口

通过这一行：

/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access

这就是ArrayList维护的底层数据结构，用于存放元素，是一个Object数组。还注意到使用了一个关键字：transient ，该关键字是在对ArrayList进行序列化时，禁止对该字段进行序列化。该字段是默认访问权限

初始化

    /*** Constructs an empty list with the specified initial capacity.** @param  initialCapacity  the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity*         is negative*/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);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}

ArrayList提供了三个构造器：

空的构造器

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

使用该构造器创建一个ArrayList时，统一使用默认的空的一个数组来初始化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);}
}

当使用一个整型变量初始化ArrayList时，根据initialCapacity的大小：- 小于0会抛出非法参数异常
- 等于0使用内部维护的EMPTY_ELEMENTDATA来创建
- 大于0，此时创建一个指定大小的Object数组

通过Collection来创建，主要用于从其他类型的集合创建ArrayList

集合操作

ArrayList源码中提供了一堆add函数，但是可以将添加元素的操作分为两类：

追加元素
插入元素

追加元素

在末尾追加数据调用的都是同一个方法

    private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;}

这里的elementData.length其实就是当前数组的容量，s这里传入的是size，也就是当前数组中实际元素的个数，首先会判断是否需要扩容,然后将数据追加到数组末尾。

插入数据

    public void add(int index, E element) {rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;size = s + 1;}

这里的操作也比较常规，就是将数组index后面的元素向后面一次迁移，然后将index的位置设置为指定元素

删除数据

    public E remove(int index) {Objects.checkIndex(index, size);final Object[] es = elementData;@SuppressWarnings("unchecked") E oldValue = (E) es[index];fastRemove(es, index);return oldValue;}private void fastRemove(Object[] es, int i) {modCount++;final int newSize;if ((newSize = size - 1) > i)System.arraycopy(es, i + 1, es, i, newSize - i);es[size = newSize] = null;}

逻辑也很简单，没啥说的，就是使用后面的数据覆盖掉index位置的数据

修改数据

    public E set(int index, E element) {Objects.checkIndex(index, size);E oldValue = elementData(index);elementData[index] = element;return oldValue;}

没什么说的

查找

E elementData(int index) {return (E) elementData[index];
}public E get(int index) {Objects.checkIndex(index, size);return elementData(index);
}

扩容操作

从上面有些方法的API中看到，如果向集合中添加元素时，此时会检查ArrayList的容量，如果容量不足会引发扩容，主要调用grow方法

    private Object[] grow() {return grow(size + 1);}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}

这里的preferred growth(参考增量)是原数组大小的一半，minGrowth是最小增量。

扩容可以分为四种情况：

如果原数组长度为0或者为默认的空数组对象

其实就是第一次向一个空的ArrayList添加元素，此时返回一个默认容量的数组, 默认容量为 10
如果根据计算得到的参考分配长度小于等于SOFT_MAX_ARRAY_LENGTH ,就返回该参考长度(这里我看网上很多文章说是扩容1.5倍，这其实是当最小增量小于原长度的一半时才发生的，所以并不准确，或者通过for循环依次追加时会发生，但是当批量添加时并不一定是1.5倍)

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength >= 0// assert minGrowth > 0int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflowif (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}}

如果参考长度(prefLength)大于SOFT_MAX_ARRAY_LENGTH , 如果实际需要的容量小于SOFT_MAX_ARRAY_LENGTH，就分配SOFT_MAX_ARRAY_LENGTH

    private static int hugeLength(int oldLength, int minGrowth) {int minLength = oldLength + minGrowth;if (minLength < 0) { // overflowthrow new OutOfMemoryError("Required array length " + oldLength + " + " + minGrowth + " is too large");} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}}