第16课：集合框架 - Map

🎯 学习目标

理解 Map 的键值对结构
掌握 HashMap、LinkedHashMap、TreeMap 的使用
理解 HashMap 的底层原理（数组+链表+红黑树）
掌握 ConcurrentHashMap 线程安全
理解哈希冲突和扩容机制

📖 一、Map 接口概述

C vs Java Map

C 语言（需要手动实现）：

// 需要自己实现哈希表
struct HashMap {
    Entry** table;
    int capacity;
    int size;
};

Java（内置）：

java

// 开箱即用
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
int age = map.get("Alice");  // 25

Map 体系结构

Map (接口) - 键值对映射
├── HashMap - 最常用，无序
├── LinkedHashMap - 保持插入顺序
├── TreeMap - 按键排序
├── Hashtable - 线程安全（已过时）
└── ConcurrentHashMap - 线程安全（推荐）

📖 二、HashMap - 最常用的 Map

1. 基本使用

java

import java.util.HashMap;
import java.util.Map;

// 创建 HashMap
Map<String, Integer> map = new HashMap<>();

// 添加键值对
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Cherry", 30);

// 获取值
Integer appleCount = map.get("Apple");  // 10
Integer orangeCount = map.get("Orange");  // null（不存在）

// getOrDefault - 如果不存在返回默认值
int count = map.getOrDefault("Orange", 0);  // 0

// 判断是否包含
boolean hasApple = map.containsKey("Apple");  // true
boolean has50 = map.containsValue(50);  // false

// 删除
map.remove("Banana");

// 大小
int size = map.size();

// 清空
map.clear();

2. 遍历方式

java

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

// 方式1：遍历键
for (String key : map.keySet()) {
    Integer value = map.get(key);
    System.out.println(key + " = " + value);
}

// 方式2：遍历值
for (Integer value : map.values()) {
    System.out.println(value);
}

// 方式3：遍历键值对（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);
}

// 方式4：forEach + Lambda（Java 8+）
map.forEach((key, value) -> {
    System.out.println(key + " = " + value);
});

3. 常用方法

java

Map<String, Integer> map = new HashMap<>();

// putIfAbsent - 如果不存在才添加
map.putIfAbsent("A", 1);  // 添加成功
map.putIfAbsent("A", 2);  // 不添加（A已存在）

// replace - 替换值
map.replace("A", 10);  // 将A的值改为10
map.replace("A", 10, 20);  // 只有当前值是10时才改为20

