前言

前面几篇我们学习了 String 相关的高频面试题。

这一篇开始进入 Java 集合中非常经典的问题：HashMap。

HashMap 是 Java 面试中几乎绕不开的知识点。很多面试官都会从一个简单问题开始问：

你说一下 HashMap 的底层原理。

然后继续追问：

• HashMap 底层数据结构是什么？
• put 方法大概流程是什么？
• 为什么数组长度一般是 2 的幂？
• 哈希冲突怎么解决？
• 什么时候链表会转红黑树？
• 扩容机制是什么？
• 为什么重写 equals 也要重写 hashCode？
• HashMap 线程安全吗？

这一篇我们就按面试回答的思路，把 HashMap 的核心知识点系统梳理一遍。

一、HashMap 是什么？

HashMap 是 Java 中非常常用的一种集合，用来保存键值对。

也就是：

key -> value

比如：

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

map.put("username", "zhangsan");
map.put("password", "123456");
map.put("phone", "13800000000");

这里：

username -> zhangsan
password -> 123456
phone    -> 13800000000

HashMap 的特点是：

1. 按 key 存储 value
2. 根据 key 查询速度快
3. key 不能重复
4. value 可以重复
5. key 和 value 都可以为 null
6. 线程不安全

二、HashMap 的基本使用

1. 添加数据

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

map.put("name", "张三");
map.put("gender", "男");
map.put("city", "北京");

2. 根据 key 获取 value

String name = map.get("name");

System.out.println(name);

输出：

张三

3. key 重复会覆盖 value

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

map.put("name", "张三");
map.put("name", "李四");

System.out.println(map.get("name"));

输出：

李四

因为 HashMap 中 key 不能重复。

当再次放入相同 key 时，新的 value 会覆盖旧的 value。

4. 判断 key 是否存在

if (map.containsKey("name")) {
    System.out.println("存在 name 这个 key");
}

5. 遍历 HashMap

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

map.put("name", "张三");
map.put("gender", "男");
map.put("city", "北京");

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

这种写法是比较常见的遍历方式。

三、HashMap 底层数据结构

在 JDK 1.8 中，HashMap 底层主要是：

数组 + 链表 + 红黑树

可以简单理解成：

HashMap
  └── Node[] table 数组
        ├── Node 链表
        ├── Node 链表
        └── TreeNode 红黑树

默认情况下，HashMap 使用数组保存数据。

当多个 key 计算后落到同一个数组位置时，就会形成链表。

如果链表太长，并且数组容量达到一定条件，就会把链表转换成红黑树，提高查询效率。

所以 JDK 1.8 的 HashMap 结构可以总结为：

数组是主体，链表用来解决哈希冲突，红黑树用来优化过长链表的查询性能。

四、HashMap 中的 Node 是什么？

HashMap 中保存的每一个键值对，本质上都是一个节点。

可以简单理解成：

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

每个 Node 中保存了：

字段	含义
hash	key 的哈希值
key	键
value	值
next	指向下一个节点

如果多个元素落在同一个数组位置，就通过 next 连接成链表。

五、HashMap 的 put 流程

我们来看这段代码：

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

map.put("name", "张三");

put 大概流程可以理解为：

1. 根据 key 计算 hash 值
2. 根据 hash 值计算数组下标
3. 如果该位置为空，直接放入新节点
4. 如果该位置不为空，说明发生哈希冲突
5. 判断 key 是否相同
6. key 相同则覆盖 value
7. key 不同则插入链表或红黑树
8. 插入后判断是否需要扩容

下面分步骤讲。

六、第一步：计算 key 的 hash 值

HashMap 存储数据时，首先会根据 key 计算 hash 值。

可以简单理解为：

int hash = key.hashCode();

不过 HashMap 不是直接使用 hashCode()，它还会做一次扰动计算。

JDK 1.8 中大概类似：

