跳到主要内容

Map 集合

Map 是 Java 集合框架中与 Collection 并列的另一个超级重量级成员，以键值对（key-value）形式存储数据。Map 中的 key 是唯一的，value 可以重复，这让 Map 成为“字典”“缓存”“索引表”等场景的首选。

什么是 Map？🌍​

Map 是一个将唯一 key 映射到 value 的对象。它不继承 Collection，拥有自己的一套 API。

Map 的核心特性：

  • 🔑 key 唯一，不能重复；value 可以重复
  • 📦 通过 key 快速定位 value
  • 🧠 允许 null（视具体实现而定，如 HashMap 允许一个 null key）
  • 📚 提供 Entry 视图，支持遍历 key、value、entry

为什么要使用 Map？🎯​

Map 非常适合以下业务场景：

  1. 快速查找：根据 key 在 O(1) 或 O(log n) 时间拿到 value
  2. 缓存/索引：如用户 ID → 用户信息、订单号 → 订单详情
  3. 计数/去重：统计词频、访问次数
  4. 配置映射：存储键值配置、国际化文案
  5. 对象组装：构建树形、图结构或 DTO

常见 Map 实现 🔧​

实现类特点底层结构适用场景
HashMap ⚡最常用，允许一个 null key数组 + 链表/红黑树高性能、非线程安全
LinkedHashMap 🔗维护插入/访问顺序HashMap + 双向链表需顺序 + LRU 缓存
TreeMap 🌳key 自动排序红黑树有序映射、范围查询
Hashtable 🧱早期线程安全实现数组 + 链表老项目兼容
ConcurrentHashMap 🛡️高并发安全分段/桶 + CAS多线程读写
EnumMap 🎭针对枚举 key数组固定枚举键性能极高

日常开发默认优先 HashMap；多线程读多写少看 ConcurrentHashMap.newKeySet() + Map；需要顺序则 LinkedHashMap。

HashMap 关键知识点 🧠​

  • 结构：JDK 8 以后采用“数组 + 链表/红黑树”。同一桶元素超过 8 且数组长度 ≥ 64 时转为红黑树，避免 O(n) 链查。
  • 容量与负载因子：默认初始容量 16，负载因子 0.75；当 size > capacity * loadFactor 时触发扩容，扩为 2 倍并重新计算 hash。
  • hash 计算：高低位扰动 hash ^ (hash >>> 16)，减少碰撞。
  • 线程安全：非线程安全，存在扩容死循环等问题，不能在并发写环境直接用。
  • Fail-Fast：迭代器检测结构修改 modCount，并发修改抛 ConcurrentModificationException。

Map 常用操作 🛠️​

Map<String, Integer> map = new HashMap<>();

// 新增 & 覆盖
map.put("Java", 1);                 // 若 key 已存在则覆盖
map.putIfAbsent("Java", 2);         // key 不存在才插入

// 查询
int value = map.get("Java");        // 若不存在返回 null
int score = map.getOrDefault("Go", 0);

// 删除
map.remove("Java");
map.remove("Java", 1);              // key/value 都匹配才删

// 更新
map.replace("Java", 3);
map.compute("Java", (k, v) -> v == null ? 1 : v + 1);
map.merge("Python", 1, Integer::sum);

// 判空 & 大小
map.isEmpty();
map.size();

// 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}
map.forEach((k, v) -> System.out.println(k + ":" + v));

Map 常见遍历方式 🔄​

方式适用场景示例
keySet()只需要 keyfor (String key : map.keySet()) { ... }
values()只需要 valuefor (Integer v : map.values()) { ... }
entrySet()同时要 key/valuefor (Map.Entry<K,V> e : map.entrySet()) { ... }
forEachJava 8 Lambdamap.forEach((k,v) -> ...)
Iterator遍历时安全删除Iterator<Entry<K,V>> it = map.entrySet().iterator();

Map 实战场景 ✨​

1. 统计词频​

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

2. LRU 缓存​

Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100;
    }
};

3. TreeMap 范围查询​

NavigableMap<Integer, String> tree = new TreeMap<>();
tree.put(10, "A");
tree.put(20, "B");

tree.subMap(10, true, 20, true);   // 10~20 闭区间
tree.ceilingEntry(15);             // >=15 的最小键

Map 底层原理速记 🧩​

  • HashMap 扩容：新数组容量 = 旧容量 × 2；数据迁移时，元素要么留在原索引，要么移动 oldCap 偏移位置，二进制判断高位即可。
  • 红黑树转换：链表长度 > 8 且数组容量 ≥ 64 → 树化；树节点个数 < 6 → 退化为链表。
  • 链地址法：处理 hash 冲突时，桶里存链表/树，拉链法降低冲突影响。
  • ConcurrentHashMap：JDK8 采用 Node + CAS + synchronized（在桶级别），避免全表锁，读无锁，写锁粒度更细。
  • LinkedHashMap 访问顺序：构造函数 accessOrder=true 可实现基于访问的顺序维护，是手写 LRU 的基础。

Map 设计要点补充 🧱​

  • key 判等协议：任何自定义对象要作为 key，都必须保证 equals()、hashCode()、compareTo()（若使用 TreeMap）之间保持自洽，且字段不可变，避免写入后 hash 变化导致“丢失”。
  • Fail-Fast vs Fail-Safe：传统集合迭代器通过 modCount 快速失败；而 ConcurrentHashMap、CopyOnWriteArrayList 提供弱一致性或快照视图，牺牲实时性换取稳定性。
  • 装箱与自动拆箱成本：高频使用基础类型可考虑 TIntObjectHashMap 等第三方或 Long2ObjectOpenHashMap（fastutil），避免 Integer 装箱带来的 GC 压力。
  • 内存占用：HashMap 每个 Node 额外存储 key、value、hash、next 指针；当 value 较小、数据量大时要注意对象头开销，可用 Int2IntMap 等紧凑结构。
  • 不可变 Map：对于配置类数据，可使用 Map.of() 或 Guava ImmutableMap，在构建时校验并冻结，提升线程安全性与访问性能。

