集合面试题：选对数据结构是基本功

集合是 Java 里最常用的 API 之一，也是面试必问。

很多人在准备面试时把各种集合的源码背了一遍，但真正被问到："我们系统里有个场景是高并发写入、随机读取，你觉得该用哪个？" 就答不上来了。

光背源码没用，得理解每个集合的设计意图和适用场景。

Java 集合框架全览

Collection
├── List（有序、可重复）
│   ├── ArrayList        → 数组实现，随机访问 O(1)
│   ├── LinkedList       → 链表实现，插入删除 O(1)
│   └── Vector           → 同步版 ArrayList（已被弃用）
└── Set（无序、去重）
    ├── HashSet          → 哈希表，O(1) 查找/插入
    ├── TreeSet          → 红黑树，有序
    └── LinkedHashSet    → 保留插入顺序的 HashSet

Map（键值对）
├── HashMap              → O(1) 查找/插入
├── TreeMap              → 红黑树，有序
├── LinkedHashMap        → 保留插入顺序
└── Hashtable            → 同步版 HashMap（已被弃用）

ArrayList vs LinkedList

对比	ArrayList	LinkedList
随机访问	O(1)	O(n)，需遍历
头部插入	O(n)，需移动后面所有元素	O(1)
中间插入	O(n)	O(1)，但需先遍历到位置
内存	连续，节省指针开销	分散，需要额外存储指针
CPU 缓存	友好，连续内存访问快	不友好

结论：90% 的场景用 ArrayList，只有在大量头插/尾删时才考虑 LinkedList。

HashMap 原理：必问

HashMap 的底层是数组 + 链表（JDK 8+ 红黑树）。

当发生哈希冲突时，冲突的元素以链表形式挂在数组的同一位置。当链表长度超过 8 时，转化为红黑树（O(log n) vs O(n)）。

核心参数：

参数	默认值	说明
capacity	16	数组大小，必须是 2 的幂次
loadFactor	0.75	负载因子，超过就扩容
threshold	12	触发扩容的阈值（capacity * loadFactor）

扩容机制：容量翻倍（16 → 32 → 64...），重新计算每个元素的索引位置。

ConcurrentHashMap：线程安全

HashMap 线程不安全，并发下会死循环（JDK 7 的扩容机制）。多线程环境用 ConcurrentHashMap：

// ❌ 线程不安全
Map<String, Integer> map = new HashMap<>();

// ✅ 线程安全
Map<String, Integer> safe1 = new ConcurrentHashMap<>();

// ✅ 也安全，但不推荐（全表锁）
Map<String, Integer> safe2 = Collections.synchronizedMap(new HashMap<>());

集合转换

List<String> list = Arrays.asList("a", "b", "c");

// List → Set（去重）
Set<String> set = new HashSet<>(list);

// List → Map
Map<String, Integer> map = list.stream()
    .collect(Collectors.toMap(s -> s, String::length));

// 过滤
List<String> filtered = list.stream()
    .filter(s -> s.length() > 1)
    .collect(Collectors.toList());

总结

选集合的核心：

• 随机访问多 → ArrayList
• 频繁插入删除 → LinkedList（仅限头尾）
• 键值对 → HashMap
• 多线程 → ConcurrentHashMap
• 需要排序 → TreeMap / TreeSet

没有最好的集合，只有最合适的。