Java ArrayList 操作的底层逻辑
Java ArrayList 概述
在 Java 编程中，ArrayList 是一个非常常用的集合类，它实现了 List 接口，提供了动态数组的功能。与普通数组相比，ArrayList 可以动态地增加或减少其大小，更加灵活方便。ArrayList 位于 java.util 包下，在日常开发中被广泛应用于存储和操作一组相关的数据元素。
ArrayList 的基本使用
下面通过一个简单的代码示例来展示 ArrayList 的基本使用方法：
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
// 创建一个 ArrayList 对象
List<String> list = new ArrayList<>();
// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// 获取元素
String element = list.get(1);
System.out.println("获取的元素: " + element);
// 修改元素
list.set(2, "Date");
// 删除元素
list.remove(0);
// 遍历 ArrayList
for (String s : list) {
System.out.println(s);
}
}
}
在上述代码中，我们首先创建了一个 ArrayList 对象，并向其中添加了几个字符串元素。然后，我们获取、修改和删除了元素，并通过增强型 for 循环遍历了整个列表。这些操作是 ArrayList 最常见的使用场景。
ArrayList 的底层数据结构
ArrayList 的底层数据结构是一个动态数组。它使用一个数组来存储元素，并且当数组的容量不足时，会自动进行扩容操作，以适应更多元素的添加。
数组存储
在 ArrayList 类中，有一个 elementData 数组用于存储实际的元素。这个数组的类型是 Object[]，这意味着 ArrayList 可以存储任何类型的对象。
private transient Object[] elementData;
transient 关键字表示该字段不会被默认的序列化机制所序列化。这是因为 ArrayList 自定义了序列化和反序列化的过程，以提高性能和处理一些特殊情况。
容量和大小
ArrayList 有两个重要的属性：容量（capacity）和大小（size）。容量是指 elementData 数组当前能够容纳的元素数量，而大小是指 ArrayList 中实际存储的元素个数。
private int size;
size 变量记录了 ArrayList 中当前的元素数量。当我们添加元素时，size 会增加；当我们删除元素时，size 会减少。
扩容机制
当 ArrayList 中的元素数量达到其容量时，再添加新元素就需要进行扩容操作。扩容的过程涉及到创建一个更大的新数组，并将原数组中的所有元素复制到新数组中。
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);
}
在上述 grow 方法中，新的容量 newCapacity 是原容量 oldCapacity 的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。如果新容量仍然小于所需的最小容量 minCapacity，则将新容量设置为 minCapacity。如果新容量超过了 MAX_ARRAY_SIZE，则会调用 hugeCapacity 方法来确定最终的容量。最后，通过 Arrays.copyOf 方法将原数组的元素复制到新数组中。
ArrayList 的添加操作底层逻辑
添加单个元素
ArrayList 提供了 add(E e) 方法来向列表末尾添加一个元素。下面来看这个方法的实现：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先，ensureCapacityInternal 方法会检查当前 ArrayList 的容量是否足够。如果容量不足，会进行扩容操作。然后，将新元素 e 赋值给 elementData[size]，并将 size 加 1。
添加元素到指定位置
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++;
}
rangeCheckForAdd 方法用于检查插入位置 index 是否合法。如果 index 小于 0 或者大于 size，会抛出 IndexOutOfBoundsException 异常。然后，同样会检查容量并进行扩容。接着，通过 System.arraycopy 方法将从 index 位置开始的 size - index 个元素向后移动一位。最后，将新元素 element 插入到 index 位置，并将 size 加 1。
ArrayList 的获取操作底层逻辑
get(int index) 方法用于获取指定位置的元素。这个方法的实现比较简单：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private E elementData(int index) {
return (E) elementData[index];
}
首先，rangeCheck 方法会检查索引 index 是否合法。如果 index 小于 0 或者大于等于 size，会抛出 IndexOutOfBoundsException 异常。然后，通过 elementData(index) 方法直接返回 elementData 数组中指定位置的元素，并进行类型转换。
ArrayList 的修改操作底层逻辑
set(int index, E element) 方法用于替换指定位置的元素。其实现如下：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
同样，先通过 rangeCheck 方法检查索引是否合法。然后获取原位置的元素 oldValue，将新元素 element 赋值到指定位置，并返回原元素 oldValue。
ArrayList 的删除操作底层逻辑
删除指定位置的元素
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;
}
先通过 rangeCheck 方法检查索引是否合法。然后，获取要删除的元素 oldValue。计算需要向前移动的元素个数 numMoved，如果 numMoved 大于 0，则通过 System.arraycopy 方法将从 index + 1 位置开始的 numMoved 个元素向前移动一位。最后，将数组末尾的元素设置为 null，以便垃圾回收机制回收该对象，并将 size 减 1，返回被删除的元素 oldValue。
删除指定元素
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
}
该方法首先判断要删除的元素 o 是否为 null。如果为 null，则遍历数组，找到第一个值为 null 的元素，并调用 fastRemove 方法删除该元素。如果 o 不为 null，则遍历数组，通过 equals 方法找到第一个与 o 相等的元素，并调用 fastRemove 方法删除该元素。fastRemove 方法与 remove(int index) 方法中删除元素的核心逻辑相同。
ArrayList 的遍历操作底层逻辑
ArrayList 支持多种遍历方式，如普通 for 循环、增强型 for 循环和迭代器遍历。不同遍历方式的底层实现略有不同。
普通 for 循环遍历
List<String> list = new ArrayList<>();
// 添加元素
for (int i = 0; i < list.size(); i++) {
String element = list.get(i);
System.out.println(element);
}
普通 for 循环遍历是通过 get(int index) 方法依次获取每个位置的元素。这种方式在遍历过程中直接访问数组，效率较高，但需要注意索引的边界检查。
增强型 for 循环遍历
List<String> list = new ArrayList<>();
// 添加元素
for (String element : list) {
System.out.println(element);
}
增强型 for 循环实际上是基于迭代器实现的。在编译阶段，编译器会将增强型 for 循环转换为使用迭代器的形式。例如，上述代码在编译后类似于以下形式：
List<String> list = new ArrayList<>();
// 添加元素
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String element = it.next();
System.out.println(element);
}
迭代器遍历
ArrayList 实现了 Iterable 接口，因此可以使用迭代器进行遍历。
List<String> list = new ArrayList<>();
// 添加元素
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String element = it.next();
System.out.println(element);
}
iterator 方法返回一个实现了 Iterator 接口的迭代器对象。Iterator 接口提供了 hasNext 和 next 方法来遍历集合中的元素。在 ArrayList 中，迭代器的实现是一个内部类 Itr。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在 Itr 类中，cursor 表示下一个要返回的元素的索引，lastRet 表示上一个返回的元素的索引，expectedModCount 用于检测在迭代过程中 ArrayList 是否被修改。hasNext 方法判断是否还有下一个元素，next 方法返回下一个元素并更新 cursor 和 lastRet。remove 方法用于删除当前迭代到的元素，并更新相关状态。checkForComodification 方法在每次调用 next 或 remove 方法时检查 modCount 是否被修改，如果被修改则抛出 ConcurrentModificationException 异常，以防止在迭代过程中集合被意外修改。
ArrayList 的性能分析
添加操作性能
- 在列表末尾添加元素：平均时间复杂度为 O(1)。因为大多数情况下，只需要将元素添加到数组末尾，并更新
size变量。只有在容量不足需要扩容时，时间复杂度会变为 O(n)，但扩容操作并不频繁，因此平均下来接近 O(1)。 - 在指定位置添加元素：时间复杂度为 O(n)。因为需要将插入位置之后的所有元素向后移动一位。
获取操作性能
获取指定位置元素的时间复杂度为 O(1)。因为可以直接通过数组索引访问元素。
修改操作性能
修改指定位置元素的时间复杂度为 O(1)。因为直接通过数组索引进行赋值操作。
删除操作性能
- 删除指定位置元素：时间复杂度为 O(n)。因为需要将删除位置之后的所有元素向前移动一位。
- 删除指定元素：时间复杂度为 O(n)。首先需要遍历列表找到要删除的元素，平均时间复杂度为 O(n)，找到后删除元素同样需要移动元素，时间复杂度也为 O(n)。
遍历操作性能
- 普通 for 循环遍历：时间复杂度为 O(n)。直接通过索引访问数组，效率较高。
- 增强型 for 循环遍历：时间复杂度为 O(n)。虽然基于迭代器实现，但在正常情况下性能与普通
for循环相当。 - 迭代器遍历：时间复杂度为 O(n)。迭代器遍历在遍历过程中可以安全地删除元素，但由于涉及到方法调用等额外开销，性能略低于普通
for循环。
ArrayList 与其他集合类的比较
与 LinkedList 的比较
- 数据结构：
ArrayList底层是动态数组，LinkedList底层是双向链表。 - 随机访问性能：
ArrayList支持高效的随机访问，时间复杂度为 O(1)；而LinkedList随机访问性能较差，时间复杂度为 O(n)。 - 插入和删除性能：在列表中间插入和删除元素时，
LinkedList只需修改几个指针，时间复杂度为 O(1)；而ArrayList需要移动大量元素，时间复杂度为 O(n)。但在列表末尾插入和删除元素时，ArrayList平均时间复杂度接近 O(1)，而LinkedList虽然也是 O(1)，但由于链表节点的创建和销毁开销，性能可能稍逊一筹。 - 内存占用：
ArrayList内存占用相对紧凑，因为它是连续的数组；而LinkedList每个节点除了存储数据还需要存储两个指针，内存占用相对较大。
与 Vector 的比较
- 线程安全性：
Vector是线程安全的，它的大多数方法都使用synchronized关键字进行同步；而ArrayList是非线程安全的。在单线程环境下，ArrayList的性能更好。 - 扩容机制：
Vector默认扩容时新容量为原容量的 2 倍，而ArrayList扩容时新容量为原容量的 1.5 倍。
ArrayList 在实际项目中的应用场景
存储和管理数据列表
在很多应用中，需要存储和管理一组相关的数据，如用户信息列表、订单列表等。ArrayList 提供了方便的添加、获取、修改和删除操作，适合这种场景。例如，在一个电商系统中，可以使用 ArrayList 存储用户的购物车商品列表。
数据处理和分析
在数据处理和分析任务中，ArrayList 可以作为数据的临时存储结构。例如，从文件或数据库中读取数据后，可以先将数据存储在 ArrayList 中，然后进行各种数据处理操作，如过滤、排序、统计等。
与其他集合类或框架结合使用
ArrayList 可以与其他集合类或框架结合使用，以实现更复杂的功能。例如，在使用 Collections 工具类进行排序、查找等操作时，ArrayList 是常用的数据源之一。在 Spring 框架中，也经常使用 ArrayList 来存储配置信息或管理组件列表。
总结
通过深入了解 ArrayList 的底层逻辑，我们可以更好地在实际项目中使用它。在选择使用 ArrayList 时，需要根据具体的需求和性能要求来决定。如果需要频繁的随机访问，ArrayList 是一个很好的选择；如果需要频繁的插入和删除操作，尤其是在列表中间位置，可能需要考虑使用 LinkedList。同时，要注意 ArrayList 的线程安全性问题，在多线程环境下需要采取适当的同步措施。希望本文对您理解 ArrayList 的底层逻辑和应用有所帮助。