static final int hash(Object key) {
    int h;
    return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里：

h ^ (h >>> 16)

是为了让 hash 值的高位和低位都参与计算，减少哈希冲突。

初学阶段不用死记源码，但要知道：

HashMap 会根据 key 的 hashCode 计算出一个 hash 值，并通过扰动函数降低冲突概率。

七、第二步：计算数组下标

有了 hash 值之后，HashMap 需要决定这个键值对放到数组哪个位置。

大概计算方式是：

index = (table.length - 1) & hash;

比如数组长度是 16，那么下标范围就是：

0 到 15

为什么使用：

(table.length - 1) & hash

而不是直接取模？

因为位运算效率更高。

当数组长度是 2 的幂时：

hash % length

可以等价优化成：

hash & (length - 1)

所以 HashMap 的数组长度通常是 2 的幂，比如：

16、32、64、128

八、为什么 HashMap 容量是 2 的幂？

这是一个高频追问。

主要原因有两个：

1. 方便用位运算计算下标

当数组长度是 2 的幂时：

index = hash & (length - 1)

可以让计算结果均匀分布在数组范围内。

比如长度是 16：

length - 1 = 15
二进制：0000 1111

和 hash 做与运算后，结果一定在 0 到 15 之间。

2. 扩容后元素迁移更高效

JDK 1.8 中，HashMap 扩容时容量会变成原来的 2 倍。

元素新位置要么保持不变，要么移动到：

原位置 + oldCap

这样扩容迁移效率更高，不需要重新完整计算所有位置。

所以容量设计成 2 的幂，是为了提高计算下标和扩容迁移的效率。

九、什么是哈希冲突？

哈希冲突就是：

不同的 key 经过计算后，落到了数组的同一个位置。

比如数组下标是 3 的位置，已经有一个节点了：

table[3] -> Node("name", "张三")

现在又来了一个 key，计算出来的下标也是 3：

table[3] -> Node("name", "张三")
            Node("city", "北京")

这就发生了哈希冲突。

哈希冲突无法完全避免。

因为 hash 值空间很大，但数组长度有限，不同 key 落到同一个数组位置是正常情况。

十、HashMap 如何解决哈希冲突？

在 JDK 1.8 中，HashMap 主要通过：

链表 + 红黑树

解决哈希冲突。

如果数组某个位置已经有节点，新节点会挂到这个位置对应的链表中。

结构类似：

table[3] -> Node1 -> Node2 -> Node3

查询时，先定位数组下标，再遍历链表比较 key。

如果链表很短，效率还可以。

但是如果链表很长，查询效率就会下降。

所以 JDK 1.8 做了优化：当链表达到一定长度时，会转换成红黑树。

十一、什么时候链表会转成红黑树？

JDK 1.8 中，链表转红黑树大致需要满足两个条件：

链表长度 >= 8
数组容量 >= 64

也就是：

TREEIFY_THRESHOLD = 8
MIN_TREEIFY_CAPACITY = 64

如果链表长度达到 8，但是数组容量还小于 64，HashMap 通常会优先扩容，而不是马上树化。

为什么？

因为数组容量太小时，链表长可能是因为数组太小导致冲突多。

这时候扩容可能就能减少冲突。

只有数组容量已经比较大，链表仍然很长，才会转成红黑树。

十二、为什么要转成红黑树？

链表查询的时间复杂度是：

O(n)

如果链表很长，查询会比较慢。

红黑树查询的时间复杂度大概是：

O(log n)

所以链表过长时转红黑树，可以提高查询效率。

不过红黑树本身结构更复杂，维护成本也更高。

所以 HashMap 不会一冲突就转红黑树，而是链表达到一定长度后才转换。

十三、HashMap 的扩容机制

HashMap 默认初始容量是：

16

默认负载因子是：

0.75

扩容阈值是：

容量 * 负载因子

所以默认情况下：

16 * 0.75 = 12

也就是说，当元素数量超过 12 时，HashMap 会扩容。

扩容时容量变成原来的 2 倍：

16 -> 32 -> 64 -> 128

扩容后，原来的元素需要重新分布到新数组中。

这一步叫做 rehash 或 resize。

十四、负载因子为什么默认是 0.75？

负载因子表示数组装到什么程度时开始扩容。

如果负载因子太小，比如 0.5：

数组还没装多少就扩容
空间浪费比较多

如果负载因子太大，比如 1：

数组装得太满才扩容
哈希冲突可能增加
链表可能变长
查询效率下降

默认值 0.75 是在空间利用率和查询效率之间做的折中。

所以一般情况下，不需要手动修改负载因子。

十五、HashMap 的 get 流程

看代码：

String value = map.get("name");

get 大概流程是：

1. 根据 key 计算 hash 值
2. 根据 hash 值计算数组下标
3. 找到数组对应位置
4. 如果第一个节点 key 匹配，直接返回 value
5. 如果不匹配，继续在链表或红黑树中查找
6. 找到则返回 value
7. 找不到返回 null

注意：

map.get(key)

返回 null 有两种可能：

1. key 不存在
2. key 存在，但 value 本身就是 null

如果需要区分，可以使用：

map.containsKey(key)

十六、为什么重写 equals 也要重写 hashCode？

HashMap 判断 key 是否相同，需要用到：

hashCode + equals

大致逻辑是：

1. 先比较 hash 值
2. hash 值相同，再用 equals 比较 key 是否相等

如果两个对象通过 equals 判断相等，那么它们的 hashCode 也应该相等。

否则放到 HashMap 中可能出现问题。

示例：

public class Student {
    private String name;
    private Integer age;

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Student student = (Student) obj;
        return Objects.equals(name, student.name)
                && Objects.equals(age, student.age);
    }
}

如果只重写 equals，不重写 hashCode，两个内容相同的对象可能 hash 值不同。

这样它们可能被放到不同数组位置，HashMap 就无法正确判断它们是同一个 key。

所以实际开发中：

只要重写 equals，通常就必须同时重写 hashCode。

完整写法：

import java.util.Objects;

public class Student {
    private String name;
    private Integer age;

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Student student = (Student) obj;

        return Objects.equals(name, student.name)
                && Objects.equals(age, student.age);
    }

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

十七、HashMap 能不能存 null？

可以。

HashMap 允许：

一个 null key
多个 null value

示例：

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

map.put(null, "空key");
map.put("name", null);
map.put("city", null);

