# 11. 如何提高ArrayList查询性能?批量插入数据时如何优化?

# 标准答案

ArrayList 查询性能的优化主要依赖于索引访问的 O(1) 复杂度,并尽量减少不必要的遍历。对于批量插入,可以通过预分配容量使用 addAll 批量方法来减少扩容开销,提高插入效率。

# 答案解析

ArrayList 是基于动态数组实现的,查询操作本质上是基于索引的随机访问,时间复杂度为 O(1),但如果查询逻辑涉及 contains()indexOf(),性能可能退化为 O(n),因为需要遍历整个数组。插入操作主要受扩容机制的影响,默认扩容系数为 1.5 倍,每次扩容都涉及数组拷贝,影响性能。

# 优化查询性能的策略

  1. 使用索引直接访问

    list.get(index); // O(1) 访问
    
    1

    相比 contains()indexOf(),索引访问的性能更优。

  2. 避免使用 contains() 进行查找

    list.contains(target); // O(n) 遍历查找
    
    1

    若查询较多,使用 HashSet 进行加速

    Set<Integer> set = new HashSet<>(list);
    if (set.contains(target)) { ... } // O(1) 查找
    
    1
    2
  3. 使用 binarySearch() 进行有序查询
    如果 ArrayList有序的,可以使用 Collections.binarySearch() 进行 O(log n) 的二分查找

    Collections.binarySearch(list, target);
    
    1

# 优化批量插入的策略

  1. 指定初始容量,减少扩容

    List<Integer> list = new ArrayList<>(1000); // 预估数据量,减少扩容
    
    1

    这样可以避免多次数组拷贝,提高性能。

  2. 使用 addAll 进行批量插入

    List<Integer> list = new ArrayList<>();
    list.addAll(Arrays.asList(1, 2, 3, 4, 5));
    
    1
    2

    相比单个 add(),批量插入性能更优。

  3. 使用 ensureCapacity() 预分配内存

    list.ensureCapacity(5000);
    
    1

    适用于动态增长的数据集合,可以提前分配内存,减少扩容开销。

# 深入追问

  • ArrayList 在并发环境下查询和插入是否安全?如何解决?
  • VectorCopyOnWriteArrayList 在查询性能上有什么不同?

# 相关面试题

  • 为什么 ArrayListcontains() 方法性能较低?
  • ArrayListsubList() 方法有哪些坑?