// compute - 计算新值
map.compute("A", (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);

// computeIfAbsent - 如果不存在则计算
map.computeIfAbsent("B", key -> key.length());

// computeIfPresent - 如果存在则计算
map.computeIfPresent("A", (key, oldValue) -> oldValue * 2);

// merge - 合并值
map.merge("A", 5, (oldValue, newValue) -> oldValue + newValue);

4. HashMap 底层原理

JDK 1.7：数组 + 链表

HashMap 底层是 Entry[] 数组
每个元素是一个链表（解决哈希冲突）

[0] → null
[1] → Entry(key1, value1) → Entry(key2, value2) → null
[2] → Entry(key3, value3) → null
[3] → null
...

JDK 1.8+：数组 + 链表 + 红黑树

当链表长度 ≥ 8 时，转换为红黑树
提升查询性能：O(n) → O(log n)

[0] → null
[1] → Entry(key1, value1) → Entry(key2, value2) → ...（链表）
[2] → TreeNode（红黑树）
...

扩容机制：

java

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 当 size > capacity * loadFactor 时扩容
// 扩容为原来的 2 倍

哈希计算：

java

// 1. 计算 key 的 hashCode
int hash = key.hashCode();

// 2. 高低位异或（减少冲突）
hash = hash ^ (hash >>> 16);

// 3. 计算数组索引
int index = (capacity - 1) & hash;

📖 三、LinkedHashMap - 保持插入顺序

java

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

// 遍历顺序：C, A, B（插入顺序）
map.forEach((key, value) -> System.out.println(key));

// 内部：双向链表维护顺序
// HashMap 功能 + 链表顺序

应用场景：

LRU 缓存（Least Recently Used）
需要保持插入顺序的场景

📖 四、TreeMap - 按键排序

java

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

// 遍历顺序：A, B, C（按键排序）
map.forEach((key, value) -> System.out.println(key));

// 自定义排序
Map<String, Integer> map2 = new TreeMap<>(Comparator.reverseOrder());
map2.put("C", 3);
map2.put("A", 1);
map2.put("B", 2);
// 遍历顺序：C, B, A（降序）

// 内部：红黑树实现
// 时间复杂度：O(log n)

📖 五、ConcurrentHashMap - 线程安全

java

Map<String, Integer> map = new ConcurrentHashMap<>();

// 线程安全的操作
map.put("A", 1);
map.get("A");

// 原子操作
map.putIfAbsent("B", 2);
map.computeIfAbsent("C", key -> key.length());

// JDK 1.7：分段锁（Segment）
// JDK 1.8+：CAS + synchronized

📖 六、四种 Map 对比

特性	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
底层实现	数组+链表+红黑树	HashMap+链表	红黑树	数组+链表+红黑树
是否有序	无序	插入顺序	键排序	无序
允许null键	✅ 1个	✅ 1个	❌	❌
允许null值	✅ 多个	✅ 多个	✅ 多个	❌
线程安全	❌	❌	❌	✅
性能	最快	略慢	慢	快
使用场景	默认选择	保持顺序	需要排序	多线程

📖 七、实战应用

1. 统计词频

java

String text = "apple banana apple cherry banana apple";
String[] words = text.split(" ");

Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
    wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}

// 或使用 merge
for (String word : words) {
    wordCount.merge(word, 1, Integer::sum);
}

wordCount.forEach((word, count) -> 
    System.out.println(word + ": " + count));
// 输出：apple: 3, banana: 2, cherry: 1

2. 分组

java

List<Student> students = Arrays.asList(
    new Student("Alice", "Math"),
    new Student("Bob", "CS"),
    new Student("Charlie", "Math"),
    new Student("David", "CS")
);

Map<String, List<Student>> groupByMajor = new HashMap<>();
for (Student student : students) {
    groupByMajor.computeIfAbsent(student.getMajor(), k -> new ArrayList<>())
                .add(student);
}

// Math: [Alice, Charlie]
// CS: [Bob, David]

3. 缓存

java

public class Cache<K, V> {
    private final Map<K, V> cache = new HashMap<>();
    
    public V get(K key, Supplier<V> supplier) {
        return cache.computeIfAbsent(key, k -> supplier.get());
    }
}

// 使用
Cache<String, User> userCache = new Cache<>();
User user = userCache.get("user123", () -> database.findUser("user123"));

4. LRU 缓存

java

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // 超过容量时删除最老的
    }
}

// 使用
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("A", "1");
cache.put("B", "2");
cache.put("C", "3");
cache.get("A");  // A 最近访问
cache.put("D", "4");  // B 被淘汰（最久未使用）

⚠️ 常见陷阱

陷阱1：可变对象作为 key

如果 key 加入 Map 后修改了参与 hashCode 的字段，后续可能 get/remove 不到。

陷阱2：HashMap 并发写

HashMap 不是线程安全容器，多线程写可能导致数据错乱。并发场景使用 ConcurrentHashMap。

陷阱3：containsKey 和 put 不是原子操作

并发场景中 if (!map.containsKey(k)) map.put(k, v) 有竞态，应使用 putIfAbsent 或 computeIfAbsent。

陷阱4：误用 computeIfAbsent

computeIfAbsent 的 mapping 函数不应做长时间阻塞操作，也不应递归修改同一个 Map。

🆚 Java vs C 对比

