HashMap

S1-017必学进阶约 90 分钟JDK 21编程语言基础 · 集合

1. 本节定位

HashMap 是 Java 集合里最重要的一个实现类：日常开发中用得最多，面试里问得最狠，内部实现也最值得理解。

本节分两层：会用（怎么选 key、怎么避免踩坑）和懂原理（哈希、冲突、扩容）。第二层不是为了应付面试，而是因为 HashMap 的所有坑几乎都来自它的内部结构——key 为什么要求不可变、为什么遍历顺序会变、为什么并发下会出问题，答案都在原理里。

2. 学习目标

完成本节后，你应该能够：

用 put / get / getOrDefault / merge / computeIfAbsent 完成常见统计与缓存需求；
说出 HashMap 的底层结构（数组 + 链表 + 红黑树）与查找的平均复杂度；
解释为什么用自定义对象做 key 必须重写 equals 和 hashCode；
说出负载因子 0.75 与扩容对性能的影响；
解释为什么 HashMap 的遍历顺序不保证稳定。

3. 前置知识检查

知道 Map、List、Set 三者的差别吗？（《List、Set、Map》）
知道 equals 与 hashCode 的契约吗？（《equals、hashCode 与对象比较》）
能写一个 record 或普通类吗？（《类与对象》）

4. 为什么需要这个知识

假设要统计一段文本里每个单词出现的次数。

用 List 的思路：每遇到一个单词，就遍历列表找有没有记录过——数据量翻倍，耗时翻四倍。

用 HashMap：给定单词（key），直接算出它的存放位置，一步拿到计数。

text

List 查找：逐个比对        O(n)
HashMap 查找：算位置直达    O(1) 平均

当数据从 1000 条涨到 100 万条时，这个差别是"毫秒"和"分钟"的差别。

5. 核心概念

5.1 底层结构：数组 + 链表 + 红黑树

text

table 数组（默认长度 16）
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ …… │    │    │ 15 │
└─┬──┴────┴─┬──┴────┴────┴────┴────┴────┘
  │         │
  ▼         ▼
 Node     Node → Node → Node（冲突时挂成链表）
                    ↓ 链表长度 ≥ 8 且数组长度 ≥ 64 时
                 转为红黑树（查找从 O(n) 降到 O(log n)）

一个节点存四样东西：hash、key、value、next。

5.2 从 key 到数组下标

put(key, value) 做了三件事：

计算 hash = key.hashCode() 并做扰动（高低位异或，让哈希更分散）；
用 hash & (n - 1) 算出下标（n 是数组长度，等价于取模但更快，这也是数组长度必须是 2 的幂的原因）；
下标位置为空就直接放；不为空就比较 hash 与 equals，相同则覆盖 value，不同则挂到链表上。

哈希冲突指的是两个不同的 key 算出了同一个下标。这种情况无法避免（下标只有 16 个，key 可以有无数个），所以用链表/红黑树来解决。

5.3 扩容机制

默认初始容量 16，负载因子 0.75；
元素数量超过 容量 × 0.75（初始是 12）时，容量翻倍到 32，并把所有元素重新分布；
扩容要重建整个表，是 HashMap 最耗时的操作。知道大概要存多少数据时，直接指定初始容量：

java

// 预计存 1000 条，容量取 1000 / 0.75 ≈ 1334，向上取最近的 2 的幂 → 2048
Map<String, Integer> map = new HashMap<>(2048);

5.4 key 的要求：不可变 + 正确实现 equals/hashCode

这是 HashMap 最容易出错的地方。规则有两条：

equals 相等的两个对象，hashCode 必须相等（否则存进去就找不回来）；
key 放入后不能再变化（如果 key 的 hashCode 变了，它就永远躺在错误的桶里）。

所以实践中 key 常用 String、Integer、Long 或 record —— 它们都是不可变的，且已正确实现 equals / hashCode。

5.5 遍历顺序为什么不保证

因为元素的最终位置取决于：数组长度、哈希值、扩容历史。同样是 {a, b, c}，插入顺序一样，元素数量不同时顺序就可能不同。

结论：需要有序时用 TreeMap（按 key 排序）或 LinkedHashMap（按插入顺序），不要依赖 HashMap 的顺序。

6. 递进示例

6.1 最小示例：基本操作

java

Map<String, Integer> visits = new HashMap<>();
visits.put("首页", 120);
visits.put("订单页", 45);

// 不存在时返回默认值，而不是 null
int payPage = visits.getOrDefault("支付页", 0);

// 存在就累加，不存在就当 1——统计场景的标准写法
visits.merge("首页", 1, Integer::sum);

