5.3 门牌索引：Map

5.3 门牌索引：Map

本节摘要：Map 存键值对——键是门牌号（唯一、用于定位），值是门牌后的住户（可重复）。HashMap 按哈希定位、快而不保序；LinkedHashMap 保插入序；TreeMap 按键排序。一次 put 的内部过程是：算哈希、定位桶、键冲突时用 equals 判定覆盖或挂链，超阈值扩容。本节拆开这个过程，比较三种遍历姿势，并复现可变键的定位漂移事故。

没有门牌号的查找有多慢

按"身份证号查人"，用 List 就得从头扫到尾；数据百万级时每次查询都是一次全库巡航。Map 的解法是给每条记录发一个门牌号（键），查询时先算门牌的位置直接走到柜子前——这个"算位置"用的正是键的 hashCode。先看日常用法：

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

public class MapDemo {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();   // 门牌：商品编号 住户：库存数
        stock.put("P01", 50);           // 登记门牌
        stock.put("P02", 30);
        stock.put("P01", 80);           // 同一门牌再登记 覆盖旧住户
        System.out.println(stock.size());       // 输出：2 门牌不重复
        System.out.println(stock.get("P01"));   // 输出：80 拿到的是覆盖后的值
        System.out.println(stock.containsKey("P02"));  // 输出：true
        System.out.println(stock.get("P99"));   // 输出：null 没这个门牌

        Integer old = stock.put("P02", 35);     // put 返回被覆盖的旧值
        System.out.println("旧库存：" + old);    // 输出：旧库存：30

        stock.remove("P02");
        System.out.println(stock);              // 输出：{P01=80}
    }
}
​

要点两条。put 的双重身份：新门牌是登记、旧门牌是覆盖，返回值是被顶掉的旧值（没有旧值为 null）——一行代码同时完成"存在就更新、不存在就插入"。get 查无此键返回 null：拿返回值直接拆箱（4.1 节）或直接调方法的写法都有空指针风险，先用 containsKey 判断，或用带缺省值的查询方法。

一次 put 的内部旅程

图 5-3 HashMap 一次 put 的内部流程与扩容

六个环节里三个值得展开。键的哈希质量决定碰撞率： hashCode 全都相同（比如恶意的或糟糕的实现），所有元素挤一个桶，哈希表退化成链表——这正是"键必须正确实现 hashCode"的性能理由，与 5.2 节 Set 一致。负载因子与扩容：默认桶数十六、负载因子四分之三，元素超过十二个就扩容翻倍并全表重排；预估数据量时用 new HashMap(预估容量) 传入初始容量，能省掉连续搬家的开销。挂链转树：单个桶排队超过八个（且表足够大）时，这条链转成红黑树，把最坏情况从线性拉回对数级——这是哈希实现对抗碰撞攻击的防御工事。

遍历三姿势

Map 不能直接 for-each（它不是 Iterable），遍历要选一个视角：遍历门牌、遍历住户、或成对遍历：

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

public class MapIterDemo {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        scores.put("赵一", 82); scores.put("钱二", 95); scores.put("孙三", 88);

        for (String key : scores.keySet()) {            // 姿势一：只要门牌
            System.out.println("门牌 " + key);
        }
        for (Integer v : scores.values()) {             // 姿势二：只要住户
            System.out.println("住户 " + v);
        }
        for (Map.Entry<String, Integer> e : scores.entrySet()) {   // 姿势三：成对取 门牌加住户
            System.out.println(e.getKey() + " 得分 " + e.getValue());
            // 输出三行 赵一 82 钱二 95 孙三 88（具体顺序与哈希分布有关）
        }

        int total = 0;
        for (Integer v : scores.values()) total += v;
        System.out.println("平均分：" + total / scores.size());   // 输出：平均分：88
    }
}
​

三种姿势按需选：查名单用 keySet、汇总用 values、既改又看用 entrySet——entrySet 一轮遍历同时拿到键与值，比分两次查省一半定位成本。LinkedHashMap 与 TreeMap 的角色和 Set 那边完全对应：前者遍历按插入序、后者按键排序，TreeMap 还提供按键的范围视图（比大小、取一段区间）。

可变键事故：搬家不销户

背景：一个自定义类当键，入 Map 后字段被改。操作：

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

class RoomKey {
    String building;
    int number;
    RoomKey(String b, int n) { building = b; number = n; }

    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        RoomKey k = (RoomKey) o;
        return number == k.number && Objects.equals(building, k.building);
    }
    @Override public int hashCode() { return Objects.hash(building, number); }
}

public class MutableKeyDemo {
    public static void main(String[] args) {
        Map<RoomKey, String> rooms = new HashMap<>();
        RoomKey key = new RoomKey("甲栋", 301);
        rooms.put(key, "会议室");                 // 入柜时按当时的哈希定位
        System.out.println(rooms.get(key));       // 输出：会议室 引用还在 同一对象直接命中

        key.number = 302;                          // 改字段 哈希随之变化 等于搬家没销户
        System.out.println(rooms.get(key));       // 输出：null 按新哈希找 旧位置当然没有
        System.out.println(rooms.containsKey(key)); // 输出：false
        System.out.println("柜里还躺着：" + rooms.size()); // 输出：柜里还躺着：1 删都删不掉
    }
}
​

结果：门牌改号后，查询、删除全部扑空，那条记录成了柜里的幽灵数据。解读：定位两步走（哈希定桶、equals 核对）的第一步就断了——键的哈希是入柜时算的，改字段后用新哈希去旧桶找，自然找不到；而 containsKey 返回 false 又让 remove 无从下手。变式：把 RoomKey 的字段改成 final、去掉改字段的接口（1.4 节铁证），键从此不可变，事故根除；工程上更省心的做法是直接用 String、Integer 这些天生不可变的类型组合当键。

本节要点回顾

• Map 存门牌与住户：键唯一定位、值随便重复；put 兼具登记与覆盖、返回旧值，get 查无返回 null（判空再拆箱）
• put 六步：算哈希、定位桶、equals 核对、覆盖或挂链、查负载、必要时翻倍扩容全表重排——键的哈希质量决定碰撞率
• 三种 Map 对应 Set 三兄弟：HashMap 快无序、LinkedHashMap 保插入序、TreeMap 键排序带范围查询
• 遍历三姿势：keySet 要名单、values 汇总、entrySet 成对处理最省——Map 本身不是 Iterable
• 键必须不可变：可变键改字段即搬家不销户，查询删除全扑空成幽灵数据；不可变类型组合当键是默认答案

下一节给工具房收尾：叫号机 Queue 与双端队列 Deque（LinkedList 的第二张证在此兑现），外加集合的百宝箱 Collections——排序、反转、包装同步与不可变集合一柜全齐。