特性	C	Java Map
哈希表	手写或第三方库	HashMap / ConcurrentHashMap
key 相等	手写比较函数	equals + hashCode
排序 Map	需要树结构库	TreeMap
并发 Map	手动加锁	ConcurrentHashMap

对 C 程序员来说，Map 的核心不是“键值对”本身，而是 key 的相等性和哈希规则。只要 key 规则错，整个 Map 的行为都会错。

💡 最佳实践

1. 指定初始容量

java

// ❌ 默认容量16，频繁扩容
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put("key" + i, i);
}

// ✅ 指定初始容量，减少扩容
int expectedSize = 10000;
int capacity = (int) (expectedSize / 0.75f) + 1;
Map<String, Integer> map = new HashMap<>(capacity);

2. 使用 computeIfAbsent

java

// ❌ 繁琐
if (!map.containsKey(key)) {
    map.put(key, new ArrayList<>());
}
map.get(key).add(value);

// ✅ 简洁
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

3. 避免在遍历时修改

java

// ❌ 抛 ConcurrentModificationException
for (String key : map.keySet()) {
    if (某条件) {
        map.remove(key);  // 错误
    }
}

// ✅ 使用迭代器
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    if (某条件) {
        iterator.remove();  // 正确
    }
}

// ✅ 或使用 removeIf（Java 8+）
map.entrySet().removeIf(entry -> 某条件);

4. 重写 equals 和 hashCode

java

// 作为 Map 的 key，必须重写这两个方法
public class Person {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

📝 练习

完成 练习/Ex16_Map.java：

HashMap 基本操作
词频统计
分组操作
LRU 缓存实现
TreeMap 排序
综合：学生成绩管理系统

🎓 下一步

第17课：集合框架 - Queue - PriorityQueue、Deque、BlockingQueue

第16课：集合框架 - Map ​

🎯 学习目标 ​

📖 一、Map 接口概述 ​

C vs Java Map ​

Map 体系结构 ​

📖 二、HashMap - 最常用的 Map ​

1. 基本使用 ​

2. 遍历方式 ​

3. 常用方法 ​

4. HashMap 底层原理 ​

📖 三、LinkedHashMap - 保持插入顺序 ​

📖 四、TreeMap - 按键排序 ​

📖 五、ConcurrentHashMap - 线程安全 ​

📖 六、四种 Map 对比 ​

📖 七、实战应用 ​

1. 统计词频 ​

2. 分组 ​

3. 缓存 ​

4. LRU 缓存 ​

⚠️ 常见陷阱 ​

陷阱1：可变对象作为 key ​

陷阱2：HashMap 并发写 ​

陷阱3：containsKey 和 put 不是原子操作 ​

陷阱4：误用 computeIfAbsent ​

🆚 Java vs C 对比 ​

💡 最佳实践 ​

1. 指定初始容量 ​

2. 使用 computeIfAbsent ​

3. 避免在遍历时修改 ​

4. 重写 equals 和 hashCode ​

📝 练习 ​

🎓 下一步 ​

第16课：集合框架 - Map

🎯 学习目标

📖 一、Map 接口概述

C vs Java Map

Map 体系结构

📖 二、HashMap - 最常用的 Map

1. 基本使用

2. 遍历方式

3. 常用方法

4. HashMap 底层原理

📖 三、LinkedHashMap - 保持插入顺序

📖 四、TreeMap - 按键排序

📖 五、ConcurrentHashMap - 线程安全

📖 六、四种 Map 对比

📖 七、实战应用

1. 统计词频

2. 分组

3. 缓存

4. LRU 缓存

⚠️ 常见陷阱

陷阱1：可变对象作为 key

陷阱2：HashMap 并发写

陷阱3：containsKey 和 put 不是原子操作

陷阱4：误用 computeIfAbsent

🆚 Java vs C 对比

💡 最佳实践

1. 指定初始容量

2. 使用 computeIfAbsent

3. 避免在遍历时修改

4. 重写 equals 和 hashCode

📝 练习

🎓 下一步