JavaDS —— 顺序表ArrayList

'# JavaDS —— 顺序表ArrayList

一、背景与问题

在Java的集合框架中，ArrayList 是最基础且最常用的顺序表实现。它基于动态数组结构，支持随机访问，但插入和删除操作的时间复杂度较高。理解其底层原理对性能调优和数据结构选型至关重要。

在实际开发中，我们经常需要处理大量数据的存储和访问，例如：

• 管理用户会话信息
• 实现缓存池
• 构建任务队列
• 构造数据导出的结构

但如果不了解其内部机制，可能会遇到以下问题：

• 频繁扩容导致性能下降
• 遍历时修改集合引发 ConcurrentModificationException
• 内存泄漏风险
• 线程安全问题

二、基本原理

1. 动态数组的结构

ArrayList 使用一个 Object[] 数组存储元素，通过维护三个核心变量：

private transient Object[] elementData;
private int size;
private final int DEFAULT_CAPACITY = 10;

其中：

• elementData 是实际存储元素的数组
• size 表示当前元素个数
• DEFAULT_CAPACITY 是默认初始容量

2. 扩容机制

当元素数量超过当前容量时，会进行扩容。扩容策略是：

int newCapacity = (oldCapacity * 3)/2 + 1;

例如初始容量为10时，扩容后变为16，再扩容则为25，依此类推。这种策略在大部分场景下能保持较好的性能平衡。

3. 随机访问特性

由于数组的内存连续性，ArrayList 的随机访问时间复杂度为 O(1)：

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

三、环境准备

确保开发环境支持 Java 8+，代码示例使用标准 JDK：

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

public class ArrayListDemo {
    // 示例代码
}

四、核心实现

1. 基础操作实现

public class MyArrayList<E> {
    private Object[] elementData;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }
    
    public void add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
    
    public E get(int index) {
        rangeCheck(index);
        return (E) elementData[index];
    }
    
    private void rangeCheck(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    
    public int size() {
        return size;
    }
}

关键代码解释：

• ensureCapacityInternal 方法实现扩容逻辑，采用 oldCapacity + (oldCapacity >> 1) 的策略
• Arrays.copyOf 方法实现数组复制，这个过程需要 O(n) 时间
• rangeCheck 方法确保索引在合法范围内

2. 扩容性能分析

当向 ArrayList 中添加元素时，最坏情况下的时间复杂度为 O(n)（扩容时的数组复制）。但平均情况下，由于扩容策略，每个元素的平均移动次数是常数。

3. 遍历与修改

public void iterateAndModify() {
    MyArrayList<String> list = new MyArrayList<>();
    list.add("A");
    list.add("B");
    list.add("C");
    
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).equals("B")) {
            list.remove(i); // 会引发 ConcurrentModificationException
        }
    }
}

错误分析：

• 在遍历过程中修改集合会抛出 ConcurrentModificationException
• 原因是 ArrayList 使用 modCount 记录修改次数，遍历器会检查这个计数器

五、完整案例

1. 任务管理器实现

public class TaskManager {
    private MyArrayList<Task> tasks = new MyArrayList<>();
    
    public void addTask(Task task) {
        tasks.add(task);
    }
    
    public void removeTask(int index) {
        tasks.remove(index);
    }
    
    public void printTasks() {
        for (int i = 0; i < tasks.size(); i++) {
            System.out.println(tasks.get(i));
        }
    }
    
    public static void main(String[] args) {
        TaskManager manager = new TaskManager();
        manager.addTask(new Task("Task 1", "Description 1"));
        manager.addTask(new Task("Task 2", "Description 2"));
        
        manager.printTasks();
        manager.removeTask(0);
        manager.printTasks();
    }
}

案例说明：

• 使用 MyArrayList 管理任务列表
• 展示添加、删除和遍历操作
• 演示如何避免遍历修改的问题

2. 性能测试

public class PerformanceTest {
    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>();
        
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Add 1M elements: " + (endTime - startTime) + "ms");
        
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("Get 1M elements: " + (endTime - startTime) + "ms");
    }
}

测试结果分析：

• 插入操作的耗时主要集中在扩容阶段
• 随机访问性能稳定

六、源码解析

1. JDK 8 的 ArrayList 源码

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 1224463155212318919L;
    
    private transient Object[] elementData;
    private int size;
    
    public ArrayList() {
        this.elementData = new Object[10];
    }
    
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
    
    private void add(E e, Object[] elementData, int size) {
        if (size == elementData.length)
            elementData = grow();
        elementData[size] = e;
        size++;
    }
    
    private Object[] grow() {
        return Arrays.copyOf(elementData, 
            (elementData.length * 3 + 1) / 2);
    }
}

关键点：

• modCount 计数器用于检测结构修改
• grow() 方法实现扩容逻辑
• Arrays.copyOf 是核心的数组复制方法

七、进阶使用

1. 预分配容量

MyArrayList<String> list = new MyArrayList<>(1000);

提前指定容量可避免多次扩容，适用于已知数据量的场景。

2. 使用迭代器安全修改

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
    
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    if (s.equals("B")) {
        iterator.remove();
    }
}

3. 使用 subList 方法

List<String> subList = list.subList(0, 2);

创建子列表时需注意，对子列表的修改会直接影响原列表。

八、性能与工程实践

1. 性能优化策略

2. 异常处理

try {
    list.get(-1);
} catch (IndexOutOfBoundsException e) {
    System.err.println("Invalid index");
}

3. 线程安全

List<String> safeList = Collections.synchronizedList(new ArrayList<>());

4. 内存管理

避免内存泄漏的实践：

• 及时移除不再使用的对象
• 使用 clear() 方法而非 removeAll()（因为 clear() 会释放内存）
• 使用 trimToSize() 减少内存占用

九、常见问题与踩坑

1. 遍历修改导致的异常

错误代码：

for (String s : list) {
    if (s.equals("B")) {
        list.remove(s);
    }
}

解决办法：使用迭代器或复制列表

2. 扩容性能瓶颈

问题表现：频繁扩容导致程序卡顿

解决办法：预估数据量或使用 LinkedList

3. 索引越界异常

错误代码：

list.get(list.size());

解决办法：使用 size() 方法判断边界

4. 线程安全问题

错误代码：

// 多线程环境下的不安全操作
list.add("A");

解决办法：使用 CopyOnWriteArrayList 或加锁

十、最佳实践

1. 推荐场景

• 需要频繁随机访问的场景
• 元素数量已知且较大的场景
• 需要高性能的存储结构

2. 推荐方案

• 预分配容量
• 使用迭代器进行修改
• 避免频繁扩容
• 需要线程安全时使用 CopyOnWriteArrayList

3. 代码规范

• 避免在遍历时修改集合
• 使用 size() 方法判断边界
• 遇到频繁扩容时考虑使用 LinkedList

十一、总结

ArrayList 作为 Java 中最基础的顺序表结构，其核心特性在于动态数组的内存连续性和随机访问的高效性。通过理解其内部实现机制，我们可以更好地在实际开发中选择和使用这个数据结构。

在实际项目中，我们应该：

• 在需要随机访问时使用 ArrayList
• 在频繁插入删除时考虑 LinkedList
• 在多线程环境中使用线程安全的集合
• 避免在遍历时修改集合
• 合理预估数据量以减少扩容次数

通过深入理解 ArrayList 的实现原理，我们不仅能写出更高效的代码，还能更好地规避常见的开发陷阱，提升整体代码质量。