容器高频面试题

List 族

Q1：ArrayList 和 LinkedList 的区别？什么时候选谁？

• 底层：动态数组（O(1) 随机访问，扩容 1.5 倍拷贝） vs 双向链表（头尾 O(1)，随机访问 O(n)）
• 选型：默认 ArrayList；头尾高频增删（队列/栈场景）用 ArrayDeque 而不是 LinkedList；LinkedList 的独特价值是"同时要 List 又要 Deque"的少数场景
• 反直觉点：LinkedList 中间插入并不快——定位是 O(n)，只有"已持有节点引用"时改指针才是 O(1)
• 详见 ArrayList / LinkedList

Q2：ArrayList 扩容机制？为什么是 1.5 倍？

• grow()：newCapacity = old + (old >> 1)；Arrays.copyOf 整体迁移
• 无参构造懒惰初始化：首次 add 才分配 10
• 1.5 倍是折中：2 倍浪费内存（Vector 的教训），太小扩容频繁；位运算 >>1 快
• 大数据量先 new ArrayList<>(预估容量) 免反复拷贝
• 详见 ArrayList 扩容机制节

Q3：什么是 fail-fast？怎么安全地遍历删除？

• modCount 结构修改计数器；迭代器发现不一致立即抛 ConcurrentModificationException
• 安全删除：迭代器自己的 it.remove()（同步更新 expectedModCount）；或 removeIf()
• 本质是"尽力而为"的 bug 探测器，不是并发保证——多线程该用并发容器
• 详见 ArrayList Fail-Fast 节

Q4：为什么不用 Vector？CopyOnWriteArrayList 好在哪？

• Vector 方法级 synchronized：读读也互斥，并发度被压到 1
• CopyOnWriteArrayList：读无锁；写复制新数组（写贵）——读多写极少场景碾压
• 详见 Vector "为什么现在基本不用"节

Set 族

Q5：Set 怎么保证元素唯一？

• HashSet：先 hashCode() 定桶，再 equals() 确认——两者必须一致重写（契约：equals 相等则 hashCode 必须相等）
• TreeSet：只看 compareTo()/compare() 返回 0——与 equals 不一致时会"存进 equals 不等的对象"
• 详见 00-Set总览 + Object 通用方法

Q6：HashSet、LinkedHashSet、TreeSet 怎么选？

• 默认 HashSet（最快）；要保插入序 LinkedHashSet（链表微开销）；要排序/范围查询 TreeSet（O(log n)，禁 null）
• LinkedHashSet 本质 = HashSet + 双向链表（底层 LinkedHashMap）
• 详见 00-Set总览

Queue 族

Q7：Queue 的 add/offer、remove/poll、element/peek 有什么区别？

• 两套风格：抛异常（add/remove/element） vs 返回特殊值（offer/poll/peek，队空返回 null/false）
• 日常推荐 offer/poll/peek——判返回值比抓异常自然
• 详见 00-Queue和Deque总览 两套方法表

Q8：为什么栈要用 ArrayDeque 而不是 Stack？

• Stack 继承 Vector：粗粒度锁 + "继承了 Vector 的 15 个方法"，语义污染（能从中间插）
• ArrayDeque：循环数组，头尾均摊 O(1)，无锁开销，官方 Javadoc 推荐替代
• 详见 ArrayDeque + 00-Queue和Deque总览 告诫块

Q9：PriorityQueue 的原理？Top K 怎么做？

• 二叉最小堆（数组存储）：offer 上浮 O(log n)、poll 下沉 O(log n)、peek O(1)
• Top K：维护大小为 K 的小顶堆，遍历比堆顶大就替换——O(n log K)
• 遍历它不是有序的（只是堆序）；要有序得逐个 poll
• 详见 PriorityQueue

Map 族（重灾区）

Q10：HashMap 的底层结构？JDK 8 做了什么优化？

• JDK 7：数组+链表；JDK 8：数组+链表+红黑树——链表长度 ≥8 且容量 ≥64 树化，退化阈值 6
• 为什么阈值 8：泊松分布下链表到 8 的概率约千万分之一，树化是兜底不是常态
• hash 扰动：高 16 位异或低 16 位，减少"高位差异被 (n-1)&hash 丢失"的碰撞
• 详见 HashMap / HashMap源码解析

Q11：HashMap 扩容流程？容量为什么是 2 的幂？

• 负载因子 0.75（时间/空间折中），超过阈值扩 2 倍
• JDK 8 优化：rehash 不重算 hash——新位置要么原下标，要么原下标+旧容量（看新增的那一位 hash 是 0 还是 1）
• 容量 2 的幂让 (n-1) & hash 等价取模且均匀
• 详见 HashMap源码解析 扩容节

Q12：HashMap 线程安全吗？会出什么问题？

• 不安全。JDK 7 头插法扩容并发时可成环死循环；JDK 8 改尾插解决了成环，但仍有数据覆盖丢失——不安全就是不安全
• 正解：ConcurrentHashMap（JDK 8 CAS+锁单桶）
• 详见 HashMap源码解析 线程安全节

Q13：HashMap 允许 null 键吗？为什么 Hashtable 不允许？

• HashMap 允许 1 个 null 键（固定放 0 号桶）+ 多个 null 值
• Hashtable/TreeMap 不允许 null 键：前者多线程下 get 返回 null 无法区分"不存在/值为 null"；后者 null 无法参与比较
• 详见 00-容器总览 Hashtable 节

Q14：LinkedHashMap 怎么实现 LRU？

• 构造传 accessOrder=true → 每次 get 把节点移到链尾；重写 removeEldestEntry() 让最老的（链头）自动淘汰
• 三行核心代码就是面试标准答案——不用手写双向链表
• 详见 LinkedHashMap

Q15：TreeMap/TreeSet 的排序依据是什么？和 equals 冲突会怎样？

• 只看 compareTo/compare 是否为 0；为 0 即视为"同一元素"
• 若比较逻辑与 equals 不一致：TreeMap 里会出现 equals 不等但存不进去的元素——"一致性问题"
• 详见 TreeMap + 红黑树

收尾三问（综合题）

Q16：HashMap、LinkedHashMap、TreeMap 三者怎么选？

• 默认 HashMap；要插入/访问序或 LRU → LinkedHashMap；要按键排序/范围查询 → TreeMap（代价 O(log n) + 禁 null 键）

Q17：自定义类做 HashMap 的 key 要注意什么？

• 必须同时重写 equals() 和 hashCode() 且逻辑一致；推荐用不可变类（String/Integer）做 key——key 可变会导致哈希漂移、再也取不回来

Q18：遍历 Map 有几种方式？哪种最好？

• entrySet（键值都要，一次遍历）/ keySet / values / forEach。键值都要时 entrySet 最优（keySet 再 get 是二次查找）；JDK 8 起 forEach 最简洁
• 详见 00-Map总览 上手示例节

⬅️ 00-容器选型总对比 🏠 00-Java ➡️ 00-Java并发总览