元数据卡

项目	内容
前置知识	集合框架基础、List 详解（前两页）
预计时间	30 分钟
完成标志	能解释 HashMap 的 put/get 流程、扩容时机、HashSet 去重原理、TreeMap 排序机制

---

老陈递来仓库账本："登记库存——每样材料后面跟数量。铁锭 50、木材 30、皮革 20。"

用 List 要维护两个列表靠下标关联，删一个另一个全错位。你需要"地址簿"，通过名字查数量。这就是 Map。

HashMap 基础操作

// MapBasic.java，javac && java 运行
import java.util.*;
public class MapBasic {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("铁锭",50); stock.put("木材",30); stock.put("皮革",20);
        System.out.println("铁锭: "+stock.get("铁锭"));
        System.out.println("精金 or 0: "+stock.getOrDefault("精金",0));
        System.out.println("有木材吗: "+stock.containsKey("木材"));
        for (Map.Entry<String,Integer> e : stock.entrySet())
            System.out.println(e.getKey()+" = "+e.getValue());
    }
}

预期输出（顺序不定）： 铁锭: 50 精金 or 0: 0 有木材吗: true 皮革 = 20 木材 = 30 铁锭 = 50

工作原理

底层是数组+链表（Java 8+ 链表超 8 转红黑树）。put("铁锭",50)：hashCode()→h→h&(长度-1)→桶下标。桶空直接放；不空遍历链表用 equals 比 key，找到覆盖，没找到追加。get 走同样路径。

O(1) 来自数组下标直接定位。两 key 算到同一桶叫哈希冲突，冲突串成链表，越长越接近 O(n)。

不可变 key 的陷阱

// MapKeyMutation.java，javac && java 运行
import java.util.*;
class Person { String n; int a;
    Person(String name, int age) { n=name; a=age; }
    @Override public int hashCode() { return Objects.hash(n,a); }
    @Override public boolean equals(Object o) {
        if (!(o instanceof Person)) return false;
        Person p=(Person)o; return n.equals(p.n) && a==p.a; } }
public class MapKeyMutation {
    public static void main(String[] args) {
        Map<Person,String> map=new HashMap<>();
        Person p=new Person("Alice",25); map.put(p,"student");
        p.a=26; // 改了参与 hashCode 的字段！
        System.out.println("get(p): "+map.get(p));
        System.out.println("get(新): "+map.get(new Person("Alice",25)));
} }

预期输出： 两行 null。put 时 hash 基于 age=25；age 改后 hash 变了，去新桶找找不到。原桶 key 的 age=26，equals 也匹配不上。

规则：永远不用可变对象做 key。 String、Integer、LocalDate 天然安全。

负载因子与扩容

• 默认负载因子 0.75
• 元素数 > 容量 x 0.75 → 容量翻倍 → 所有元素重新哈希

Map<String, Integer> bigMap = new HashMap<>(2048); // 存 1000 条零次扩容

2 的幂的容量让 h & (n-1) 代替 h % n，位运算比取模快得多。0.75 是时间与空间的折中点。

HashSet：披着 Set 皮的 HashMap

HashSet 底层就是 HashMap：元素作为 key，value 全指向 dummy 对象（PRESENT）。去重原理来自 HashMap——key 相同就覆盖，add 返回 false。

// SetDemo.java，javac && java 运行
import java.util.*;
public class SetDemo {
    public static void main(String[] args) {
        Set<String> h=new HashSet<>();
        h.add("铁锭");h.add("木材");h.add("皮革");h.add("铁锭");
        System.out.println("HashSet: "+h+" size="+h.size());
        Set<String> t=new TreeSet<>();
        t.add("铁锭");t.add("木材");t.add("皮革");
        System.out.println("TreeSet: "+t);
        Set<String> l=new LinkedHashSet<>();
        l.add("铁锭");l.add("木材");l.add("皮革");
        System.out.println("LinkedHashSet: "+l); } }

预期输出：

HashSet: [木材, 皮革, 铁锭] size=3
TreeSet: [皮革, 木材, 铁锭]
LinkedHashSet: [铁锭, 木材, 皮革]

特性	HashSet	TreeSet	LinkedHashSet
底层	HashMap	TreeMap(红黑树)	LinkedHashMap
时间复杂度	O(1)	O(log n)	O(1)
迭代顺序	无序	自然升序	插入顺序

TreeMap：按 key 排序

需要排序遍历或范围查询时用 TreeMap。底层是红黑树。

// TreeDemo.java，javac && java 运行
import java.util.*;
public class TreeDemo {
    public static void main(String[] args) {
        Map<String,Integer> s=new TreeMap<>();
        s.put("Charlie",92);s.put("Alice",95);s.put("Bob",87);
        System.out.println("排序: "+s); // {Alice=95,Bob=87,Charlie=92}
        TreeMap<String,Integer> tm=(TreeMap<String,Integer>)s;
        System.out.println("headMap('C'): "+tm.headMap("C"));
        System.out.println("tailMap('B'): "+tm.tailMap("B"));
        System.out.println("subMap('A','C'): "+tm.subMap("A","C")); } }

HashMap vs TreeMap 性能：

操作	HashMap	TreeMap
插入/查找/删除	O(1)	O(log n)
排序遍历	不支持	O(n) 中序
范围查询	不支持	O(log n + k)

经验法则：除非需要排序或范围查询，否则永远选 HashMap。

Map 遍历方式

// MapTraverse.java，javac && java 运行
import java.util.*;
public class MapTraverse {
    public static void main(String[] args) {
        Map<String,Integer> map=new HashMap<>();
        map.put("铁锭",50);map.put("木材",30);map.put("皮革",20);
        for(Map.Entry<String,Integer> e:map.entrySet())
            System.out.println(e.getKey()+" -> "+e.getValue());
        for(String k:map.keySet())
            System.out.println(k+" -> "+map.get(k));
        map.forEach((k,v)->System.out.println(k+" -> "+v)); } }

entrySet 和 forEach 性能更好——直接操作 entrySet，不需多一次 map.get(key)。

---

旅人笔记

HashMap 用 hashCode 定位桶、equals 解决冲突，平均 O(1)。key 必须不可变，改字段就找不回。负载因子 0.75，超了双倍扩容重哈希。HashSet 底层就是 HashMap。需排序或范围查询时换 TreeMap，默认永远选 HashMap。

→ 下一步：异常处理与 I/O

程序总会出错。文件读不到、网络超时——不光要能处理数据，还要能在出错时说明"哪里出了问题"。

看异常处理 →