NOTES · 学习笔记
从 0 到 1 理解 HashMap 底层原理
本文的实现细节以 JDK 8 的 HashMap 为例。数组下标和冲突示例会先使用简化模型,后面再对应到 Java 的实际实现。
一、什么是 HashMap?
假设现在有一个用户系统,里面有 100 万个用户。
我们需要根据用户 ID 查询用户信息。
例如:
用户 ID:1001;用户姓名:张三
用户 ID:1002;用户姓名:李四
用户 ID:1003;用户姓名:王五
用户 ID:1004;用户姓名:赵六
最简单的方式是什么?
方式一:数组遍历
假设我们把用户全部放进数组:
User[] users = new User[1000000];现在要查找 ID 为 1003 的用户:
for (User user : users) {
if (user.id == 1003) {
return user;
}
}问题来了:
• 如果用户在第一个位置,很快就找到。
• 如果用户在最后一个位置,需要遍历大量数据。
• 如果用户不存在,需要遍历整个数组。
最坏情况下,时间复杂度是:
O(n)
100 万条数据,最坏可能需要比较 100 万次。
有没有办法直接找到用户,而不需要遍历?
这就是 HashMap 要解决的问题。
二、HashMap 的核心思想
HashMap 的核心思想其实很简单:
通过 Key 计算出一个数组下标,然后直接去对应位置查找 Value。
例如
Key:1003(用户 id)→ 通过 Hash 函数(计算对应 Key 的位置)→获取数组下标
例如:
下面用一个简化模型说明定位过程;这不是 Java 8 HashMap 的实际下标公式。
int hash = hashFunction(1003);
int index = hash % 16;假设最终得到:
hash = 35
index = 3那么我们就可以直接访问数组的 index 3 位置。
这就是 HashMap 查询效率高的原因。
在哈希分布比较均匀的平均情况下,查询时间复杂度可以达到:
O(1)
不过这里有个问题
1003 % 16 = 3
1019 % 16 = 3两个不同的 key 通过一个 hash 函数得出来的位置可能是一样的
那么问题来了:
数组下标只有一个位置,两个不同的 Key 都想存进去,怎么办?
这就是 HashMap 非常重要的一个知识点:
哈希冲突。
三、哈希冲突
和刚刚那个 Key 的例子一样,我们再来看一遍哈希冲突场景
我们存入三组数据:
map.put(1, "张三");
map.put(9, "李四");
map.put(17, "王五");为了方便理解,这里只对示例中的正整数使用下面这个简化计算方式:
index = key % 8;计算结果:
Key:1;计算过程:1 % 8;数组下标:1
Key:9;计算过程:9 % 8;数组下标:1
Key:17;计算过程:17 % 8;数组下标:1
你会发现:
三个不同的 Key,最终都指向了数组下标 1。
发生哈希冲突
这就是哈希冲突:不同的 Key,经过哈希计算后,得到了相同的数组下标。
注意:哈希冲突不代表两个 Key 相同,也不代表它们的哈希值一定相同。
1. 如何解决哈希冲突?
常见的解决方案有两种:
• 链地址法
• 开放寻址法
方案一:链地址法
核心思想:
如果多个 Key 映射到了同一个数组下标,就在这个位置建立链表,把多个数据连接起来。
假设 HashMap 底层有一个长度为 8 的数组。
我们使用一个简单的公式计算数组下标:
index = key % 8;现在依次存入三条数据:
map.put(1, "张三");
map.put(9, "李四");
map.put(17, "王五");计算结果:
Key:1;计算过程:1 % 8;数组下标:1
Key:9;计算过程:9 % 8;数组下标:1
Key:17;计算过程:17 % 8;数组下标:1
你会发现,三个 Key 最终都要存入 index 1。
2. 链地址法是怎么解决的?
假设我们第一次存入:
map.put(1, "张三");此时 index 1 是空的,我们直接把数据放进去。
第一次存入
index 0
空
index 1
(1, 张三)
index 2
空
index 3
空
接下来存入:
map.put(9, "李四");计算得到 index 1。
但是 index 1 已经有数据了,怎么办?
链地址法的做法是:
让 index 1 指向一个链表,把新的数据作为链表中的节点连接起来。
第二次存入
数组 index 1
节点 (1, 张三)
节点 (9, 李四)
再存入:
map.put(17, "王五");计算结果还是 index 1。
于是继续把新节点连接到链表中。
最终存储结构:
数组 index 1 → 头节点 → (1, 张三) → (9, 李四) → (17, 王五) → null
现在,虽然三个 Key 都映射到了 index 1,但它们并没有互相覆盖,而是通过链表连接在一起。
3. 如果现在要查询 Key = 9 呢?
例如:
map.get(9);执行过程:
1. 在这个简化示例中,计算 Key = 9 对应的数组下标:9 % 8 = 1。
2. 找到数组 index 1。
3. 从链表头节点开始查找。
4. 第一个节点 Key = 1,不匹配。
5. 第二个节点 Key = 9,匹配成功。
6. 返回 Value:李四。
所以,链地址法虽然解决了哈希冲突,但如果链表越来越长,查询仍然需要遍历链表。
4. 另一种方案:开放寻址法
另一种思路是:
如果当前位置已经被占用,就继续寻找其他空位置。
例如:
Key 1 → index 1
Key 9 → index 2(原位置被占用)
Key 17 → index 3(原位置被占用)这种方法叫开放寻址法。
它的特点是:数据直接存储在数组中,不需要额外建立链表。
开放寻址法和链地址法是两种不同的冲突处理方式。Java 8 的 HashMap 使用链地址法;当某个桶里的链表较长且满足树化条件时,才会把这个桶转换成红黑树。开放寻址法本身没有桶内链表,也不会通过红黑树处理链表。
四、红黑树
为什么需要红黑树?
1. 先看一个问题
假设多个不同的 Key 都映射到了数组的 index 1。在桶还没有树化之前,这些数据会先通过链表连接起来;冲突继续增加时,链表也会变长。
假设我们要在这条链表中查询最后一个节点。
使用链表的方式,需要从头开始逐个比较。
最坏情况下:O(n)
也就是说,链表越长,查询所需要的比较次数就越多。
2. 红黑树是什么?
红黑树是一种自平衡二叉搜索树。
第一:什么是二叉树?
一个节点最多有两个子节点:
第二:什么是二叉搜索树?
它有一个重要规则:
• 左子树的节点值小于当前节点。
• 右子树的节点值大于当前节点。
例如:
有了这个规则,查找数据时就不需要一个一个遍历。
例如查找 40:
1. 从根节点 33 开始。
2. 40 大于 33,往右边找。
3. 找到 40。
这就是二叉搜索树的查找思路。
1. 为什么还需要红黑树?
普通二叉搜索树有一个问题:它可能变得非常不平衡。
例如依次插入:
1、2、3、4、5可能形成这样的结构:
不平衡的二叉搜索树
1→2→3→4→5
极端情况下,二叉搜索树会退化成链表。
这样查询效率又退化成了:
O(n)
所以我们需要一种能够自动维持树结构平衡的数据结构。
这就是红黑树。
五、HashMap 的存取原理 · 1. 先看一段代码
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
HashMap<Integer, String> map = new HashMap<>();
map.put(1, "张三");
map.put(9, "李四");
map.put(17, "王五");
System.out.println(map.get(9));
}
}输出:
李四我们重点看两个方法:
• put():存储数据。
• get():查询数据。
2. put():数据是怎么存进去的?
假设我们执行:
map.put(1, "张三");Java HashMap 内部可以简化理解为以下几个步骤。
1. 计算 Key 的哈希值
根据 Key 计算哈希值,为后续定位数组下标做准备。
2. 计算数组下标
根据哈希值和数组长度,计算数据应该存放在哪个桶中。
3. 判断当前位置是否为空
• 如果为空,直接创建节点。
• 如果不为空,说明可能发生了哈希冲突。
4. 处理哈希冲突
遍历对应桶中的节点,判断 Key 是否已经存在。
• Key 相同:更新 Value。
• Key 不同:继续寻找位置,必要时添加新节点。
5. 检查是否需要树化或扩容
根据桶中节点数量、数组容量等条件决定后续操作。
get():数据是怎么查询出来的?
现在执行:
map.get(9);它的过程和 put() 有相似之处。
1. 计算 Key 的哈希值
根据 9 计算哈希值。
2. 计算数组下标
找到对应的桶,也就是 index 1。
3. 检查桶中的节点
如果桶中只有一个节点,检查 Key 是否匹配。
4. 遍历链表或查询红黑树
如果存在多个节点,就根据节点的 Key 继续查找。
5. 返回 Value
找到 Key = 9,返回对应的 Value:李四。
3. 进入 JDK 8 源码:看看真实的 put()
前面讲的是原理,现在看一下 Java 源码中的核心代码。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}这段代码说明:
put() 并没有直接完成所有存储操作,而是:
1. 调用 hash(key) 计算哈希值。
2. 调用 putVal() 执行真正的存储逻辑。
六、哈希扰动与数组下标计算
1. 为什么需要哈希扰动?
先回顾一下:
HashMap 需要根据 Key 计算出数组下标,才能知道数据存在哪里。
Java 中每个对象都有自己的 hashCode() 方法,可以获取一个哈希值。
例如:
int hash = key.hashCode();但是有一个问题:
如果只使用哈希值的低位来计算数组下标,那么高位的信息就可能没有被充分利用。
因此,Java 8 的 HashMap 引入了哈希扰动。
它的作用是:
让哈希值的高位信息也参与后续的桶下标计算,帮助不同的 Key 分布得更均匀。
1. Java 8 的哈希扰动函数
看一下源码:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}重点看这一行:
h ^ (h >>> 16)简单理解:
• h:原始哈希值。
• h >>> 16:将哈希值无符号右移 16 位。
• ^:异或运算。
通过这种方式,让哈希值的高 16 位信息也参与低位计算。
2. 数组下标是怎么计算的?
接下来是重点。
Java 8 HashMap 使用:
index = (n - 1) & hash;其中:
• n:数组长度。
• hash:经过扰动处理后的哈希值。
• &:按位与运算。
为什么不用 % 取模?
因为 HashMap 的数组长度通常是 2 的幂次方。
例如:
16、32、64、128当数组长度为 16 时:
(n - 1) & hash
(16 - 1) & hash
15 & hash这样就能通过位运算得到数组下标。这里重点是计算方式简单;哈希扰动则帮助高位信息参与低位索引的计算。
3. 为什么数组长度必须是 2 的幂次方?
这样设计主要有两个原因:
1. 可以使用 (n - 1) & hash 快速计算数组下标。
2. 在配合哈希扰动后,可以让哈希值的高位信息也影响低位索引,帮助数据分布得更均匀。仅仅把数组长度设成 2 的幂次方,并不能单独保证哈希分布均匀。
例如数组长度为 16:
n = 16
n - 1 = 1515 的二进制:
00001111与 hash 进行按位与运算,就可以得到 0~15 之间的数组下标。
七、扩容机制和负载因子 · 1. 为什么需要扩容?
HashMap 底层数组长度有限。
随着存入的数据越来越多,多个 Key 可能落到同一个桶中,导致哈希冲突增加,查询效率下降。
所以,HashMap 需要在达到一定条件时扩容。
2. 两个重要参数
例如:
参数:初始容量;默认值:16;含义:数组默认初始长度
参数:负载因子;默认值:0.75;含义:判断是否需要扩容的比例
16 * 0.75 = 12
也就是说,默认情况下,HashMap 的扩容阈值是 12
3. 什么时候扩容?
假设现在有一个 HashMap:
• 数组长度:16
• 扩容阈值:12
插入数据的过程
当前元素数量
达到阈值后的元素数量:12 → 插入第 13 个元素后,size 超过阈值并触发扩容
原数组长度:16 → 扩容后:32
默认情况下,容量为 16、负载因子为 0.75,阈值是 12;插入第 13 个键值对后,元素数量超过阈值,会触发扩容。默认构造时数组还没有立即创建,第一次 put() 时才初始化。
4. 扩容后发生什么?
JDK 8 中,HashMap 扩容时通常会将数组长度扩大为原来的两倍。
例如:
• 原来:16
• 扩容后:32
扩容后,原来桶中的数据需要重新分布到新数组中。
八、HashMap 的线程安全问题 · 1. 什么是线程安全?
先理解一个概念:
假设多个线程同时操作同一个 HashMap:
• 线程 A:往里面添加数据。
• 线程 B:也往里面添加数据。
• 线程 C:同时读取数据。
如果多个线程同时修改同一个 HashMap,它不会自动协调这些并发操作,因此不能保证更新都按预期完成,也不能把它当作线程安全的集合使用。
这就是线程安全问题。
2. HashMap 为什么线程不安全?
核心原因:HashMap 没有提供并发访问时的线程安全保障。
多个线程同时调用 put(),即使写入不同的 Key,也不能仅凭单次调用看起来正常,就认为整个 HashMap 支持并发修改。它没有提供并发访问时的同步保障;需要并发使用时,应选择合适的同步方案或使用 ConcurrentHashMap。
3. 怎么解决?
Java 中常见的选择有三个:
集合:HashMap;线程安全:否;特点:普通场景使用
集合:Hashtable;线程安全:是;特点:使用 synchronized,性能和并发扩展性较差
集合:ConcurrentHashMap;线程安全:是;特点:专门为并发场景设计
九、HashMap 的 equals() 和 hashCode()
HashMap 的 Key 为什么要重写 equals() 和 hashCode()?
1. 先理解一个问题
假设我们创建两个内容相同的 String:
String key1 = new String("Java");
String key2 = new String("Java");
System.out.println(key1 == key2);
System.out.println(key1.equals(key2));输出:
false
true原因:
• ==:比较两个对象是不是同一个对象。
• equals():String 重写了这个方法,用来比较字符串内容。
也就是说,两个对象虽然不是同一个对象,但内容可以相同。
2. HashMap 如何判断 Key 是否相同?
HashMap 判断两个 Key 是否相同时,主要经过两个步骤:
1. 比较 hash 值,判断是否可能是同一个 Key。
2. 如果哈希值相同,再通过 == 或 equals() 判断 Key 是否相同。
注意:哈希值相同,不代表 Key 一定相同。
例如:
map.put("Java", 100);
map.put("Go", 200);即使两个 Key 的哈希值发生冲突,HashMap 也会进一步判断它们是否相等。
3. 为什么要重写 hashCode() 和 equals()?
假设我们自定义一个 User 类:
class User {
String name;
User(String name) {
this.name = name;
}
}创建两个 User:
User user1 = new User("Kevin");
User user2 = new User("Kevin");如果直接使用默认的 equals() 和 hashCode(),它们不会按照 name 的内容来判断相等。
因此,如果希望两个 name 相同的 User 被 HashMap 识别为同一个 Key,就需要重写这两个方法。
必须遵守的规则:
• 两个对象通过 equals() 判断相等,它们的 hashCode() 必须相同。
• 两个对象的 hashCode() 相同,不代表它们的 equals() 一定相等。
十、HashMap 中高频面试题 · 一、底层数据结构 · 1. HashMap 底层数据结构是什么?
JDK 8 中,HashMap 底层采用数组 + 链表 + 红黑树。
• 数组:用于存储数据,通过下标快速定位。
• 链表:解决哈希冲突。
• 红黑树:当链表过长且满足树化条件时转换,提高查询效率。
2. HashMap 如何解决哈希冲突?
HashMap 使用链地址法解决哈希冲突。
当不同 Key 计算出相同的数组下标时,会将这些节点存储在同一个桶中,通过链表连接。当满足树化条件时,可以转换为红黑树。
3. HashMap 为什么使用红黑树?
当链表过长时,查询效率会下降。
红黑树是一种自平衡二叉搜索树,可以提高查询效率。树化后,查询时间复杂度通常为 O(log n)。
二、哈希计算与存取流程 · 4. HashMap 的哈希扰动是什么?为什么需要它?
JDK 8 中,HashMap 会对原始哈希值进行扰动处理,让哈希值的高位参与低位计算,帮助 Key 分布得更均匀。
核心代码:
static final int hash(Object key) {
int h;
return (key == null) ? 0 :
(h = key.hashCode()) ^ (h >>> 16);
}5. HashMap 如何计算数组下标?为什么使用位运算?
HashMap 使用:
index = (n - 1) & hash;其中 n 是数组长度,hash 是经过扰动处理后的哈希值。
因为数组长度通常是 2 的幂次方,所以可以使用位运算代替取模运算,提高计算效率。
6. HashMap 的 put() 方法执行流程是什么?
1. 计算 Key 的哈希值。
2. 计算数组下标。
3. 判断对应桶是否为空,为空则直接插入。
4. 如果不为空,判断 Key 是否相同。
5. Key 相同则更新 Value,不同则处理哈希冲突。
6. 根据条件进行树化或扩容。
7. HashMap 的 get() 方法执行流程是什么?
1. 计算 Key 的哈希值。
2. 计算数组下标,找到对应桶。
3. 判断节点的 Key 是否相同。
4. 如果相同,直接返回 Value。
5. 如果不同,继续遍历链表或查询红黑树。
8. HashMap 如何判断两个 Key 是否相同?
HashMap 首先比较哈希值,如果哈希值相同,再通过 == 或 equals() 判断 Key 是否相同。
哈希值相同不代表 Key 一定相同。
三、扩容与红黑树机制 · 9. HashMap 默认初始容量和负载因子是多少?
• 默认初始容量:16。
• 默认负载因子:0.75。
注意:默认构造 HashMap 时不会立即创建长度为16的数组,第一次 put() 时才会初始化。
10. HashMap 什么时候扩容?扩容后容量变成多少?
扩容阈值计算公式:
threshold = capacity * loadFactor;默认情况下:
16 * 0.75 = 12当插入元素后,元素数量超过扩容阈值时,会触发扩容。
扩容后数组容量通常变为原来的两倍,例如 16 扩大为 32。
11. HashMap 扩容后,原来的数据如何处理?
扩容后,原数组中的节点需要重新分布到新数组中。
JDK 8 做了优化,通过原来的容量判断节点的位置:节点要么留在原索引,要么移动到原索引加旧容量的位置。
12. HashMap 什么时候转换为红黑树?
主要参数:
• 树化阈值:8。
• 退化阈值:6。
• 最小树化容量:64。
当链表达到树化条件时,如果数组容量小于64,会优先扩容;满足容量条件后才会树化。
四、线程安全与对象比较 · 13. HashMap 是线程安全的吗?如何解决?
HashMap 是线程不安全的。
多个线程同时修改数据时,HashMap 不会替它们协调操作,也不保证并发修改的结果正确。
如果需要在多线程环境下使用线程安全的 Map,通常选择 ConcurrentHashMap。
14. HashMap、Hashtable 和 ConcurrentHashMap 有什么区别?
• HashMap:线程不安全,适合普通场景。
• Hashtable:线程安全,主要通过 synchronized 保证线程安全。
• ConcurrentHashMap:线程安全,专门为并发场景设计,并发性能更好。
15. 为什么 HashMap 的 Key 需要重写 equals() 和 hashCode()?
HashMap 使用 hashCode() 计算哈希值,通过 equals() 判断 Key 是否相等。
如果自定义对象作为 Key,需要根据业务需求正确重写这两个方法。
需要遵守的规则:
• 两个对象通过 equals() 判断相等,它们的 hashCode() 必须相同。
• 两个对象 hashCode() 相同,不代表 equals() 一定相等。