NOTES · 学习笔记

从 0 到 1 理解 HashMap 底层原理

Java约 12 分钟

本文的实现细节以 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 = 15

15 的二进制:

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() 一定相等。