System.out.println(visits.get("首页"));   // 121
System.out.println(payPage);              // 0

6.2 业务示例：多级缓存与分组

java

// computeIfAbsent：key 不存在时才计算并放入，避免重复计算
Map<String, List<String>> cache = new HashMap<>();
cache.computeIfAbsent("java", key -> List.of("Java 教程 A", "Java 教程 B"));
cache.computeIfAbsent("java", key -> List.of("不会被使用"));
System.out.println(cache.get("java").size());   // 2

computeIfAbsent 的典型用途：把"主表 + 分组列表"这种结构一次写对，不用先 containsKey 再 put。

6.3 反例：不重写 equals / hashCode 的自定义 key

java

class BadKey {
    private final String id;
    BadKey(String id) { this.id = id; }
}

Map<BadKey, String> map = new HashMap<>();
map.put(new BadKey("A"), "值");
System.out.println(map.get(new BadKey("A")));   // null！

两次 new BadKey("A") 是两个不同对象：Object 默认的 hashCode 来自内存地址，默认的 equals 比较地址。于是存进去一个，拿另一个去找，永远找不到。

修复方案一（推荐）：用 record，它自动生成基于字段的 equals 与 hashCode。

java

record GoodKey(String id) {}

Map<GoodKey, String> map = new HashMap<>();
map.put(new GoodKey("A"), "值");
System.out.println(map.get(new GoodKey("A")));   // 值

修复方案二：手写 equals 与 hashCode，两个都不能漏。

7. 完整可运行代码

文件：labs/collections/src/main/java/cn/kb/learn/collection/HashMapLesson.javaJava 版本：21（javac --release 21）依赖：无 运行命令：

powershell

javac --release 21 -d out HashMapLesson.java
java -cp out cn.kb.learn.collection.HashMapLesson

java

package cn.kb.learn.collection;

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

public class HashMapLesson {
    record GoodKey(String id) {
    }

    /** 错误示范：故意不重写 equals/hashCode，字段不会被读取 */
    @SuppressWarnings("unused")
    static class BadKey {
        private final String id;

        BadKey(String id) {
            this.id = id;
        }
    }

    public static void main(String[] args) {
        // 1. 词频统计
        String text = "java is simple java is powerful";
        Map<String, Integer> counter = new HashMap<>();
        for (String word : text.split(" ")) {
            counter.merge(word, 1, Integer::sum);
        }
        System.out.println("词频统计：" + new java.util.TreeMap<>(counter));

        // 2. 自定义 key：错误示范
        Map<BadKey, String> badMap = new HashMap<>();
        badMap.put(new BadKey("A"), "值");
        System.out.println("未重写 equals/hashCode：" + badMap.get(new BadKey("A")));

        // 3. 自定义 key：record 正确示范
        Map<GoodKey, String> goodMap = new HashMap<>();
        goodMap.put(new GoodKey("A"), "值");
        System.out.println("使用 record：" + goodMap.get(new GoodKey("A")));

        // 4. computeIfAbsent 做分组
        Map<String, StringBuilder> groups = new HashMap<>();
        for (String channel : new String[]{"alipay", "wechat", "alipay"}) {
            groups.computeIfAbsent(channel, key -> new StringBuilder()).append("订单;");
        }
        System.out.println("分组结果：" + new java.util.TreeMap<>(groups));

        // 5. 指定初始容量，避免扩容
        Map<String, Integer> sized = new HashMap<>(2048);
        sized.put("预分配容量", 1);
        System.out.println("容量已预分配，元素数：" + sized.size());
    }
}

预期输出：

text

词频统计：{is=2, java=2, powerful=1, simple=1}
未重写 equals/hashCode：null
使用 record：值
分组结果：{alipay=订单;订单;, wechat=订单;}
容量已预分配，元素数：1

8. Debug 观察点

在 counter.merge(word, 1, Integer::sum); 打断点，展开 Variables 面板里的 counter；
继续展开 counter.table（IDEA 会显示为 Node[]），观察：
- table.length 一开始是 16；
- 每个非空下标里挂着一个 Node，Node 里有 hash、key、value、next；
- 当元素个数到第 13 个时（12 = 16 × 0.75），table.length 会变成 32——这就是扩容；
对比 badMap 与 goodMap：在 get 处断点，单步进入 HashMap.getNode，观察 hash 值是否一致。BadKey 两次 hash 不同，直接定位失败；GoodKey 两次 hash 相同，再用 equals 确认相等，命中。

第 2 步的扩容观察是本节的"名场面"，值得亲手试一次。

9. 常见错误

错误 1：用可变对象做 key

java

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "值");
key.add("b");                         // key 的 hashCode 变了
System.out.println(map.get(key));     // null：找不回来了

