文章目录
- ArrayList 万字长文解析：使用、优化、源码分析
- 前言
- ArrayList 简介
- ArrayList 的基本使用方法
- ArrayList 性能优化
- ArrayList 的源码分析
- 内部结构
- 构造方法解析
- 扩容机制
- System.arraycop与 Arrays.copyof 实现方式 与 使用场景
- 迭代器
- JDK 8版本 ArrayList bug 示例
- ArrayList 使用注意事项代码演示
- ArrayList 与其他集合类的比较
- 结尾
ArrayList 万字长文解析：使用、优化、源码分析
前言
大家好，这里是 Rocky 编程日记 ，一位喜欢后端架构及中间件源码的CSDN博主，该篇文章主要是对 Java 集合框架体系下 ArrayList的一个解析 。
梳理出来也是想和大伙探讨一下这块内容，同时也供大家学习交流，如若笔记中有不对的地方，那一定是我的理解还不够，希望你大胆的在评论区指出来噢~。
同时，如果对于该笔记存在很多疑惑，也欢迎和我交流讨论，最后也感谢您的阅读，嘿嘿，期待你的点赞，关注，收藏噢~。
前人述备矣，我只是知识的搬运工，ArrayList 文中代码示例皆在开源代码仓库中，源代码仓库地址为: https://gitee.com/Rocky-BCRJ/java-diary.git。欢迎star~。
同时，本文只是对 ArrayList 核心方法的一些讲解，如果有一些相关方法未讲解到的，欢迎评论区留言讨论，后续我也会把 JDK 注释的开源代码同步出来，敬请期待~。
ArrayList 简介
ArrayList 是一种动态数组，可以在运行时自动扩展容量。它可以存储任何类型的对象，并提供高效的随机访问和快速的插入/删除操作。ArrayList 有以下优点：
- 高效的随机访问：ArrayList 内部使用数组实现，因此可以通过下标快速访问任意元素。
- 动态扩容：ArrayList 可以在运行时自动扩展容量，因此可以存储任意数量的元素。
- 可以存储任何类型的对象：ArrayList 可以存储任何类型的对象，包括基本类型和自定义类型。
- 支持插入/删除操作：ArrayList 内部使用数组实现，因此可以通过移动元素来实现插入和删除操作。
然而，ArrayList 也有一些缺点：
- 插入和删除操作可能会导致数组元素的移动，因此在大量插入和删除操作时，ArrayList 的性能可能会受到影响。
- ArrayList 内部使用数组实现，因此在插入和删除操作时，可能需要重新分配数组空间，这可能会导致性能下降。
- ArrayList 只能存储对象，不能存储基本类型，因此需要将基本类型包装成对象，这可能会导致一些额外的开销。
ArrayList 的基本使用方法
该段介绍 ArrayList 的基本操作，如添加、删除、遍历等。
package cn.rocky.other;
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListDemo {
public static void main(String[] args) {
// 创建 ArrayList 对象
ArrayList<String> list = new ArrayList<>();
// 添加元素
list.add("Java");
list.add("Python");
list.add("C++");
// 获取元素
System.out.println("第二个元素是：" + list.get(1));
// 修改元素
list.set(1, "JavaScript");
System.out.println("修改后的第二个元素是：" + list.get(1));
// 删除元素
list.remove(0);
System.out.println("删除后的第一个元素是：" + list.get(0));
System.out.println("for遍历元素：");
// for
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
System.out.println("for each 遍历元素：");
// for each 遍历元素
for (String s : list) {
System.out.print(s + " ");
}
System.out.println();
System.out.println("迭代器遍历元素：");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
System.out.print(element + " ");
}
}
}
ArrayList 性能优化
当使用 ArrayList 时，可以考虑以下性能优化技巧：
- 指定 ArrayList 的初始容量：在创建 ArrayList 时，可以指定其初始容量，这可以避免在添加元素时频繁地扩展数组。例如，如果预计 ArrayList 中将包含 100 个元素，可以使用以下代码创建 ArrayList：
ArrayList<String> list = new ArrayList<>(100);
- 使用 Iterator 迭代器遍历 ArrayList：使用 Iterator 迭代器遍历 ArrayList 可以避免使用 for 循环时频繁地调用 get() 方法。例如：
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
// do something with element
}
- 使用 for-each 循环遍历 ArrayList：使用 for-each 循环遍历 ArrayList 可以使代码更加简洁，也可以避免使用 for 循环时频繁地调用 get() 方法。例如：
for (String element : list) {
// do something with element
}
- 使用 toArray() 方法将 ArrayList 转换为数组：如果需要频繁地访问 ArrayList 中的元素，可以使用 toArray() 方法将 ArrayList 转换为数组，以提高访问速度。例如：
String[] array = list.toArray(new String[0]);
- 使用 subList() 方法获取子列表：如果需要对 ArrayList 中的部分元素进行操作，可以使用 subList() 方法获取子列表，以避免对整个 ArrayList 进行操作。例如：
List<String> subList = list.subList(0, 10);
// do something with subList
这些技巧可以帮助提高 ArrayList 的性能，但需要根据具体情况进行选择。在实际使用中，还需要考虑其他因素，比如数据量、操作频率等。
ArrayList 的源码分析
在这一部分中，我们将深入分析 ArrayList 的源码，以深入理解其实现原理和性能特点。我们将会讨论 ArrayList 的内部结构、扩容机制、迭代器实现等重要内容。
内部结构
- 数组元素：ArrayList 内部使用 Object 类型的数组来存储元素，可以通过数组下标来访问元素。
- 元素数量：ArrayList 中的元素数量，也就是当前数组中实际存储的元素数量。
- 容量大小：ArrayList 中数组的容量大小，也就是数组能够存储的最大元素数量。当元素数量超过容量大小时，ArrayList 会自动扩容。
- 修改次数：ArrayList 中记录修改次数的变量，用于在迭代器遍历时检测是否有其他线程对 ArrayList 进行修改。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 默认初始化容量 10
private static final int DEFAULT_CAPACITY = 10;
// 共享的空数组对象
private static final Object[] EMPTY_ELEMENTDATA = {};
// 共享的空数组对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 思考？ 这里为啥要加 transient。
// 存储 ArrayList 中元素的数组
transient Object[] elementData;
// 实际存储的元素数量
private int size;
// 父类的元素
// modCount 变量表示 ArrayList 的结构修改次数，
// 用于在迭代器遍历时检测是否发生了结构性修改，如果发生了则抛出 ConcurrentModificationException 异常
protected transient int modCount = 0;
}
构造方法解析
// 默认构造函数
public ArrayList() {
// 将 elementData 成员变量初始化为一个空数组，表示 ArrayList 的初始容量为 0。
// 当第一个元素被添加到 ArrayList 中时，elementData 数组会被扩容成默认容量 10。
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
// 初始化容量大于 0 时，创建 Object 数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
}
// 初始化容量等于 0 时，使用 EMPTY_ELEMENTDATA 对象
else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
}
// 初始化容量小于 0 时，抛出 IllegalArgumentException 异常
else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
// 将 集合 c 转换成 Object 数组。 思考？这里能用 elementData去接么 element = c.toArray();
Object[] a = c.toArray();
// 数组包含 元素时(length != 0)
if ((size = a.length) != 0) {
// 类型为 ArrayList,直接赋值
if (c.getClass() == ArrayList.class) {
elementData = a;
}
// 集合元素不是 Object[] 类型，则会创建 新的 Object[] 数组，并将 元素赋值到其中，最后赋值给 elementData。
else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
}
// 如果数组中不包含 元素时(length == 0),则使用 EMPTY_ELEMENTDATA 。
else {
elementData = EMPTY_ELEMENTDATA;
}
}
扩容机制
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
// 加元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 计算 calculate 得到的容量大小 ，判断是否需要进行扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量 1.当前数组 2.minCapacity = size + 1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果当前数组等于{}, 返回默认初始化大小 10;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回 size + 1;
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 修改次数 +1
modCount++;
// overflow-conscious code
// 需要的minCapacity容量大于数组元素长度，则需要进行扩容
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
}
// 扩容方法
private void grow(int minCapacity) {
// overflow-conscious code
// 意思是指在编写代码时考虑数据溢出的情况，避免因为数据溢出而导致程序出错或崩溃。
// 例如，在进行数值计算时，如果结果超出了数据类型的范围，就会发生数据溢出，此时就需要使用 overflow-conscious code 来避免这种情况。
// 旧数组容量大小,也即当前数组容量
int oldCapacity = elementData.length;
// 计算新数组容量，新数组容量 = 旧数组容量 + 1/2旧数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新数组容量小于最小容量，则将最小容量作为新的数组容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的数组容量超过了数组最大容量(Integer.Max - 8)，则调用 hugeCapacity 方法进入扩容
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);
}
// 计算扩容的最大容量, 在 Java 中，数组的最大长度是 Integer.MAX_VALUE, hugeCapacity 方法就能保证在扩容时，不会超过数组的最大长度限制。
private static int hugeCapacity(int minCapacity) {
// 传入的 minCapacity 小于 0，抛出 oom
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果 minCapacity 大于 MAX_ARRAY_SIZE，则返回 Integer.MAX_VALUE，否则返回 MAX_ARRAY_SIZE。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
System.arraycop与 Arrays.copyof 实现方式 与 使用场景
System.arraycopy() 和 Arrays.copyOf() 都可以用来复制一个数组，但是它们的实现方式和使用场景略有不同。
System.arraycopy() 是一个本地方法，它可以快速地将一个数组的一部分复制到另一个数组中的指定位置。它的语法如下：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
其中，src 是源数组，srcPos 是源数组中要复制的起始位置，dest 是目标数组，destPos 是目标数组中要复制到的起始位置，length 是要复制的元素数量。
Arrays.copyOf() 是一个静态方法，它可以将一个数组复制到一个新的数组中，并且可以指定新数组的长度。它的语法如下：
public static <T> T[] copyOf(T[] original, int newLength);
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
其中，original 是要复制的原始数组，newLength 是新数组的长度。
总的来说，System.arraycopy() 适用于需要高效复制数组的场景，而 Arrays.copyOf() 则更适用于需要创建一个新数组并且长度不确定的场景。另外，Arrays.copyOf() 还支持将原始数组的元素类型转换为另一种类型，而 System.arraycopy() 不支持。
迭代器
-
迭代器的作用：迭代器是一种用于遍历集合类中元素的工具，它可以让我们轻松地遍历 ArrayList 中的元素，而不需要使用传统的 for 循环或者 foreach 循环。
-
迭代器的使用方法：通过调用 ArrayList 的
iterator()方法可以获取一个迭代器对象，然后可以使用hasNext()方法和next()方法来遍历 ArrayList 中的元素。需要注意的是，在使用迭代器遍历元素时，不能直接使用 ArrayList 的get()方法获取元素。 -
迭代器的优点：相比传统的 for 循环或者 foreach 循环，使用迭代器遍历集合类中的元素有以下几个优点：
- 可以在遍历过程中删除元素，而不会出现
ConcurrentModificationException异常。 - 可以遍历所有实现了 Iterable 接口的集合类，而不需要关心具体的集合类型。
- 可以避免使用索引来访问元素，从而避免出现数组越界等异常。
- 可以在遍历过程中删除元素，而不会出现
-
迭代器的缺点：使用迭代器遍历集合类中的元素也有一些缺点：
- 不能在遍历过程中修改元素，否则会出现 ConcurrentModificationException 异常。
- 遍历过程中不能向集合中添加新的元素，否则会导致遍历不完整。
JDK 8版本 ArrayList bug 示例
public class TestList {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1, 2, 3);
Object[] array = list.toArray();
// JDK8 返回 Integer[] 数组，JDK9+ 返回 Object[] 数组。
System.out.println("class name : " + array.getClass().getSimpleName());
// JDK 8 和 JDK9+ 表现不同, 前者会报 ArrayStoreException 异常, 后者不会
array[0] = new Object();
}
}
ArrayList 使用注意事项代码演示
当使用 subList() 方法获取 ArrayList 的子列表时，返回的是一个新的列表对象，但是它与原来的列表对象共享同一个数据存储区域，也就是说，对子列表的修改会影响到原来的列表对象。如果在对子列表进行修改的同时，原来的列表对象也被修改了，就会导致 ConcurrentModificationException 异常的抛出。
package cn.rocky.other;
import java.util.ArrayList;
import java.util.List;
public class TestList04 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
List<String> subList = list.subList(0, 2);
list.add("D"); // 修改原列表
subList.clear(); // 修改子列表
// 此时会抛出 ConcurrentModificationException 异常
}
}
结果如下:
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1241)
at java.util.ArrayList$SubList.size(ArrayList.java:1050)
at java.util.AbstractList.clear(AbstractList.java:234)
at cn.rocky.other.TestList04.main(TestList04.java:18)
多线程环境下操作 ArrayList 也会出现一些其妙的问题，代码如下:
package cn.rocky.other;
import java.util.ArrayList;
public class TestList05 {
public static void main(String[] args) throws InterruptedException {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
list.add(i);
}
Thread thread1 = new Thread(() -> {
for (int i = 0; i < 500; i++) {
list.remove(i);
}
});
Thread thread2 = new Thread(() -> {
for (int i = 0; i < 500; i++) {
list.remove(i);
}
});
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println(list.size());
}
}
结果如下:
Exception in thread "Thread-1" Exception in thread "Thread-0" java.lang.IndexOutOfBoundsException: Index: 459, Size: 276
at java.util.ArrayList.rangeCheck(ArrayList.java:659)
at java.util.ArrayList.remove(ArrayList.java:498)
at cn.rocky.other.TestList05.lambda$main$1(TestList05.java:20)
at java.lang.Thread.run(Thread.java:750)
java.lang.IndexOutOfBoundsException: Index: 276, Size: 276
ArrayList 与其他集合类的比较
- ArrayList：底层是基于数组实现的，因此支持随机访问和快速的插入、删除操作，但是在插入、删除元素时可能需要移动其他元素，因此效率不如 LinkedList。ArrayList 还有一个优点是它的空间利用率高，因为它的容量是动态扩展的，而且可以通过设置初始容量来避免频繁扩容。
- LinkedList：底层是基于链表实现的，因此支持快速的插入、删除操作，但是随机访问效率较低，因为需要从头开始遍历链表。LinkedList 还有一个优点是它支持高效的队列和栈操作，因为可以在链表的头部和尾部进行插入、删除操作。
- Vector：与 ArrayList 类似，底层也是基于数组实现的，但是它是线程安全的，因此在多线程环境下使用更加安全，但是效率较低。Vector 还有一个缺点是它的扩容机制是翻倍扩容，因此在扩容时可能会浪费一些空间。
结尾
感谢您阅读本文，如果您有任何问题或建议，请在评论区留言，我将尽快回复您。如果你也有关于 ArrayList 使用的心得体会，欢迎评论区留言讨论。如果您觉得本文对您有所帮助，请点赞，评论，收藏，如果可以的话请分享给更多的人，让更多的人受益。
