10.3 Map 与 Set 详解

读完集合入门和 List 后，再用约 45 分钟跑完这里的 Java 17 示例。目标不是记住一张实现表，而是能设计稳定的 key，并按相等性、顺序、范围与并发要求选择 Map 或 Set。

用 Map 表达“名称 → 数量”

若把名称和数量放进两个独立 List，它们的关系只靠相同下标维持。Map 直接把这层关系写成 名称 -> 数量；Set 则表达某个值是否已经登记，去重结果由元素的相等性规则决定。

1. Map 的基础读取与更新

java

Map<String, Integer> stock = new HashMap<>();
stock.put("零件", 50);
stock.put("木材", 30);

Integer component = stock.get("零件");
boolean hasLeather = stock.containsKey("皮革");
int missing = stock.getOrDefault("缺失项", 0);

put 返回旧值，键原先不存在时返回 null。remove(key) 也返回旧值。若 Map 允许 null value，单看 get 返回 null 无法区分“没有这个 key”和“key 存在但 value 为 null”：

java

Map<String, Integer> stockWithUnknown = new HashMap<>();
stockWithUnknown.put("待确认", null);

stockWithUnknown.get("待确认");         // null
stockWithUnknown.containsKey("待确认"); // true

getOrDefault 只为不存在的键使用默认值；已有的 null 映射仍返回 null，直接拆箱为 int 会抛 NullPointerException。是否允许 null 由具体实现决定。HashMap 允许一个 null key 和多个 null value；ConcurrentHashMap 不允许 null key/value；自然排序的 TreeMap 不接受无法比较的 null key。

复合更新

java

stock.merge("零件", -2, Integer::sum);
stock.computeIfAbsent("皮革", key -> 0);

merge 在 key 缺失或旧值为 null 时使用给定值，否则调用合并函数。合并函数返回 null 会删除映射。computeIfAbsent 只在缺失或映射为 null 时计算；映射函数返回 null 时不会新增。

这些方法能把“读取旧值再写新值”表达成一个 Map 操作。普通 HashMap 仍不支持并发写；ConcurrentHashMap 对相应复合方法提供并发语义，计算函数应短小，而且不应在其中再次更新这个 Map 的任何映射；不同实现对违规修改的检测方式不同。示例的 Integer::sum 也不会检查溢出或库存是否变负，领域约束仍需显式实现。

2. HashMap 的查找模型

HashMap 的大致流程是：

取得 key 的 hashCode 并做内部扰动；
用哈希定位桶；
在桶内比较保存的 hash 与 equals；
找到相等 key 就读取或更新 value；没找到时，get 返回 null，put 才会新增节点。

可靠且分布合理的哈希下，get、put、remove 提供期望 O(1) 性能。冲突、恶意 key、昂贵的 equals 和扩容都会改变单次成本。Java 8+ 的实现可在冲突严重且表够大时把桶转成树，但阈值、容量取整与内部节点结构属于 JDK 实现细节，不是 Map 接口保证。

构造器的 initial capacity 是内部表容量提示，不是“可无扩容存放的 entry 数”。默认负载因子 0.75 也是 HashMap 实现的默认值。已知最多 n 条记录时，应按负载因子估计所需桶容量，而不是直接把 n 当作容量；Java 17 的 HashMap 文档给出了容量大于“最大条目数 / 负载因子”时避免 rehash 的条件。同时别把容量开得过大：完整迭代成本与容量加条目数成正比。

HashMap 不保证迭代顺序。需要插入遭遇顺序用 LinkedHashMap；需要 key 排序、邻近键或范围视图用 TreeMap/NavigableMap。

3. equals 与 hashCode 契约

HashMap 和 HashSet 先用 hash 缩小候选范围，再用 equals 确认相等。key/元素必须遵守：

equals 自反、对称、传递，并在参与比较的信息不变时保持一致；
x.equals(y) 为 true 时，x.hashCode() == y.hashCode()；
hash 相同不代表 equals 相等，冲突是合法情况；
参与 equals/hashCode 的信息在作为 hash key 期间应保持稳定。

record 很适合简单值 key，但组件也要有正确语义。数组组件沿用数组身份相等，不会自动按元素比较；可变 List 组件还可能在插入后改变 hash。

java

record MaterialKey(String tenantId, String materialCode) {
    MaterialKey {
        Objects.requireNonNull(tenantId, "tenantId");
        Objects.requireNonNull(materialCode, "materialCode");
    }
}

手写普通类时，equals 与 hashCode 使用同一组稳定字段。IDE 可以生成骨架，但领域仍要决定“哪些字段定义同一个对象”，工具无法替你做这个判断。

