学完了单列的 Collection，本篇进入双列世界：Map 用”键找值”的模型组织数据，是现实开发中出现频率最高的结构。同时把 Collections 工具类和集合嵌套一并拿下，至此集合框架的主干就齐了。

本篇目标

  • 理解 Map 的键值对模型，说清它和 Collection 的区别
  • 掌握 HashMap、LinkedHashMap、TreeMap、Hashtable 的特点与选型
  • 熟练 Map 的四种遍历方式
  • 会用 Collections 工具类的常用方法，理解集合嵌套

Map：键值对模型

Map 存储”键 → 值”的映射：一个键最多映射一个值，键不允许重复（put 同键会覆盖旧值并返回旧值），值随意。这种模型也叫字典或关联数组，Python 的 dict、JS 的对象字面量都是同一种思想。和 Collection 的区别一句话说清：Collection 单列、Map 双列；Map 的数据结构只针对键有效，和值无关——所以自定义对象做键和放进 HashSet 一样，必须重写 hashCode/equals，否则两个内容相同的键会被当成不同的键。

HashMap<String, Integer> hm = new HashMap<>();
hm.put("张三", 23);            // 键首次出现，返回 null
hm.put("李四", 24);
hm.put("张三", 25);            // 键已存在，覆盖旧值并返回 23
hm.get("张三");                // 25，根据键取值
hm.remove("李四");             // 按键删除，返回被删的值
hm.containsKey("王五");        // 判断键是否存在
hm.size();                     // 键值对个数

Map 家族四个实现类

  • HashMap：底层哈希表，无序、最快，允许一个 null 键和多个 null 值，线程不安全，是默认选择。一句话预告：它的灵魂是”hashCode 定位桶 + 拉链法解决冲突”，JDK 8 起冲突严重时还会把链表树化成红黑树，本篇点到为止，后续会专门做 HashMap 源码分析。
  • LinkedHashMap：哈希表 + 双向链表，遍历时怎么存就怎么取，代价是维护链表的少量开销。
  • TreeMap：底层红黑树，键按排序规则存放，要求键可比较（Comparable 或传入 Comparator），用法和 TreeSet 一脉相承。
  • Hashtable：JDK 1.0 的遗物，方法级 synchronized 线程安全但低效，且不允许 null 键值；新代码别用，并发场景直接上 ConcurrentHashMap。

什么时候用谁：单线程无顺序要求用 HashMap；要按插入顺序遍历用 LinkedHashMap；键要排序用 TreeMap；并发用 ConcurrentHashMap——Hashtable 基本只活在面试题里。”HashMap 和 Hashtable 的区别”正是经典面试题：记住新的快、允许 null，旧的安全但慢、禁止 null，结论是新代码一律 HashMap。

Map 的四种遍历方式

Map 没有迭代器，遍历要先转成 Collection 的视角。方式一，键找值：

for (String key : hm.keySet()) {
    System.out.println(key + "=" + hm.get(key));
}

方式二，键值对（推荐）：entrySet 把每个键值对看成一个 Entry 对象，少一次哈希查找，效率更高：

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

entrySet 更快的原因很直白：keySet 方式拿到键后还要再 get() 一次哈希查找，entrySet 直接摊开内部节点，键值一步到位。方式三，只遍历值（拿不到键，用得少）：for (Integer v : hm.values())。方式四，JDK 8 的 forEach：hm.forEach((k, v) -> System.out.println(k + "=" + v))。日常记住前两种即可。

Collections 工具类

Collections 之于集合，相当于 Arrays 之于数组，常用的就几招：

List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(2);

Collections.sort(list);            // 排序，元素须实现 Comparable 或传入比较器
Collections.shuffle(list);         // 随机打乱，洗牌就靠它
Collections.reverse(list);         // 反转
Collections.max(list);             // 最大值（还有 min）
Collections.binarySearch(list, 2); // 二分查找，前提：list 必须已排序