修复：key 只用不可变类型（String、Integer、record），或用集合时先 List.copyOf(...) 固定内容。

错误 2：遍历时修改 map

java

for (String key : map.keySet()) {
    if (key.startsWith("temp")) {
        map.remove(key);          // ConcurrentModificationException
    }
}

修复：用迭代器的 remove，或 Java 8+ 的 removeIf：

java

map.entrySet().removeIf(entry -> entry.getKey().startsWith("temp"));

错误 3：依赖遍历顺序

java

// 不要这样写
String first = map.keySet().iterator().next();

修复：需要顺序时改 LinkedHashMap（插入序）或 TreeMap（排序）；需要"第一个"时用 LinkedHashMap 并明确语义。

10. 动手实验

目标：亲手观察一次扩容与哈希冲突。

步骤：

运行第 7 节的代码，确认输出一致；
把 counter 的循环改成插入 20 个不同的 key，在第 13 个 put 处断点，记录 table.length 的变化；
构造两个不同字符串但哈希值相同（提示："Aa".hashCode() == "BB".hashCode()），把它们放进同一个 HashMap，观察是否挂成链表；
把 HashMap 换成 LinkedHashMap 与 TreeMap，比较三者输出的顺序差异。

验收方式：能解释第 2 步"为什么是第 13 个元素触发扩容"，第 3 步"哈希冲突时发生了什么"。

扩展任务：用 HashMap 实现一个"最近访问缓存"：容量上限 3，超出时淘汰最早访问的 key（提示：LinkedHashMap 的重写 removeEldestEntry，这是 S4 Redis 缓存的雏形）。

11. 练习题

基础题

判断：HashMap 的遍历顺序与插入顺序一致。（对 / 错）
填空：HashMap 默认初始容量是 ____，负载因子是 ____。
简答：为什么 HashMap 的数组长度必须是 2 的幂？

代码阅读题

java

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.merge("a", 10, Integer::sum);
map.computeIfAbsent("b", key -> 100);
map.computeIfAbsent("b", key -> 200);
System.out.println(map);

输出是什么？merge 与 computeIfAbsent 的区别是什么？

编程题

给定一个字符串数组，统计每个字符串出现的次数，并按出现次数从高到低输出（次数相同时按字典序）。

综合任务

实现一个 ScoreBoard 类：
- 用 Map<String, List<Integer>> 存每个学生的所有成绩；
- 方法 addScore(String student, int score)；
- 方法 average(String student) 返回平均分（无成绩返回 0）；
- 方法 top(int n) 返回平均分最高的前 n 名学生（用 Stream 或 TreeMap 皆可）；
- 说明你为什么选择当前的 key 类型。

分级提示

提示 1（方向）：第 5 题用 merge 统计，再用 stream().sorted(comparator) 排序后输出。

提示 2（关键点）：第 6 题用 computeIfAbsent(student, key -> new ArrayList<>()).add(score) 一行完成"有则取、无则建再取"。

提示 3（接近答案）：第 6 题的 top(n) 可以先把 entrySet 映射成 Map.Entry<String, Double>，再用 sorted(Comparator.comparingDouble(Map.Entry::getValue).reversed()) 截断。

12. 参考答案

基础题

错。HashMap 不保证任何顺序；需要插入序用 LinkedHashMap。
16、0.75。
因为计算下标用的是 hash & (n - 1)。只有当 n 是 2 的幂时，n - 1 的二进制才是全 1（如 16 - 1 = 1111），与操作才能均匀取到所有下标；否则会浪费部分下标、增加冲突。

代码阅读题（第 4 题）

输出 {a=11, b=100}。

merge(key, 值, 合并函数)：key 不存在时放入给定值，存在时用合并函数更新（1 + 10 = 11）；
computeIfAbsent(key, 计算函数)：只在 key 不存在时计算并放入，已存在则直接返回旧值、不再计算（所以第二次的 200 被忽略）。

编程题（第 5 题）

java

package cn.kb.learn.collection;

import java.util.*;
import java.util.stream.Collectors;

