【Java】Java集合：ArrayList源码分析

• Z时代
• 2024-01-10
• 分类：技术分享

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; // non-private to simplify nested class access
/**
* 实际数组的大小
*/
private int size;
/**
* 数组的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

 /**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 /**
* 将空数组初始化大小为10(将空数组初始化大小为10，具体在什么时候初始化大小为10，待会儿会说到)
*/
public ArrayList() {
// 将elementData元素数组初始化为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 /**
* 构造一个具有指定初始容量的列表
*
* @param  initialCapacity: 初始化数组的值
*/
public ArrayList(int initialCapacity) {
//如果初始化的值大于0，则给定elementData一个长度为initialCapacity的数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { // 如果初始化的值等于0，则初始化为空数组
this.elementData = EMPTY_ELEMENTDATA;
} else { //否则（小于0的情况）抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

 /**
* 构造一个指定元素的集合(此方法不太常用)
* @param c
*/
public ArrayList(Collection<? extends E> c) {
// 将集合转换为数组并赋值给elementData
elementData = c.toArray();
// 如果集合的大小不为0
if ((size = elementData.length) != 0) {
// 如果转换后的数组不是泛型(object)，则需要用Arrays的工具转换一下为object数组(这里不再对Arrays.copyOf展开论述)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // 否则初始化elementData为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}

 /**
* 在数组中增加一个元素
* @param e 元素对象
*/
public boolean add(E e) {
// 确定内部容量是否够用，size是元素数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。
ensureCapacityInternal(size + 1);
// 将元素e赋值到elementData末尾
elementData[size++] = e;
return true;
}
// 此方法可以理解为中转计算
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断数组是不是空数组, 如果是空数组(此时minCapacity = 0 + 1 = 1)，就将minCapacity初始化为10，但此时仅仅是返回要初始化数组的大小，并没有真正初始化数组为10
// private static final int DEFAULT_CAPACITY = 10;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Math.max(参数1，参数2)方法的意思是返回参数中最大的数，如果是空数组是，此时返回的是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果初始化的集合不是空，则返回元素数组的size + 1
return minCapacity;
}
// 别担心 我有奥妙全自动(奥妙洗衣粉～全国人民都知道～～)
private void ensureExplicitCapacity(int minCapacity) {
// 结构变化记录+1 在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList结构性变化的次数
modCount++;
// 判断数组是否够用，如果不够用，则自动扩容
// 1、当初始化的集合为空数组时，此时minCapacity是10，而elementData的长度为0，所以需要扩容
// 2、当初始化的集合不为空是，也就是给定了大小，或已经初始化了元素，此时的minCapacity = 实际数组个数+1，此时判断集合不够用，也需要进行扩容，否则元素会溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 自动扩容
private void grow(int minCapacity) {
// oldCapacity：元素数组的实际长度(即扩充前的数组大小)
int oldCapacity = elementData.length;
// oldCapacity 扩容1.5倍赋值给newCapacity( >>为右移运算符，相当于除以2 即oldCapacity/2 )
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果初始化为空的情况，则将数组扩容为10，此时才是真正初始化元素数组elementData大小为10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果1.5倍的数组大小超过了集合的最大长度，则调用hugeCapacity方法，重新计算，也就是给定最大的集合长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 已经确定了大小，就将元素copy到elementData元素数组中~~
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 内存溢出判断
if (minCapacity < 0)
throw new OutOfMemoryError();
// 这里的逻辑为：如果需要扩容的大小比数组的最大值都大，就返回Integer,MAX_VALUE(int最大值),否则返回集合的最大值(int最大值-8)
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

 /**
* 增加元素到指定下标
*
* @param index 下标
* @param element 元素
*/
public void add(int index, E element) {
// 参数校验
rangeCheckForAdd(index);
// 此方法不再赘述，参考上文Add方法重的论述
ensureCapacityInternal(size + 1);
// 请看下面代码块的注释
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将指定元素覆盖到指定下标
elementData[index] = element;
// 长度size + 1
size++;
}
/**
* 适用于add 和 addAll的校验方法
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 /**
* System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制
* 函数为：public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length)；
* @param      src      the source array. 源数组
* @param      srcPos   starting position in the source array. 源数组的起始位置
* @param      dest     the destination array. 目标数组
* @param      destPos  starting position in the destination data. 目标数组的起始位置
* @param      length   the number of array elements to be copied. 复制的长度
//举个例子
public static void main(String[] args){
int[] arr = {1,2,3,4,5};
int[] copied = new int[10];
System.out.println(Arrays.toString(copied));
System.arraycopy(arr, 0, copied, 1, 5);//5是复制的长度
System.out.println(Arrays.toString(copied));
}
输出结果为：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 0, 0, 0, 0] 

 public E remove(int index) {
// 参数校验
rangeCheck(index);
// 结构变化记录+1
modCount++;
// 获取旧数据，返回给开发人员，目的是让开发人员知道删除了哪个数据
E oldValue = elementData(index);
// 计算需要元素需要移动的次数
int numMoved = size - index - 1;
if (numMoved > 0)
// 同上文叙述
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一个元素置为空(元素前移，最后一位置为空)，让GC回收
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 /**
* 清空集合
*/
public void clear() {
modCount++;
// 将数组置为空，促使GC回收
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

 /**
* 检查给定的索引是否在范围内。 如果没有，则抛出一个适当的运行时异常。
* @param index : 下标
*/
public E get(int index) {
// 校验下标有效性
rangeCheck(index);
// 返回元素数组中指定index位置的数据
return elementData(index);
}
private void rangeCheck(int index) {
// 如果下标大于实际数组长度（元素数组最后一个数据下标为size-1）
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 /**
* 覆盖相应下标的数据
* @param index 下标
* @param element 元素数据
*/
public E set(int index, E element) {
// 校验方法(不再解释，与get方法中一样)
rangeCheck(index);
// 获取到旧数据，这里将旧数据返回出去，为了让开发者知道替换的是哪个值
E oldValue = elementData(index);
// 将指定下标覆盖为新元素
elementData[index] = element;
return oldValue;
}

其实我看到已有不少大佬写过此类文章，而且写的也比较清晰明了，那我为什么要再写一遍呢？其实也是为了加深自己的印象，巩固自己的基础

（主要是很多文章没有写出来我想知道的东西！！！​！！！！)

前言 

​自我洗脑中～我是大佬！我是大佬！我是大佬！（he~tui！我不配!!!）

正文

本次是基于JDK1.8来具体分析ArrayList源码

ArrayList的概念：

1、继承结构分析

我们先来看一下ArrayList类的继承结构：

​

Java支持单继承，多实现

AbstractList<E>：

List<E>：

RandomAccess：

Cloneable：

Serializable：

🤔🤔🤔🤔为什么AbstractList已经实现了List，ArrayList还要再实现一次呢？ 

• 其实ArrayList再去实现一次List在这里并没有什么实际意义，这其实是一个错误，因为作者写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。有兴趣的同学可以去研究一下。

2、类分析 

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; // non-private to simplify nested class access
/**
* 实际数组的大小
*/
private int size;
/**
* 数组的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

这里分析几个地方：

（1）为什么数组最大容量是Integer.MAX_VALUE - 8，而不是Integer.MAX_VALUE？

其实源码中给了备注：意思应该是有些虚拟机在数组中保留了一些头信息。避免内存溢出！

 /**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

（2）为什么定义了两个空数组？

（3）elementData为什么定义成transient？

3、构造方法

​

Array List总共有三个构造方法，下面我们一一分析

1）无参构造方法 ArrayList()

 /**
* 将空数组初始化大小为10(将空数组初始化大小为10，具体在什么时候初始化大小为10，待会儿会说到)
*/
public ArrayList() {
// 将elementData元素数组初始化为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

无参构造方法中，将元素数组elementData初始化为空数组。(注意：这里就体现了我上文说到的，为什么定义两个空数组)

2）有参构造方法 ArrayList(int)

 /**
* 构造一个具有指定初始容量的列表
*
* @param  initialCapacity: 初始化数组的值
*/
public ArrayList(int initialCapacity) {
//如果初始化的值大于0，则给定elementData一个长度为initialCapacity的数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { // 如果初始化的值等于0，则初始化为空数组
this.elementData = EMPTY_ELEMENTDATA;
} else { //否则（小于0的情况）抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

3）有参构造方法 ArrayList(Collection<? extends E> c)

 /**
* 构造一个指定元素的集合(此方法不太常用)
* @param c
*/
public ArrayList(Collection<? extends E> c) {
// 将集合转换为数组并赋值给elementData
elementData = c.toArray();
// 如果集合的大小不为0
if ((size = elementData.length) != 0) {
// 如果转换后的数组不是泛型(object)，则需要用Arrays的工具转换一下为object数组(这里不再对Arrays.copyOf展开论述)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // 否则初始化elementData为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}

对于当前构造方法，我举个例子，更清晰明了

​

4、常用方法源码分析

 /**
* 在数组中增加一个元素
* @param e 元素对象
*/
public boolean add(E e) {
// 确定内部容量是否够用，size是元素数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。
ensureCapacityInternal(size + 1);
// 将元素e赋值到elementData末尾
elementData[size++] = e;
return true;
}
// 此方法可以理解为中转计算
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断数组是不是空数组, 如果是空数组(此时minCapacity = 0 + 1 = 1)，就将minCapacity初始化为10，但此时仅仅是返回要初始化数组的大小，并没有真正初始化数组为10
// private static final int DEFAULT_CAPACITY = 10;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Math.max(参数1，参数2)方法的意思是返回参数中最大的数，如果是空数组是，此时返回的是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果初始化的集合不是空，则返回元素数组的size + 1
return minCapacity;
}
// 别担心 我有奥妙全自动(奥妙洗衣粉～全国人民都知道～～)
private void ensureExplicitCapacity(int minCapacity) {
// 结构变化记录+1 在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList结构性变化的次数
modCount++;
// 判断数组是否够用，如果不够用，则自动扩容
// 1、当初始化的集合为空数组时，此时minCapacity是10，而elementData的长度为0，所以需要扩容
// 2、当初始化的集合不为空是，也就是给定了大小，或已经初始化了元素，此时的minCapacity = 实际数组个数+1，此时判断集合不够用，也需要进行扩容，否则元素会溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 自动扩容
private void grow(int minCapacity) {
// oldCapacity：元素数组的实际长度(即扩充前的数组大小)
int oldCapacity = elementData.length;
// oldCapacity 扩容1.5倍赋值给newCapacity( >>为右移运算符，相当于除以2 即oldCapacity/2 )
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果初始化为空的情况，则将数组扩容为10，此时才是真正初始化元素数组elementData大小为10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果1.5倍的数组大小超过了集合的最大长度，则调用hugeCapacity方法，重新计算，也就是给定最大的集合长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 已经确定了大小，就将元素copy到elementData元素数组中~~
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 内存溢出判断
if (minCapacity < 0)
throw new OutOfMemoryError();
// 这里的逻辑为：如果需要扩容的大小比数组的最大值都大，就返回Integer,MAX_VALUE(int最大值),否则返回集合的最大值(int最大值-8)
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

 /**
* 增加元素到指定下标
*
* @param index 下标
* @param element 元素
*/
public void add(int index, E element) {
// 参数校验
rangeCheckForAdd(index);
// 此方法不再赘述，参考上文Add方法重的论述
ensureCapacityInternal(size + 1);
// 请看下面代码块的注释
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将指定元素覆盖到指定下标
elementData[index] = element;
// 长度size + 1
size++;
}
/**
* 适用于add 和 addAll的校验方法
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

System.arraycopy 方法解析

 /**
* System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制
* 函数为：public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length)；
* @param      src      the source array. 源数组
* @param      srcPos   starting position in the source array. 源数组的起始位置
* @param      dest     the destination array. 目标数组
* @param      destPos  starting position in the destination data. 目标数组的起始位置
* @param      length   the number of array elements to be copied. 复制的长度
//举个例子
public static void main(String[] args){
int[] arr = {1,2,3,4,5};
int[] copied = new int[10];
System.out.println(Arrays.toString(copied));
System.arraycopy(arr, 0, copied, 1, 5);//5是复制的长度
System.out.println(Arrays.toString(copied));
}
输出结果为：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 0, 0, 0, 0] 

 public E remove(int index) {
// 参数校验
rangeCheck(index);
// 结构变化记录+1
modCount++;
// 获取旧数据，返回给开发人员，目的是让开发人员知道删除了哪个数据
E oldValue = elementData(index);
// 计算需要元素需要移动的次数
int numMoved = size - index - 1;
if (numMoved > 0)
// 同上文叙述
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一个元素置为空(元素前移，最后一位置为空)，让GC回收
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 /**
* 清空集合
*/
public void clear() {
modCount++;
// 将数组置为空，促使GC回收
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

 /**
* 检查给定的索引是否在范围内。 如果没有，则抛出一个适当的运行时异常。
* @param index : 下标
*/
public E get(int index) {
// 校验下标有效性
rangeCheck(index);
// 返回元素数组中指定index位置的数据
return elementData(index);
}
private void rangeCheck(int index) {
// 如果下标大于实际数组长度（元素数组最后一个数据下标为size-1）
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 /**
* 覆盖相应下标的数据
* @param index 下标
* @param element 元素数据
*/
public E set(int index, E element) {
// 校验方法(不再解释，与get方法中一样)
rangeCheck(index);
// 获取到旧数据，这里将旧数据返回出去，为了让开发者知道替换的是哪个值
E oldValue = elementData(index);
// 将指定下标覆盖为新元素
elementData[index] = element;
return oldValue;
}

结尾

其实ArrayList中还有很多很多方法，这里就不在一一叙述了，因为你理解了本文中所说的源码，其实其它再去理解，再去查看，是比较容易简单的。

​

本篇文章就讲到这里，如果有写的不好的地方，请多多指教，我是善良的小黑哥，希望与大家共同进步！！

以上是 【Java】Java集合：ArrayList源码分析 的全部内容， 来源链接： utcz.com/a/106619.html