sort 内部是稳定的归并排序，shuffle 就是循环里随机交换下标。还有一个易忽视的方法族：Collections.synchronizedList(new ArrayList<>()) 能把线程不安全的集合包装成同步版本，是应对”裸 ArrayList 要在多线程下用”这类场景的应急手段。

集合嵌套

真实业务的数据往往有层级：一个班级有多个学生，一个学校有多个班级——HashMap<String, ArrayList<Student>> 这类嵌套就是自然的表达。要点只有一个：泛型写完整，逐层 new，逐层遍历，思路和二维数组一脉相承。嵌套没有层数限制，但超过两层就该考虑抽实体类了，否则泛型声明会长得没法看。

HashMap<String, ArrayList<String>> school = new HashMap<>();
ArrayList<String> cls1 = new ArrayList<>();
cls1.add("张三");
cls1.add("李四");
school.put("一班", cls1);

for (Map.Entry<String, ArrayList<String>> en : school.entrySet()) {
    System.out.println(en.getKey());
    for (String name : en.getValue()) {
        System.out.println("  " + name);
    }
}

经典练习一：统计每个字符出现的次数

键存字符、值存次数，这是 Map 最经典的应用——词频统计的雏形：

String str = "aaaabbbcccccccccc";
HashMap<Character, Integer> hm = new HashMap<>();
for (char c : str.toCharArray()) {
    hm.put(c, hm.containsKey(c) ? hm.get(c) + 1 : 1);
}
for (Map.Entry<Character, Integer> en : hm.entrySet()) {
    System.out.println(en.getKey() + "=" + en.getValue());
}

经典练习二：斗地主洗牌发牌（带排序）

技巧在于用 HashMap 给每张牌编号：洗牌只洗编号（Integer 好排序），看牌时再按编号把牌面翻译回来。编号递增恰好对应牌面大小，TreeSet 自动排序后，玩家手里的牌天然就是理好的。

// 组装牌堆：编号 -> 牌面
String[] nums = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2"};
String[] colors = {"方片", "梅花", "红桃", "黑桃"};
HashMap<Integer, String> poker = new HashMap<>();
ArrayList<Integer> indexList = new ArrayList<>();
int index = 0;
for (String num : nums) {
    for (String color : colors) {
        poker.put(index, color + num);
        indexList.add(index++);
    }
}
poker.put(index, "小王");
indexList.add(index++);
poker.put(index, "大王");
indexList.add(index);

// 洗牌：只打乱编号
Collections.shuffle(indexList);

// 发牌：TreeSet 收编号，自动排好
TreeSet<Integer> player1 = new TreeSet<>();
TreeSet<Integer> player2 = new TreeSet<>();
TreeSet<Integer> bottom = new TreeSet<>();
for (int i = 0; i < indexList.size(); i++) {
    int idx = indexList.get(i);
    if (i >= indexList.size() - 3) {
        bottom.add(idx);
    } else if (i % 3 == 0) {
        player1.add(idx);
    } else {
        player2.add(idx);
    }
}

// 看牌：按编号取牌面
for (Integer idx : player1) {
    System.out.print(poker.get(idx) + " ");
}

这一道题把 Map、List、TreeSet、Collections.shuffle 全用上了，是集合框架的综合演练，值得亲手敲一遍并跑起来看效果。

小结

  • Map 以键值对组织数据，键唯一、值可重复；put 同键会覆盖并返回旧值。
  • 选型：默认 HashMap，要顺序用 LinkedHashMap，要排序用 TreeMap，并发用 ConcurrentHashMap，Hashtable 留给面试。
  • 遍历优先 entrySet（少一次查找），其次 keySet 键找值。
  • Collections 提供 sort/shuffle/binarySearch 等静态方法，binarySearch 前必须先排序。
  • 集合嵌套是表达层级数据的常规手段，泛型写全、逐层操作即可。