网站导航
> 技术文档 > ArrayList 面试知识点笔记

ArrayList 面试知识点笔记

网友: 技术文档 2025-07-30 21:29:59

ArrayList 底层实现原理

ArrayList 面试知识点笔记

ArrayList 是基于动态数组实现的线性数据结构，底层使用 Object[] 数组存储元素。

初始化机制

  • 默认构造函数创建的 ArrayList 初始容量为 0
  • 当第一次添加元素时，才会初始化容量为 10（DEFAULT_CAPACITY）
  • 使用 new ArrayList(capacity) 指定初始容量时，不会进行扩容

扩容机制（核心考点）

  • 扩容时机：当 size + 1 > 当前数组长度时触发扩容
  • 扩容倍数：每次扩容为原容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）
  • 扩容过程：调用 grow() 方法，使用 Arrays.copyOf() 创建新数组并拷贝原数据
  • 性能影响：频繁扩容会影响性能，建议预估容量大小

ArrayList vs LinkedList 核心区别

底层结构

  • ArrayList：基于动态数组，元素在内存中连续存储
  • LinkedList：基于双向链表，元素通过指针连接

时间复杂度对比

操作 ArrayList LinkedList 随机访问（get/set） O(1) O(n) 头部插入/删除 O(n) O(1) 尾部插入/删除 O(1)* O(1) 中间插入/删除 O(n) O(n)

*ArrayList 尾部插入在不扩容时为 O(1)，扩容时为 O(n)

使用场景选择

  • ArrayList 适用于：频繁随机访问、遍历操作多的场景
  • LinkedList 适用于：频繁在头部或中间插入删除的场景

重要面试考点

线程安全性

  • ArrayList 是非线程安全的
  • 多线程环境下可使用：
    • Collections.synchronizedList()
    • CopyOnWriteArrayList
    • 或使用 Vector（已过时）

内存占用

  • ArrayList 只需存储元素本身
  • LinkedList 需要额外存储前后节点指针，内存开销更大

迭代器

  • ArrayList 支持快速失败（fail-fast）的迭代器
  • 迭代过程中修改集合会抛出 ConcurrentModificationException

常见面试题答案要点

  1. 为什么 ArrayList 查找快，插入删除慢？

    • 基于数组，支持随机访问，查找时间复杂度 O(1)
    • 插入删除需要移动元素，时间复杂度 O(n)

  2. ArrayList 扩容为什么是 1.5 倍而不是 2 倍？

    • 1.5 倍可以更好地利用已释放的内存空间
    • 避免内存浪费，提高内存利用率

  3. 如何减少 ArrayList 扩容次数？

    • 预估集合大小，使用带容量参数的构造函数
    • 合理使用 ensureCapacity() 方法预分配容量

源码核心方法解析

add() 方法流程

// 核心步骤1. ensureCapacityInternal(size + 1) // 确保容量足够2. elementData[size++] = e  // 添加元素并更新size3. return true // 返回成功

remove() 方法实现

  • 按索引删除：System.arraycopy() 将后续元素前移
  • 按对象删除：先遍历找到元素，再调用 fastRemove()
  • 删除后将最后一个位置置为 null，便于 GC

扩容边界条件

  • 最大容量：Integer.MAX_VALUE - 8
  • 超大数组可能导致 OutOfMemoryError
  • 空数组和单元素数组的特殊处理

性能优化与最佳实践

批量操作优化

  • addAll() 比多次 add() 性能更好
  • removeAll() 和 retainAll() 使用位标记优化
  • clear() 只需遍历置null，不重新分配数组

内存泄漏防范

  • 及时清理不用的大型 ArrayList
  • 注意 subList() 持有原数组引用
  • 使用 trimToSize() 释放多余容量

序列化特性

  • ArrayList 实现了 Serializable 接口
  • elementData 使用 transient 修饰，自定义序列化逻辑
  • 只序列化有效元素，节省空间

JDK 版本演进差异

JDK 7 vs JDK 8+

  • JDK 7：创建时就分配默认容量 10
  • JDK 8+：延迟初始化，首次添加时才分配容量（懒加载）

新版本优化

  • 更精确的扩容计算，避免整数溢出
  • 优化了批量操作的性能
  • 改进了迭代器的实现

并发相关深入

fail-fast 机制原理

  • 使用 modCount 记录结构性修改次数
  • 迭代器创建时记录 expectedModCount
  • 每次迭代检查两者是否相等

线程安全替代方案对比

方案 适用场景 性能特点 Vector 简单同步需求 粗粒度锁，性能较差 Collections.synchronizedList() 包装现有List 方法级同步 CopyOnWriteArrayList 读多写少 写时复制，读无锁 ConcurrentLinkedQueue 高并发队列 无锁算法，性能最佳

实际开发陷阱

常见错误用法

// 错误：遍历时删除元素for(String s : list) { if(condition) list.remove(s); // ConcurrentModificationException}// 正确：使用迭代器删除Iterator<String> it = list.iterator();while(it.hasNext()) { if(condition) it.remove();}

性能陷阱

  • 频繁在头部插入元素（考虑使用 LinkedList 或 ArrayDeque）
  • 不预估容量导致频繁扩容
  • 使用 contains() 和 indexOf() 进行大量查找（考虑 HashSet）

边界问题

  • 索引越界检查：rangeCheck() 方法
  • null 元素的处理：ArrayList 允许 null 值
  • 空集合判断：使用 isEmpty() 而非 size() == 0

与其他集合的选择策略

场景化选择指南

  • 频繁随机访问：ArrayList
  • 频繁插入删除：LinkedList
  • 无重复元素：HashSet
  • 有序且无重复：TreeSet
  • 键值映射：HashMap
  • 线程安全需求：ConcurrentHashMap

性能基准参考

  • 10万元素随机访问：ArrayList > LinkedList (100:1)
  • 头部插入1万次：LinkedList > ArrayList (10:1)
  • 遍历操作：ArrayList ≈ LinkedList
  • 内存占用：ArrayList < LinkedList
网络标签：

相关问题