Map 高频面试题 🧨​

1. HashMap 和 Hashtable 的区别？​

  • 线程模型：Hashtable 对所有公有方法同步，锁粒度粗；HashMap 完全不加锁，性能优但需外部保证线程安全。
  • null 处理：HashMap 可存一个 null key、多 null value；Hashtable 不允许 null，以免同步代码中出现空指针。
  • 演进方向：Hashtable 已弃用，可使用 Collections.synchronizedMap(new HashMap<>()) 或更先进的 ConcurrentHashMap。

2. HashMap 如何解决哈希冲突？​

  • 通过 hash & (length - 1) 计算桶索引。
  • 桶为空：直接放置 Node。
  • 桶非空：比较 key，若相等则覆盖；否则采用链表（JDK8 之前）或链表+红黑树（JDK8 之后）追加。
  • 链表长度 > 8 且数组容量 ≥ 64 会树化，提高最坏情况查询效率至 O(log n)。

3. HashMap 为什么扩容是 2 的幂？​

  • 2 的幂保证 hash & (length - 1) 等价于取模，计算更快。
  • 扩容为 2 倍可保持新旧索引只在一个比特位上区别（最高有效位），迁移时节点只需判断该位是否为 1：为 1 移动到 i + oldCap，否则留在原桶。
  • 方便配合位运算扰动函数，降低冲突概率。

4. HashMap 在并发环境会出现什么问题？​

  • 数据竞争：两个线程同时 put 会互相覆盖，导致部分写入丢失。
  • 死循环：JDK7 rehash 时若链表被两个线程同时操作可能形成环，后续遍历 O(∞)。
  • 不一致视图：遍历时结构变化抛 ConcurrentModificationException，或读取到中间状态。
  • 内存可见性：缺少 volatile/happens-before 保障，线程可能看到未初始化完成的 Node。

5. ConcurrentHashMap 的并发策略？​

  • CAS + synchronized 混合：桶为空时通过 CAS 初始化；存在冲突时在桶头节点加内置锁，只锁单个桶。
  • volatile 可见性：Node.value 和桶数组都被标记为 volatile，读线程无需加锁即可看到最新值。
  • 批量操作：forEach、reduce 支持指定并行阈值，内部使用 ForkJoinPool 分区处理。
  • 扩容协助：触发扩容后插入 ForwardingNode，占位表示该桶正在迁移，其他线程遇到后协助搬运，防止单线程扩容卡住。

6. TreeMap 如何排序？​

  • 如果 key 实现 Comparable，TreeMap 使用自然顺序；否则必须传入 Comparator，否则运行时抛异常。
  • 插入/删除都通过红黑树旋转维持平衡，保证 O(log n)。
  • NavigableMap 接口拓展出 ceilingEntry、floorEntry 等范围操作，适合时间轴、排名实现。

7. 如何保证 Map 中自定义对象可以正确作为 key？​

  • 必须同时重写 hashCode() 与 equals()
  • equals() 一致性决定是否同一 key
  • hashCode() 决定桶位置，必须与 equals 保持约定
  • 可选实现 Comparable，让对象在 TreeMap 中也可排序；不需要排序则保持不可变即可。
  • 建议将与判等有关的字段声明为 final，避免写入后被修改导致 hash 失效。
class User {
    private String name;
    private int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User other = (User) o;
        return age == other.age && Objects.equals(name, other.name);
    }

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

8. 什么是 Fail-Fast？如何避免？​

  • Iterator 内部保存 expectedModCount，发现与 Map 的 modCount 不一致立即抛出 ConcurrentModificationException，目的是提醒开发者逻辑不安全。
  • 规避手段：
    • 单线程场景下，遍历时若需删除，调用迭代器自带的 remove()。
    • 多线程场景改用并发集合（如 ConcurrentHashMap、CopyOnWriteArrayList）。
    • 或先复制一份快照再遍历，成本换安全。

9. LinkedHashMap 如何实现 LRU？​

  • 构造函数第三个参数 accessOrder=true
  • 重写 removeEldestEntry
  • 每次访问节点都会把节点移动到双向链表尾部
  • 结合 accessOrder=true 时，get/put 均会调整节点位置，尾部为最近访问；头部为最久未访问。
  • 在重写 removeEldestEntry 时可以加入自定义条件（如按容量、按时间戳）。

10. Map 与 Collection 有何区别？​

  • Map 存储键值对，不允许重复 key；Collection 存储单值元素，可重复
  • Map 提供 entrySet()/keySet()/values() 视图；Collection 是单一元素视图
  • API 完全不同：Map 以 key 为中心
  • 语义差异导致遍历方式不同：Map 通过 entrySet 获得 key-value 组合，而 Collection 强调元素顺序或唯一性。
  • Map 更适合表达“关联关系”，Collection 更适合表达“元素集合”，面试常要求根据业务语义选取合适接口。

小结 💡​

  • Map 是“键值存储”的代名词，掌握 HashMap 是重中之重
  • 理解扩容、树化、hash 机制有助于分析性能瓶颈
  • 面试高频聚焦：HashMap 与 ConcurrentHashMap 的区别、线程安全、底层结构
  • 写代码时优先考虑具体场景：是否要顺序？是否多线程？是否需要排序？

熟练掌握这些知识点，你就可以在面试与实战中自信地解释任何 Map 相关的问题啦！🚀