Java集合 - ArrayList

ArrayList 是 Java 集合框架中最常用的动态数组实现类，位于 java.util 包中。它基于数组实现，支持动态扩容和随机访问。

1. 特点

1. 动态数组：ArrayList 的底层是一个数组，可以根据需要动态扩展容量。

2. 有序：元素按照插入顺序存储，支持按索引访问。

3. 允许重复元素：可以存储重复的元素。

4. 允许 null 值：可以存储 null 值。

5. 非线程安全：ArrayList 不是线程安全的，多线程环境下需要额外同步。

6. 随机访问高效：基于数组实现，随机访问的时间复杂度为 O(1)。

2. 常用方法

2.1 添加元素

• add(E e)：在列表末尾添加元素。

• add(int index, E element)：在指定位置插入元素。

2.2 删除元素

• remove(int index)：删除指定位置的元素。

• remove(Object o)：删除第一个匹配的元素。

2.3 获取元素

• get(int index)：获取指定位置的元素。

2.4 修改元素

• set(int index, E element)：修改指定位置的元素。

2.5 查找元素

• contains(Object o)：判断是否包含指定元素。

• indexOf(Object o)：返回指定元素第一次出现的索引。

• lastIndexOf(Object o)：返回指定元素最后一次出现的索引。

2.6 其他常用方法

• size()：返回列表中的元素数量。

• isEmpty()：判断列表是否为空。

• clear()：清空列表中的所有元素。

• toArray()：将列表转换为数组。

底层实现

3.1 核心字段

ArrayList的核心字段为elementData和size

transient Object[] elementData; // 存储元素的数组
private int size; // 当前元素的数量

• elementData：是一个 Object 类型的数组，用于存储集合中的元素。

• size：表示当前 ArrayList 中实际存储的元素数量。

3.2 动态扩容

• 当数组容量不足时，ArrayList 会自动扩容。

• 扩容机制：

  1. 新容量通常是旧容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。

  2. 如果新容量仍然不足，则直接使用所需的最小容量。

  3. 扩容时需要创建新数组并复制元素，时间复杂度为 O(n)。

3.3 初始容量

• 默认初始容量为 10。

• 可以通过构造方法指定初始容量：

ArrayList<String> list = new ArrayList<>(100); // 初始容量为 100

线程安全

ArrayList 是 非线程安全 的。在多线程环境下，可能会出现以下问题：

• 数据不一致：多个线程同时修改 ArrayList 时，可能会导致数据丢失或错误。

• 并发修改异常：在使用迭代器遍历时，如果另一个线程修改了 ArrayList，可能会抛出 ConcurrentModificationException。

1. 使用Collections.synchronizedList：

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

2. 使用CopyOnWriteArrayList：

   List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>()

性能分析

• 随机访问(通过下标)：基于数组实现，随机访问的时间复杂度为 O(1)。

• 查找元素(未知下标): 时间复杂度O(n)，通过二分查找的时间复杂度O(logn)。

• 插入和删除：

  • 在末尾插入或删除元素的时间复杂度为 O(1)。

  • 在中间或开头插入或删除元素的时间复杂度为 O(n)，因为需要移动元素。

• 扩容：扩容的时间复杂度为 O(n)。

总结

• ArrayList 是基于动态数组实现的集合，支持随机访问和动态扩容。

• 默认初始容量为 10，扩容时容量增加为原来的 1.5 倍。

• 非线程安全，适合单线程环境使用。

• 在多线程环境下，可以使用 Collections.synchronizedList 或 CopyOnWriteArrayList 来保证线程安全。

• 适用于需要频繁访问元素但较少插入和删除的场景。