public class WordCount {
    public static void main(String[] args) {
        String[] words = {"java", "go", "java", "python", "go", "java"};

        Map<String, Integer> counter = new HashMap<>();
        for (String word : words) {
            counter.merge(word, 1, Integer::sum);
        }

        List<Map.Entry<String, Integer>> ranked = counter.entrySet().stream()
                .sorted(Comparator
                        .comparing(Map.Entry<String, Integer>::getValue, Comparator.reverseOrder())
                        .thenComparing(Map.Entry::getKey))
                .collect(Collectors.toList());

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

预期输出：

text

java = 3
go = 2
python = 1

综合任务（第 6 题）

java

package cn.kb.learn.collection;

import java.util.*;

public class ScoreBoard {
    private final Map<String, List<Integer>> scores = new HashMap<>();

    public void addScore(String student, int score) {
        scores.computeIfAbsent(student, key -> new ArrayList<>()).add(score);
    }

    public double average(String student) {
        List<Integer> list = scores.get(student);
        if (list == null || list.isEmpty()) {
            return 0;
        }
        int total = 0;
        for (int score : list) {
            total += score;
        }
        return (double) total / list.size();
    }

    public List<String> top(int n) {
        return scores.entrySet().stream()
                .sorted(Comparator.comparingDouble(
                        (Map.Entry<String, List<Integer>> entry) -> average(entry.getKey())).reversed())
                .limit(n)
                .map(Map.Entry::getKey)
                .toList();
    }

    public static void main(String[] args) {
        ScoreBoard board = new ScoreBoard();
        board.addScore("张三", 90);
        board.addScore("张三", 80);
        board.addScore("李四", 95);
        board.addScore("王五", 60);

        System.out.println("张三平均分：" + board.average("张三"));
        System.out.println("前两名：" + board.top(2));
    }
}

key 为什么用 String：学生姓名是不可变的 String，equals 与 hashCode 由 JDK 保证正确，放入后哈希值不会变化，不会出现"存进去找不回来"的问题。如果学生有唯一学号，用学号做 key 更严谨（同名问题）。

预期输出：

text

张三平均分：85.0
前两名：[李四, 张三]

13. 掌握标准

[ ] 能用 HashMap 完成统计、分组、缓存三类需求；
[ ] 能说出数组 + 链表 + 红黑树结构与 O(1) 平均查找的来源；
[ ] 能解释为什么自定义 key 必须重写 equals 与 hashCode；
[ ] 知道何时该指定初始容量，以及扩容的触发条件。

14. 扩展资源

HashMap 官方 API 文档：类注释里写清了结构与负载因子
JDK 源码 HashMap.java：putVal 与 resize 两个方法值得一读
《equals、hashCode 与对象比较》：契约的完整解释

15. 下一步学习

《HashSet、TreeSet 与集合排序》会把 Set 补齐——它同样建立在哈希表之上，理解了本节再学几乎没有额外成本。想对比 List 的两个实现，见《ArrayList 与 LinkedList》。

前置知识

S1-015 List、Set、Map

后续知识

暂无

进度只保存在本机浏览器，可随时清除

外部学习资源

面试题库索引

项目与练手索引

工具与软件索引

HashMap

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 底层结构：数组 + 链表 + 红黑树

5.2 从 key 到数组下标

5.3 扩容机制

5.4 key 的要求：不可变 + 正确实现 equals/hashCode

5.5 遍历顺序为什么不保证

6. 递进示例

6.1 最小示例：基本操作

6.2 业务示例：多级缓存与分组

6.3 反例：不重写 equals / hashCode 的自定义 key

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用可变对象做 key

错误 2：遍历时修改 map

错误 3：依赖遍历顺序

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习

前置知识

后续知识

HashMap ​

1. 本节定位 ​

2. 学习目标 ​

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

5. 核心概念 ​

5.1 底层结构：数组 + 链表 + 红黑树 ​

5.2 从 key 到数组下标 ​

5.3 扩容机制 ​

5.4 key 的要求：不可变 + 正确实现 equals/hashCode ​

5.5 遍历顺序为什么不保证 ​

6. 递进示例 ​

6.1 最小示例：基本操作 ​

6.2 业务示例：多级缓存与分组 ​

6.3 反例：不重写 equals / hashCode 的自定义 key ​

7. 完整可运行代码 ​

8. Debug 观察点 ​

9. 常见错误 ​

错误 1：用可变对象做 key ​

错误 2：遍历时修改 map ​

错误 3：依赖遍历顺序 ​

10. 动手实验 ​

11. 练习题 ​

12. 参考答案 ​

13. 掌握标准 ​

14. 扩展资源 ​

15. 下一步学习 ​

前置知识

后续知识

HashMap

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 底层结构：数组 + 链表 + 红黑树

5.2 从 key 到数组下标

5.3 扩容机制

5.4 key 的要求：不可变 + 正确实现 equals/hashCode

5.5 遍历顺序为什么不保证

6. 递进示例

6.1 最小示例：基本操作

6.2 业务示例：多级缓存与分组

6.3 反例：不重写 equals / hashCode 的自定义 key

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用可变对象做 key

错误 2：遍历时修改 map

错误 3：依赖遍历顺序

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习