4. 可变 key 为什么失联

下面沿用完整示例中的 MutableParticipant，它把 id 和 age 都计入 equals/hashCode。

java

MutableParticipant participant = new MutableParticipant("P-1", 25);
Map<MutableParticipant, String> roles = new HashMap<>();
roles.put(participant, "会计");

participant.age = 26;
System.out.println(roles.get(participant)); // null

对象仍在原节点里，但查询会重新计算 hash。新 hash 可能指向其他桶；即使桶号碰巧相同，新 hash 仍可能与节点保存的旧 hash 不符，导致根本不会进行对象身份或 equals 比较。不是每次修改都会失联，但查找契约已经被破坏。更稳的设计是只用不可变业务标识做 key，把年龄等可变属性放在 value 中。

“不用任何可变对象做 key”也过于绝对。对象可以有可变字段，只要 key 的 equality/hash 信息在驻留期间保持稳定；不过不可变值类型更容易证明这一点。

5. Set 的重复与顺序由实现决定

实现	相等/重复规则	迭代顺序	单次查找/增删成本
`HashSet`	`hashCode` + `equals`	未指定	期望 O(1)
`LinkedHashSet`	`hashCode` + `equals`	插入遭遇顺序	期望 O(1)
`TreeSet`	`compareTo` 或 Comparator 为 0	排序顺序	O(log n)

TreeSet 有另一种“相同”：比较器返回 0，就视为重复，即使 equals 为 false。

java

Set<String> byLengthOnly = new TreeSet<>(
        Comparator.comparingInt(String::length));

System.out.println(byLengthOnly.add("木材")); // true
System.out.println(byLengthOnly.add("皮革")); // false，同长度

若要同长度字符串都保留，追加稳定的比较条件：

java

Comparator<String> byLengthThenText =
        Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder());

要满足 Set/Map 的通用契约，排序比较结果必须与 equals 一致。仅按长度比较会让不同字符串视为同一个元素，虽然 TreeSet 仍按比较器工作，却违反了通常按 equals 理解的 Set 契约。插入后也不要修改参与排序的字段；树不会自动把节点搬到新位置。

6. TreeMap 与 NavigableMap 的范围视图

java

NavigableMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);

NavigableMap<String, Integer> range =
        scores.subMap("B", true, "D", false);

range 是背靠原 TreeMap 的视图，不是副本。通过 range 修改范围内键会反映到 scores；插入范围外键会抛 IllegalArgumentException。

NavigableMap 还提供 lowerKey、floorKey、ceilingKey、higherKey、firstEntry、lastEntry。这些操作表达邻近与范围需求，HashMap 没有对应契约。

7. 遍历 Map

java

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

stock.forEach((material, count) ->
        System.out.println(material + " -> " + count));

同时需要 key/value 时用 entrySet。只要 key 用 keySet，只要 value 用 values。不要把“entrySet 永远更快”当口诀；选择能表达所需数据的视图，热点路径再测量。

迭代 HashMap/HashSet 时不要断言顺序。需要稳定输出可复制到 TreeMap、排序 entry，或从一开始选择 LinkedHash/Tree 实现。

8. 并发写入要选并发语义

假设多个工作线程同时修改一个 HashMap。HashMap 的并发结构修改没有安全保证，可能丢更新、读到不一致结果或触发其他错误。不要把风险限制成某个历史 JDK 的“死循环”故事。

计数可用 ConcurrentHashMap 的原子复合方法；原子性不会消除 Integer 的溢出上限：

java

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
counts.merge("零件", 1, Integer::sum);

如果需要多键一起满足一个不变量，单次 merge 仍不够；要重新设计状态边界，或使用覆盖整个复合事务的锁。并发容器解决其文档声明的操作，不会自动把任意业务流程变成原子操作。

9. 完整可运行示例

先准备临时目录：

bash

chapter10_map_root=$(mktemp -d)
readonly chapter10_map_root
mkdir -p "$chapter10_map_root/out"
cd "$chapter10_map_root"

保存为 MapSetContractsDemo.java。这里顺序调用 ConcurrentHashMap，检查它的 API 结果；不把这两次调用当作并发压力测试。

java

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Objects;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;

