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

标准答案

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

答案解析

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

优化查询性能的策略

1. 使用索引直接访问

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

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

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

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

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

   Set<Integer> set = new HashSet<>(list);
   if (set.contains(target)) { ... } // O(1) 查找
   

3. 使用 binarySearch() 进行有序查询
   如果 ArrayList 是有序的，可以使用 Collections.binarySearch() 进行 O(log n) 的二分查找：

   Collections.binarySearch(list, target);
   

优化批量插入的策略

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

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

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

2. 使用 addAll 进行批量插入

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

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

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

   list.ensureCapacity(5000);
   

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

深入追问

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

相关面试题

• 为什么 ArrayList 的 contains() 方法性能较低？
• ArrayList 的 subList() 方法有哪些坑？