Java 集合框架：HashMap 从入门到面试

Java 集合框架：HashMap 从入门到面试

如果要选一个 Java 集合里出镜率最高的类，那大概率就是 HashMap 了。它几乎是面试必问，也是日常开发中最常用的数据结构之一。今天就来系统梳理一下 HashMap 的核心知识点。

基本用法

Map<String, Integer> map = new HashMap<>();
map.put("Java", 1);
map.put("Python", 2);
map.put("Go", 3);

System.out.println(map.get("Java"));    // 1
System.out.println(map.containsKey("Go")); // true
map.remove("Python");

API 很简单，但真正有意思的是它的内部实现。

底层结构

以 JDK 8 为例，HashMap 的底层是 数组 + 链表 + 红黑树：

• 整个结构是一个数组，每个数组位置称为一个"桶（bucket）"。
• 当多个 key 的哈希值映射到同一个桶时，用链表串联。
• 当链表长度超过阈值（默认 8）且数组长度 >= 64 时，链表会转为红黑树，将查找复杂度从 O(n) 降到 O(log n)。

JDK 7 只有数组 + 链表，没有红黑树优化。

put 操作的大致流程

1. 对 key 计算 hash 值（不是直接调用 hashCode()，还做了一次扰动处理，让高位也参与运算，减少碰撞）。
2. 根据 hash 值定位到数组下标。
3. 如果该位置为空，直接放入新节点。
4. 如果不为空，遍历链表/红黑树：
   • key 相同则覆盖 value；
   • 不同则追加到末尾。
5. 插入后检查是否需要扩容。

为什么容量必须是 2 的幂次？

HashMap 定位下标用的是 hash & (n - 1)，其中 n 是数组长度。当 n 是 2 的幂次时，这个位运算等价于 hash % n，但效率更高。如果 n 不是 2 的幂次，会导致分布不均匀，碰撞增多。

默认初始容量是 16，负载因子是 0.75，也就是说元素数量超过 16 * 0.75 = 12 时就会扩容，每次扩容为原来的 2 倍。

为什么线程不安全？

HashMap 在多线程环境下可能出现以下问题：

• 数据覆盖：两个线程同时 put，后写入的可能覆盖先写入的。
• 扩容时数据丢失：JDK 7 中多线程扩容甚至可能导致链表成环，造成死循环（JDK 8 已修复成环问题，但数据覆盖仍然存在）。

线程安全的替代方案：

• **ConcurrentHashMap**（推荐）：分段锁 / CAS + synchronized，并发性能好。
• **Collections.synchronizedMap()**：全局加锁，性能较差。
• **Hashtable**：老旧类，不推荐使用。

为什么重写 equals 必须重写 hashCode？

HashMap 判断两个 key 是否相同的逻辑是：

1. 先比较 hashCode，不同则直接认为是不同 key；
2. hashCode 相同，再用 equals 比较。

如果你只重写了 equals 没重写 hashCode，两个"逻辑相等"的对象可能 hashCode 不同，导致 HashMap 认为它们是不同的 key，出现诡异的行为。所以 equals 和 hashCode 必须成对重写。

常用 API 小贴士

// JDK 8 引入的实用方法
map.putIfAbsent("Java", 10);        // key 不存在时才 put
map.computeIfAbsent("Ruby", k -> 5); // key 不存在时计算 value
map.getOrDefault("C++", 0);         // 取不到时返回默认值
map.forEach((k, v) -> System.out.println(k + "=" + v));

一句话总结

• 底层：数组 + 链表 + 红黑树（JDK 8）。
• 容量必须是 2 的幂次，默认 16，负载因子 0.75。
• 线程不安全，并发场景用 ConcurrentHashMap。
• 自定义类作 key 时，务必同时重写 equals 和 hashCode。