System.out.println(map.get(null));
System.out.println(map.get("name"));

输出：

空key
null

为什么只能有一个 null key？

因为 key 不能重复。

当再次 put 一个 null key 时，会覆盖原来的值。

map.put(null, "A");
map.put(null, "B");

System.out.println(map.get(null));

输出：

B

十八、HashMap 是线程安全的吗？

HashMap 不是线程安全的。

如果多个线程同时对同一个 HashMap 进行 put、remove 等修改操作，可能会出现数据不一致。

比如：

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

Thread t1 = new Thread(() -> {
    for (int i = 0; i < 10000; i++) {
        map.put(i, i);
    }
});

Thread t2 = new Thread(() -> {
    for (int i = 10000; i < 20000; i++) {
        map.put(i, i);
    }
});

多个线程同时修改同一个 HashMap，可能出现异常结果。

如果需要线程安全的 Map，可以考虑：

ConcurrentHashMap

或者：

Collections.synchronizedMap(new HashMap<>())

不过实际开发中，更推荐使用 ConcurrentHashMap。

十九、HashMap 和 Hashtable 的区别

这个问题也经常被顺手问到。

对比	HashMap	Hashtable
线程安全	不安全	安全
性能	较高	较低
null key/value	允许	不允许
出现时间	较新	较早
推荐使用	常用	较少使用

Hashtable 的很多方法使用了 synchronized，所以线程安全，但性能较低。

现在实际开发中，如果需要线程安全 Map，一般不会选择 Hashtable，而是使用：

ConcurrentHashMap

二十、面试标准回答

如果面试官问：

HashMap 底层原理是什么？

可以这样回答：

JDK 1.8 中，HashMap 底层是数组、链表和红黑树组成的。数组是主体结构，元素会根据 key 的 hash 值计算出数组下标，然后存放到对应位置。

当多个 key 计算出的下标相同时，就会发生哈希冲突。JDK 1.8 中，HashMap 会先用链表解决冲突。如果链表长度达到 8，并且数组容量达到 64，就会把链表转换成红黑树，从而提高查询效率。

put 时，会先根据 key 计算 hash 值，再计算数组下标。如果当前位置为空，就直接插入；如果不为空，就判断 key 是否相同，相同则覆盖 value，不同则插入链表或红黑树中。

HashMap 默认初始容量是 16，默认负载因子是 0.75。当元素数量超过容量乘以负载因子时，会触发扩容，容量变成原来的 2 倍。

另外，HashMap 不是线程安全的。如果多线程环境需要使用 Map，通常会选择 ConcurrentHashMap。

二十一、常见问题总结

1. HashMap 底层一定是数组加链表吗？

JDK 1.8 中是数组、链表、红黑树。

JDK 1.7 主要是数组加链表。

所以面试时最好说明版本：

JDK 1.8 中 HashMap 是数组 + 链表 + 红黑树

2. HashMap 默认容量是多少？

默认初始容量是：

16

3. HashMap 默认负载因子是多少？

默认负载因子是：

0.75

4. 链表什么时候转红黑树？

大致条件是：

链表长度 >= 8
数组容量 >= 64

如果数组容量小于 64，通常优先扩容。

5. HashMap 为什么线程不安全？

因为多个线程同时修改同一个 HashMap 时，没有同步控制，可能导致数据覆盖、结构异常、结果不一致等问题。

6. HashMap 的 key 可以重复吗？

不可以。

如果 put 相同 key，新的 value 会覆盖旧的 value。

7. HashMap 的 value 可以重复吗？

可以。

不同 key 可以对应相同 value。

二十二、实际开发建议

使用 HashMap 时，可以注意下面几点：

1. key 尽量使用不可变对象，比如 String
2. 自定义对象作为 key 时，要重写 equals 和 hashCode
3. 如果能预估数据量，可以指定初始容量，减少扩容
4. 不要在多线程写入场景中直接使用 HashMap
5. 需要线程安全时优先考虑 ConcurrentHashMap
6. 遍历时不要随便在增强 for 中直接修改结构
7. get 返回 null 时，要注意区分 key 不存在和 value 本身为 null
8. 不要只背源码名词，要能讲清楚 put、get、扩容、哈希冲突这几个流程

二十三、总结

这一篇主要学习了 HashMap 的底层原理。

在 JDK 1.8 中，HashMap 底层由数组、链表和红黑树组成。数组负责定位位置，链表解决哈希冲突，红黑树用来优化长链表查询性能。

HashMap 的核心流程就是根据 key 计算 hash，再通过 hash 计算数组下标。put 时，如果位置为空就直接插入，如果发生冲突就比较 key，相同则覆盖，不同则挂到链表或红黑树中。

默认情况下，HashMap 初始容量是 16，负载因子是 0.75，超过阈值会扩容为原来的 2 倍。

面试中讲 HashMap 时，不需要一开始就背大量源码。更重要的是把底层结构、put 流程、哈希冲突、红黑树、扩容机制、线程安全这几个点讲清楚。

下一篇我们继续学习 ArrayList 和 LinkedList 的区别。