HashMap 使用与底层原理 | JavaSE
HashMap 使用与底层原理
一、学习目标
完成本章后，你应该能够：
- 能够解释
HashMap<K,V>的核心定位和典型应用场景。 - 能够说明 HashMap 为什么不能依赖遍历顺序。
- 能够解释 HashMap 与 HashSet 在实现层面的关系。
- 能够解释 HashMap 中 key 为什么必须正确设计
hashCode()与equals()。 - 能够画出 JDK 8+ HashMap 的“数组 + 链表 + 红黑树”总体结构。
- 能够解释哈希扰动、桶定位、哈希碰撞、负载因子、扩容和树化的基本原理。
- 能够说明默认容量 16、默认负载因子 0.75 的准确含义。
- 能够理解
new HashMap<>()后底层 table 并不是立即创建。 - 能够解释
put()、get()、remove()在底层的大致工作流程。 - 能够使用 HashMap 完成词频统计、投票统计、对象映射等真实任务。
- 能够根据预计元素数量合理创建 HashMap。
二、核心知识
2.1 HashMap 是什么
HashMap<K,V> 是 Java 中最常用的 Map 实现类之一。
基本创建：
Map<String, Integer> map = new HashMap<>();
它用于保存：
key → value
映射关系。
例如：
Java → 95
MySQL → 90
Redis → 88
HashMap 同时继承 Map 的基本语义：
key 不重复
value 可以重复
例如：
Map<String, Integer> map = new HashMap<>();
map.put("Java", 80);
map.put("Java", 100);
最终不是两个 "Java"，而是：
Java → 100
旧 value 被新 value 替换。
2.2 HashMap 最核心的特点
可以先建立：
HashMap
├── key 不重复
├── value 可以重复
├── 不保证遍历顺序
├── 基于哈希表
├── 平均查找效率高
└── 非线程安全
其中：
不保证遍历顺序
非常重要。
假设：
map.put("Java", 1);
map.put("MySQL", 2);
map.put("Redis", 3);
不能写出依赖：
Java → MySQL → Redis
这一遍历顺序的业务代码。
即使某次运行“碰巧”如此，也不是 HashMap 提供的契约。
2.3 HashMap 与 HashSet 是什么关系
上一章学习 HashSet 时已经看到：
HashSet
↓
内部使用
↓
HashMap
HashSet 中：
set.add(element);
在实现思想上可以理解成：
map.put(element, PRESENT);
也就是说：
HashSet 元素
↓
HashMap 的 key
而 value 使用内部占位对象。
因此：
HashMap 的 key 去重机制
直接支撑了：
HashSet 的元素去重机制
这也是为什么：
HashMap 与 HashSet 的哈希底层原理高度一致。
2.4 HashMap 的底层总体结构
在 JDK 8+ 中，可以把 HashMap 抽象为：
HashMap
↓
Node<K,V>[] table
↓
桶 bucket
├── 空
├── 单个 Node
├── 链表
└── 红黑树
可视化：
table
index
0 1 2 3 4
↓ ↓ ↓ ↓ ↓
┌─────┬─────┬─────┬─────┬─────┐
│ │ ● │ │ ● │ │
└─────┴──│──┴─────┴──│──┴─────┘
│ │
↓ ↓
Node Node
↓
Node
↓
Node
当某个桶发生较多哈希碰撞时：
Node → Node → Node → ...
可能进一步转换成红黑树。
2.5 HashMap 中一个 Node 保存什么
从实现思想看，一个普通 HashMap 结点近似保存：
Node<K,V>
├── hash
├── key
├── value
└── next
可以抽象为：
class Node<K, V> {
int hash;
K key;
V value;
Node<K, V> next;
}
其中：
hash：处理后的 key 哈希值；key：键；value：值；next：发生桶内链表冲突时指向下一个结点。
注意：
这只是帮助理解的简化模型。
2.6 HashMap 为什么主要看 key
假设：
map.put(key, value);
HashMap 决定：
应该放到哪个桶？
这个映射是否已经存在？
主要依据：
key
而不是 value。
因此：
HashMap 的哈希
HashMap 的相等判断
HashMap 的桶定位
核心都围绕：
key
进行。
所以项目源资料中说：
Map 的整体特点主要由 key 决定。
这是非常重要的理解。
三、使用方法
3.1 创建 HashMap
常见方式：
Map<String, Integer> map = new HashMap<>();
如果需要 HashMap 自身 API：
HashMap<String, Integer> map = new HashMap<>();
普通业务代码通常优先：
Map<String, Integer> map = new HashMap<>();
体现面向接口编程。
3.2 put()
map.put("Java", 95);
map.put("MySQL", 90);
map.put("Redis", 88);
重复 key：
Integer oldValue = map.put("Java", 100);
假设原来：
Java → 95
则：
oldValue = 95
Map 中：
Java → 100
3.3 get()
Integer score = map.get("Java");
HashMap 的核心优势之一就是：
key
↓
哈希定位
↓
value
3.4 containsKey()
if (map.containsKey("Java")) {
System.out.println("存在 Java");
}
成员查询是 HashMap 最典型的用途之一。
3.5 remove()
Integer removed =
map.remove("Redis");
删除整个：
Redis → 88
映射。
3.6 遍历 HashMap
如果同时需要 key 和 value，通常推荐：
for (Map.Entry<String, Integer> entry
: map.entrySet()) {
System.out.println(
entry.getKey()
+ " -> "
+ entry.getValue()
);
}
也可以：
map.forEach((key, value) ->
System.out.println(
key + " -> " + value
)
);
但是：
不要依赖 HashMap 的遍历顺序。
3.7 HashMap 允许 null key 和 null value
这里现在讨论的是具体实现：
HashMap
而不是所有 Map。
HashMap 允许：
map.put(null, "value");
map.put("Java", null);
并且最多只能存在：
一个 null key
因为 key 本身不能重复。
value 则可以有多个 null。
例如：
Map<String, Integer> map = new HashMap<>();
map.put(null, 100);
map.put("Java", null);
map.put("MySQL", null);
这是合法的 HashMap 行为。
但这不能推广成：
所有 Map 实现都允许 null。
3.8 字符出现次数统计
这是 HashMap 最经典的训练。
例如：
String text = "aabbbcaa";
Map<Character, Integer> counts =
new HashMap<>();
传统写法：
for (char ch : text.toCharArray()) {
if (counts.containsKey(ch)) {
counts.put(
ch,
counts.get(ch) + 1
);
} else {
counts.put(ch, 1);
}
}
模型非常清晰：
字符 → 出现次数
3.9 使用 getOrDefault 简化计数
还可以：
for (char ch : text.toCharArray()) {
counts.put(
ch,
counts.getOrDefault(ch, 0) + 1
);
}
其中：
getOrDefault(ch, 0)
表示：
key 存在
→ 返回原值
key 不存在
→ 使用默认值 0
于是：
旧次数 + 1
再 put 回去。
3.10 使用 merge 进行计数
HashMap / Map 还可以：
counts.merge(ch, 1, Integer::sum);
含义近似：
第一次出现
→ ch → 1
已经存在
→ 原次数 + 1
这是非常简洁的统计写法。
不过它涉及方法引用和函数式接口，完整机制会在后续 Lambda 章节学习。
现阶段知道：
merge特别适合“存在则合并，不存在则初始化”的统计模型。
四、原理与进阶
4.1 HashMap 的哈希流程
假设：
map.put(key, value);
首先要获得：
key.hashCode();
但 OpenJDK 并不是直接拿原始 hashCode 定位桶。
概念上还会进行一次：
哈希扰动（Hash Spreading）
核心思想类似：
h ^ (h >>> 16)
目的之一是：
让原始 hashCode 的高位信息也参与到低位桶位置计算中。
所以流程更准确地表示：
key
↓
hashCode()
↓
哈希扰动
↓
处理后的 hash
↓
桶索引
4.2 null key 如何处理
HashMap 特殊处理：
key == null
时使用：
hash = 0
因此 HashMap 能支持一个 null key。
4.3 桶索引如何计算
HashMap 的 table 长度：
n
通常保持为：
2 的幂
定位桶时可以使用：
(n - 1) & hash
例如：
n = 16
那么：
n - 1 = 15
二进制：
0000 1111
通过：
(hash & 15)
即可快速取得桶索引。
因此 HashMap 采用 2 的幂容量并不是随意选择。
4.4 put() 的底层主流程
可以建立下面的核心模型：
put(key, value)
↓
计算 key 的 hash
↓
table 是否初始化？
↓
必要时初始化 / 扩容
↓
计算桶位置
↓
桶为空？
┌─────┴─────┐
│ │
是 否
│ │
直接创建 检查已有节点
Node ↓
key 是否相同？
hash 是否匹配？
equals 是否相等？
↓
┌─────┴─────┐
│ │
已存在 不存在
│ │
替换 value 插入新节点
↓
必要时链表树化
↓
size++
↓
超过 threshold？
↓
resize
这张流程图应该能够闭卷画出来。
4.5 HashMap 怎么判断“同一个 key”
核心逻辑可以理解为：
先比较 hash
↓
再判断
key == existingKey
或
key.equals(existingKey)
所以对于自定义 key：
Product
User
Student
必须认真设计：
equals()
hashCode()
否则 HashMap 可能无法正确：
找到原映射
覆盖原 value
删除原映射
判断 containsKey
4.6 一个危险案例：修改 key 的哈希字段
假设：
Product product =
new Product("旗舰店", "Java书");
map.put(product, 10);
而 Product 的：
store
name
参与：
equals
hashCode
之后：
product.setName("MySQL书");
那么：
product.hashCode()
可能改变。
此时：
map.get(product);
可能沿着新的哈希路径寻找。
但对象原来是在：
旧 hash 对应的桶
中插入的。
于是出现：
key 明明还在 HashMap 中
却可能无法正常查找到
因此：
作为 HashMap key 的身份字段应该尽可能稳定。
4.7 默认初始容量 16 的准确含义
HashMap 默认容量策略：
16
默认负载因子：
0.75
但不要错误理解为：
new HashMap<>();
执行的一瞬间就一定创建：
Node[16]
OpenJDK HashMap 的 table 是：
延迟初始化（Lazy Allocation）
刚：
new HashMap<>();
时内部：
table
仍可以是：
null
首次真正需要存储数据时才会进行分配。
因此：
默认初始容量 = 16
描述的是：
默认首次分配时的容量策略。
而不是：
构造 HashMap 对象时立即创建 16 个桶。
4.8 什么是 Capacity
容量（Capacity）指：
HashMap 当前哈希表拥有多少个桶。
例如：
16
32
64
128
注意：
capacity
不是：
map.size()
4.9 什么是 Load Factor
负载因子（Load Factor）：
默认 0.75
可以理解为：
哈希表装到多满时准备扩大容量。
例如：
capacity = 16
loadFactor = 0.75
对应阈值通常：
16 × 0.75 = 12
也就是说：
size 超过对应 threshold
时会触发扩容。
4.10 为什么默认是 0.75
负载因子是在：
空间
和：
查询性能
之间做权衡。
过低：
桶很多
元素很少
浪费空间。
过高：
桶太拥挤
哈希碰撞增加
查询成本上升。
所以：
0.75
是 Java HashMap 默认采用的一个时间与空间折中。
普通业务代码通常不需要随意修改它。
4.11 扩容
当当前映射数量超过阈值时：
HashMap
↓
resize
容量通常：
16 → 32
32 → 64
64 → 128
约翻倍。
扩容不仅是：
创建一个更大的数组
还需要重新安排原有节点在新 table 中的位置。
因此扩容存在成本。
4.12 JDK 8+ 扩容时的一个巧妙优化
假设旧容量：
oldCap
由于容量翻倍：
newCap = oldCap × 2
一个旧桶中的节点扩容后通常只有两种结果：
仍然留在原索引
或者：
移动到
原索引 + oldCap
判断可以利用：
(e.hash & oldCap)
的结果。
因此并不需要把整个 hash 逻辑从头重新计算一遍。
这是 HashMap 扩容实现中的一个重要优化思想。
学习阶段能理解：
扩容后桶数量翻倍
旧桶元素被拆分到两个可能位置
即可。
4.13 为什么预估容量有意义
假设已知：
马上要插入 100000 条数据
但仍然：
new HashMap<>();
HashMap 会经历多次：
16 → 32 → 64 → ...
扩容。
如果能够提前给出合理容量，就可以减少扩容次数。
4.14 JDK 21：newHashMap()
JDK 21 可以使用：
HashMap<String, Integer> map =
HashMap.newHashMap(10_000);
参数：
10_000
表达的是：
预计要保存的 mapping 数量。
它会帮助选择适当的内部容量。
相比开发者自己手算：
expectedSize / 0.75
更加直接。
这是 JDK 19 引入、JDK 21 可用的 API。
4.15 哈希碰撞
不同 key：
key A
key B
可能最终落入：
同一个桶
例如：
table[5]
↓
A → B → C
这就是：
哈希碰撞（Hash Collision）
HashMap 允许哈希碰撞存在。
如果完全没有碰撞才工作，那哈希表就没有实际意义了。
4.16 链表与红黑树
JDK 8+ HashMap：
桶内元素较少
→ 链表
桶内冲突严重且满足条件
→ 红黑树
OpenJDK 中的重要常量包括：
TREEIFY_THRESHOLD = 8
MIN_TREEIFY_CAPACITY = 64
但是不能简化成：
“只要链表有 8 个节点就立刻变红黑树。”
更准确地说：
当某个桶的冲突达到树化阈值相关条件时，还必须考虑当前 table 的容量。
如果 table：
< 64
实现通常优先：
扩容
而不是立即树化。
因为：
桶太少本身就可能是碰撞严重的原因。
4.17 为什么需要红黑树
极端情况：
bucket 5
A → B → C → D → E → F → G → ...
如果桶退化成长链表：
查询
可能越来越接近：
O(n)
转换成红黑树后，桶内查询性能可以改善到：
O(log n)
级别。
4.18 HashMap 的时间复杂度怎么理解
哈希分布良好情况下：
put
get
remove
containsKey
平均：
O(1)
但不能说：
HashMap 的 get 永远是绝对 O(1)。
因为还存在：
哈希碰撞
链表
红黑树
扩容
糟糕的 hashCode
等情况。
4.19 HashMap 遍历也不是“纯 O(size)”
这是一个容易忽略的知识。
HashMap 遍历的成本与：
当前容量
+
实际 size
都有关系。
如果你把容量设置得巨大：
capacity = 1_000_000
但只存：
10 个元素
遍历仍可能需要扫描大量桶。
因此：
初始容量也不是越大越好。
五、实践应用
5.1 字符频率统计
模型：
字符 → 次数
使用：
Map<Character, Integer>
5.2 单词频率统计
Java → 10
Spring → 8
MySQL → 5
非常典型：
Map<String, Integer>
5.3 投票统计
80 名学生选择景点：
北京 → 20
上海 → 15
西安 → 18
成都 → 27
模型：
景点 → 票数
使用 HashMap 非常自然。
5.4 ID 到业务对象
Map<Long, User>
模型：
userId → User
这是企业应用最典型的 HashMap 模型之一。
5.5 购物车商品数量
Map<Product, Integer>
模型：
商品 → 数量
例如：
《Java核心技术》 → 2
机械键盘 → 1
显示器 → 3
如果业务规定：
店铺 + 商品名称
相同就是同一个商品，那么 Product 的：
equals()
hashCode()
就需要按照这套业务身份规则设计。
5.6 嵌套 Map
例如：
Map<String, Map<String, Integer>>
可以表达：
班级
↓
学生 → 成绩
例如：
软件2201
├── 张三 → 90
└── 李四 → 88
软件2202
├── 王五 → 95
└── 赵六 → 91
这就是 HashMap 在复杂业务数据建模中的重要能力。
六、常见问题
6.1 HashMap 是有序的吗？
不能依赖其遍历顺序。
HashMap 官方不保证 encounter order。
如果业务要求确定顺序：
LinkedHashMap
可能更加合适。
6.2 HashMap 底层是不是数组？
不完整。
JDK 8+ 更准确的模型：
数组
+
链表
+
红黑树
6.3 默认容量是不是永远 16？
默认无参 HashMap 的默认初始容量策略是 16。
但：
new HashMap<>(100);
显然使用不同的容量策略。
而且无参构造后 table 还是延迟分配的。
6.4 为什么 HashMap 容量使用 2 的幂？
为了：
- 高效使用位运算计算桶位置；
- 简化扩容后的元素重分布；
- 改善哈希位利用。
6.5 HashMap 的 key 为什么必须正确实现 equals/hashCode？
因为 HashMap 使用：
hash
+
equals
判断：
是否是同一个 key
错误实现可能导致：
- get 找不到；
- put 无法正确覆盖；
- containsKey 判断错误；
- 同逻辑 key 出现多份映射。
6.6 value 需要重写 equals/hashCode 才能正常 put 吗？
HashMap 的键定位主要依赖：
key
所以作为普通 value 时，不需要为了 HashMap 的键定位机制专门重写 equals/hashCode。
当然业务本身可能仍需要 value 的相等语义。
6.7 HashMap 是否线程安全？
不是。
普通 HashMap：
不是线程安全集合
多线程环境需要：
- 外部同步；
- 或根据需求使用并发 Map。
后续并发章节继续学习。
6.8 HashMap 可以保存 null 吗？
HashMap：
允许一个 null key
允许多个 null value
但是不要把这个规则推广到所有 Map 实现。
6.9 为什么扩容很贵？
因为它需要：
创建更大的 table
+
重新安排大量已有节点
因此如果已知数据规模，可以合理设置容量减少不必要扩容。
6.10 HashMap 和 TreeMap 怎么选？
如果：
不需要排序
+
追求高效 key 查询
通常优先：
HashMap
如果：
需要 key 始终排序
再考虑：
TreeMap
TreeMap 会在 05-17 专门学习。
七、练习与验收
7.1 知识问答
- HashMap 的核心数据模型是什么？
- HashMap 为什么不能依赖遍历顺序？
- HashMap 与 HashSet 在实现上有什么关系？
- HashMap 底层总体结构是什么？
- Node 中通常保存哪些信息？
- 为什么 HashMap 的特点主要由 key 决定？
- HashMap 如何利用
hashCode/equals判断 key？ - 为什么 key 的身份字段不应该在放入 Map 后随意修改？
- 默认初始容量策略是多少？
- 默认负载因子是多少？
new HashMap<>()是否立即创建长度 16 的 table？- 什么是 capacity？
- 什么是 threshold？
- 什么是 load factor？
- 为什么容量使用 2 的幂？
- 哈希扰动解决什么问题？
- 桶索引如何计算？
- 什么是哈希碰撞？
- 什么情况下可能出现链表？
- 为什么需要红黑树？
- 为什么不能只记“链表长度达到 8 就树化”？
- 为什么 table 小时可能优先扩容？
- HashMap 基本操作平均时间复杂度是什么？
- 为什么遍历成本和 capacity 也有关？
HashMap.newHashMap(n)解决什么问题？
7.2 代码阅读
不运行：
Map<String, Integer> map = new HashMap<>();
map.put("Java", 80);
map.put("MySQL", 90);
map.put("Java", 100);
map.put(null, 60);
map.put("Redis", null);
System.out.println(map.size());
System.out.println(map.get("Java"));
System.out.println(map.containsKey(null));
System.out.println(map.containsValue(null));
回答：
- 最终 size 是多少？
"Java"最终对应什么？- 为什么第二次 put Java 没有增加 size？
- null key 是否存在？
- null value 是否存在？
- 如果换成其他 Map 实现，null 规则还能直接照搬吗？
7.3 手写代码
任务一：字符统计
统计：
hello java
中每个字符出现次数。
要求：
- 使用 HashMap；
- 先使用
containsKey + get + put； - 再使用
getOrDefault； - 比较两种写法。
任务二：80 人景点投票
景点：
北京
上海
西安
成都
随机模拟 80 名学生投票。
最终输出：
景点 → 票数
任务三：购物车
定义 Product：
store
name
业务规定：
店铺相同
+
商品名称相同
表示同一种商品。
使用：
Map<Product, Integer>
完成：
- 加入商品；
- 同商品再次加入数量 +1；
- 输出所有商品和数量。
7.4 Debug
下面程序：
Product product =
new Product("A店", "Java书");
Map<Product, Integer> map =
new HashMap<>();
map.put(product, 10);
product.setName("MySQL书");
System.out.println(map.get(product));
假设：
store + name
参与 equals/hashCode。
回答：
- 修改 name 后 hashCode 是否可能变化？
- HashMap 原来把对象保存在哪个桶？
- get 时会根据旧 hash 还是新 hash 寻找？
- 为什么可能出现“对象在 Map 中却找不到”？
- 应如何设计 key？
7.5 综合训练
设计课程选课系统：
studentId → Set<Course>
要求：
- 一个学生可以选择多门课程；
- 同一课程不能重复选；
- 可以通过 studentId 快速获得课程集合；
- 可以取消课程；
- 可以统计学生数量；
- 可以遍历全部学生及其课程。
要求解释：
- 外层为什么适合 Map？
- 为什么 value 可以使用 Set？
- HashMap 主要负责解决什么？
- Set 主要负责解决什么？
7.6 本章验收
- [ ] 能画出 HashMap 底层结构。
- [ ] 能口述 put 主流程。
- [ ] 能口述 get 主流程。
- [ ] 能解释 hashCode/equals 在 key 查找中的作用。
- [ ] 能解释哈希扰动。
- [ ] 能解释
(n - 1) & hash。 - [ ] 能准确解释默认容量 16 与延迟初始化。
- [ ] 能解释 0.75 负载因子。
- [ ] 能解释 resize。
- [ ] 能解释树化阈值与最小树化容量。
- [ ] 能解释 HashMap 平均 O(1) 的前提。
- [ ] 能使用 HashMap 完成字符统计。
- [ ] 能使用 HashMap 完成对象 → 次数模型。
- [ ] 能设计稳定可靠的自定义 key。