第 27 章：集合框架进阶 — Set 与 Map

学习目标

• 掌握 Set 去重原理
• 掌握 HashMap 底层结构
• 理解 ConcurrentModificationException

一、Set 接口

Set：无序、不可重复。

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("A");      // ❌ 不会添加（重复）
System.out.println(set.size());  // 2

Set 实现类对比

实现	底层	有序	性能
HashSet	HashMap	❌	O(1)
LinkedHashSet	链表 + HashMap	✅ 插入序	O(1)
TreeSet	红黑树	✅ 排序	O(log n)

HashSet 去重原理

结论：HashSet 依赖 hashCode + equals。

二、Map 接口

Map：键值对集合。

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);          // ① 添加
map.put("banana", 2);
map.get("apple");             // ② 1（取值）
map.getOrDefault("orange", 0); // ③ 0（不存在返回默认值）
map.containsKey("apple");     // ④ true
map.containsValue(1);         // ⑤ true
map.remove("apple");          // ⑥ 删除
map.size();                   // ⑦ 元素数

Map 实现类对比

实现	底层	有序	线程安全
HashMap	数组+链表+红黑树	❌	❌
LinkedHashMap	链表 + HashMap	✅ 插入序	❌
TreeMap	红黑树	✅ 排序	❌
Hashtable	数组+链表	❌	✅
ConcurrentHashMap	分段锁 / CAS	❌	✅

HashMap 底层结构（JDK 8+）

特点：

• 数组 + 链表 + 红黑树
• 默认容量 16，负载因子 0.75
• 链表长度 ≥ 8 时转红黑树，红黑树节点 ≤ 6 时退化为链表
• 哈希冲突用链地址法解决

HashMap 的 put 流程

三、ConcurrentModificationException

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));

// ❌ 遍历时修改
for (Integer n : list) {
    if (n == 2) list.remove(n);   // ❌ ConcurrentModificationException
}

// ✅ 用迭代器
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 2) it.remove();  // ✅
}

四、Map 高级用法

Map<String, Integer> map = new HashMap<>(Map.of("A", 1, "B", 2, "C", 3));

// 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

map.forEach((k, v) -> System.out.println(k + " = " + v));

// 合并
map.merge("D", 4, Integer::sum);

// 计算（不存在时计算并放入）
map.computeIfAbsent("E", k -> 0);

五、本章小结

要点	关键
Set	不可重复，依赖 hashCode + equals
HashSet	默认，O(1)
TreeSet	排序，O(log n)
HashMap	数组+链表+红黑树
默认容量	16，负载因子 0.75
并发修改	用 Iterator.remove()

动手练习

练习 1：基础题

统计一段文本中每个单词出现的次数（用 HashMap）。

练习 2：进阶题

实现一个 LRU 缓存（继承 LinkedHashMap，重写 removeEldestEntry）。

---

下一章：第 28 章：泛型深入 →