public class MapSetContractsDemo {
    public static void main(String[] args) {
        Map<String, Integer> stock = new LinkedHashMap<>();
        stock.put("零件", 50);
        stock.put("木材", 30);
        stock.merge("零件", -2, Integer::sum);
        stock.computeIfAbsent("皮革", key -> 20);
        checkEquals(48, stock.get("零件"));

        Map<String, Integer> nullable = new HashMap<>();
        nullable.put("待确认", null);
        check(nullable.get("待确认") == null, "value 应为 null");
        check(nullable.containsKey("待确认"), "key 应存在");
        check(!nullable.containsKey("缺失项"), "缺失项 key 不应存在");

        MutableParticipant mutable = new MutableParticipant("P-1", 25);
        Map<MutableParticipant, String> roles = new HashMap<>();
        roles.put(mutable, "会计");
        mutable.age = 26;
        check(roles.get(mutable) == null, "修改 hash 字段后应失联");
        checkEquals(1, roles.size());

        Set<String> encounterOrder = new LinkedHashSet<>(
                List.of("零件", "木材", "零件", "皮革"));
        checkEquals(List.of("零件", "木材", "皮革"),
                List.copyOf(encounterOrder));

        Set<String> byLengthOnly = new TreeSet<>(
                Comparator.comparingInt(String::length));
        check(byLengthOnly.add("木材"), "首次添加应成功");
        check(!byLengthOnly.add("皮革"), "同长度比较为 0，应视为重复");

        NavigableMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        NavigableMap<String, Integer> range =
                scores.subMap("B", true, "D", false);
        range.put("Bob", 88);
        checkEquals(88, scores.get("Bob"));
        expect(IllegalArgumentException.class,
                () -> range.put("Aaron", 99));

        ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
        counts.merge("零件", 1, Integer::sum);
        counts.merge("零件", 1, Integer::sum);
        checkEquals(2, counts.get("零件"));

        System.out.println("库存：" + stock);
        System.out.println("去重顺序：" + encounterOrder);
        System.out.println("分数范围：" + range);
        System.out.println("并发计数：" + new TreeMap<>(counts));
        System.out.println("Map/Set 契约检查通过");
    }

    static final class MutableParticipant {
        private final String id;
        private int age;

        MutableParticipant(String id, int age) {
            this.id = id;
            this.age = age;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof MutableParticipant participant
                    && age == participant.age
                    && id.equals(participant.id);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, age);
        }
    }

    static void expect(Class<? extends Throwable> type, Runnable action) {
        try {
            action.run();
        } catch (Throwable throwable) {
            if (type.isInstance(throwable)) return;
            throw new AssertionError(
                    "expected=" + type + ", actual=" + throwable, throwable);
        }
        throw new AssertionError("expected exception=" + type.getName());
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void checkEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("expected=" + expected + ", actual=" + actual);
        }
    }
}

运行：

bash

javac --release 17 -encoding UTF-8 -Xlint:all -d out MapSetContractsDemo.java
java -cp out MapSetContractsDemo

预期输出：

text

库存：{零件=48, 木材=30, 皮革=20}
去重顺序：[零件, 木材, 皮革]
分数范围：{Bob=88, Charlie=92}
并发计数：{零件=2}
Map/Set 契约检查通过

保存需要的输出后清理：

bash

cd
ls -ld -- "$chapter10_map_root"
rm -r -- "$chapter10_map_root"

让 key 的身份保持稳定

先写明两个物品或参与者在什么条件下算同一个值。哈希容器要求相等对象具有相同 hash；排序容器按比较结果为 0 判断重复。参与这些判断的字段，在对象留在容器期间都应保持稳定。

最后再核对输出与并发边界：HashMap 的迭代顺序不能成为断言，subMap 是会反映原表变化的范围视图，ConcurrentHashMap 的一次 merge 也不能替多键业务事务提供原子性。能解释这三点，集合代码就不再依赖偶然行为。

查阅 Java 17 的正式契约

Map、HashMap 与 ConcurrentHashMap：空值、期望复杂度和原子复合操作。
Object.equals 与 Object.hashCode：哈希容器依赖的正式契约。
Set、SortedSet 与 NavigableSet：相等、排序与邻近查询。
NavigableMap：范围视图和相邻键操作。

继续学习：异常机制

集合账本已经能稳定表达顺序、身份和范围。下一章会处理另一类边界：方法无法履行契约时，异常怎样沿调用栈传播，调用方又该在什么位置恢复。

进入第 11 章：异常机制

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算

10.3 Map 与 Set 详解

用 Map 表达“名称 → 数量”

1. Map 的基础读取与更新

复合更新

2. HashMap 的查找模型

3. equals 与 hashCode 契约

4. 可变 key 为什么失联

5. Set 的重复与顺序由实现决定

6. TreeMap 与 NavigableMap 的范围视图

7. 遍历 Map

8. 并发写入要选并发语义

9. 完整可运行示例

让 key 的身份保持稳定

查阅 Java 17 的正式契约

继续学习：异常机制