为什么所有面试官都爱追问 HashMap / HashSet？你真的搞懂它们在 JVM 里都干了些什么吗？
开篇语
哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛
今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。
我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。
小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！
一、前言：别装了，HashMap 你真懂吗？
说句可能有点扎心的话：
很多人写 Java 写了好几年，HashMap / HashSet 用得飞起，一到面试官问一句——
“那你给我讲讲 HashMap 的底层实现吧，从 put 开始说。”
当场 CPU 过载：
- “嗯……它是个哈希表。”
- “时间复杂度大概是 O(1) 吧。”
- “底层好像是数组加链表？”
然后就，没了。🌚
今天我们就从全栈开发者的视角，把 HashMap / HashSet 的底层原理、常见面试套路、真实项目里容易踩的坑，全都掰开揉碎，顺便写点手撸版本的简易 HashMap，让你以后再被问到这题：
不仅能讲原理，还能带点“情绪”和“故事”。
二、先从“你平时到底怎么用它们”说起
不要一上来就“JDK8、红黑树、扰动函数”——太生硬。面试官往往会先从你日常用法切入，看你是不是真的写过项目。
2.1 常见使用方式
// HashMap 常规用法
Map<String, Integer> ageMap = new HashMap<>();
ageMap.put("Alice", 18);
ageMap.put("Bob", 20);
ageMap.put("Alice", 19); // 会覆盖旧值
System.out.println(ageMap.get("Alice")); // 19
System.out.println(ageMap.containsKey("Bob")); // true
System.out.println(ageMap.size()); // 2
// HashSet 常规用法
Set<String> set = new HashSet<>();
set.add("Java");
set.add("Java"); // 不会重复
set.add("Python");
System.out.println(set); // [Java, Python]（顺序不保证）
这里其实已经藏着几个面试点了：
HashMap的 key 是唯一的，后 put 会覆盖前面的值（那它怎么做到“覆盖”的？👉 跟 equals / hashCode 有关）。HashSet是不允许重复元素的，那它到底是怎么判断“重复”的？（HashSet 底层其实是用 HashMap 实现的）。- 两者都不保证顺序——为什么？（因为底层是哈希表，按 hash 分桶，不是按插入顺序；要顺序得用
LinkedHashMap/LinkedHashSet）。
三、从数组到哈希表：HashMap 的灵魂三件套
理解 HashMap 前，先记住三个关键概念：
- 哈希函数（hash function）：把 key 映射成一个 int 值（
hashCode()）。 - 桶（bucket）数组：本质上是一个数组
Node<K,V>[] table。 - 冲突解决：多个 key 落在同一个桶里怎么办？——链表 or 红黑树。
3.1 HashMap 底层核心结构（JDK8 简化版）
// JDK8 中 HashMap 的基本节点结构（简化版）
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // 计算后的哈希值
final K key;
V value;
Node<K, V> next; // 指向下一个节点（链表）
}
HashMap 里最重要的就是这个数组：
transient Node<K, V>[] table;
你可以把它想象成一个：
“若干个桶组成的数组，每个桶里又可能挂着一条链表，链表太长了还会升级成红黑树”。
四、put 的全过程：面试高频题“从 put 讲起”
面试官常说的经典台词：
“那你从
put开始给我讲讲 HashMap 的执行过程。”
4.1 用一段伪代码走一遍 put 流程
下面是一个非常简化、易懂版本的伪代码（不是 JDK 源码原样，但逻辑接近）：
public V put(K key, V value) {
// 1. 第一次 put 时才真正创建 table（懒加载）
if (table == null || table.length == 0) {
resize(); // 初始化数组
}
// 2. 计算 hash 值（JDK8 会对 hashCode 做一次扰动）
int hash = hash(key);
// 3. 计算应该落在哪个桶（数组下标）
int index = (table.length - 1) & hash;
// 4. 取出这个桶的头结点
Node<K, V> head = table[index];
// 5. 如果这个桶是空的，直接放进去
if (head == null) {
table[index] = new Node<>(hash, key, value, null);
size++;
} else {
// 6. 桶不空，说明发生了“哈希冲突”，在链表/树上找有没有相同 key
Node<K, V> node = head;
while (true) {
// key 相同 => 覆盖 value
if (node.hash == hash && (node.key == key || node.key.equals(key))) {
V oldValue = node.value;
node.value = value;
return oldValue;
}
if (node.next == null) {
// 走到尾巴了，还没找到相同 key => 追加新节点
node.next = new Node<>(hash, key, value, null);
size++;
break;
}
node = node.next;
}
// 7. 链表长度如果超过一个阈值（JDK8 默认 8），就可能转成红黑树
// treeifyBin(index);
}
// 8. 判断是否需要扩容：size > threshold (= capacity * loadFactor)
if (size > threshold) {
resize();
}
return null;
}
面试时你可以这样串起来说：
先看 table 是否初始化，没有就先扩容初始化；
然后计算 key 的 hash，再根据数组长度算出它该放在第几个桶；
如果这个桶是空的，直接放一个新节点；
如果不为空，说明发生哈希碰撞，就在这个桶的链表/红黑树里挨个比对：
- 如果发现有相同 key，就覆盖 value；
- 如果没有，就把新节点挂到尾部；
插入完成后，判断当前 size 是否超过阈值（capacity * loadFactor），超过就扩容；
JDK8 里，如果同一个桶的链表长度超过 8，还会考虑把链表转成红黑树，提高查找效率。
说到这一步，基本已经 > 80% 的候选人了。
五、get 的过程：为什么能做到接近 O(1)？
public V get(Object key) {
Node<K, V> node = getNode(hash(key), key);
return node == null ? null : node.value;
}
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
// 1. table 不为空 且 对应桶的第一个节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2. 先比较桶的第一个节点（命中率高）
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k)))) {
return first;
}
// 3. 继续在链表/红黑树中找
if ((e = first.next) != null) {
// 如果是树节点，用树的方式查找
// 否则就是普通链表遍历
// 这里简化写法：
do {
if (e.hash == hash && (e.key == key || key.equals(e.key))) {
return e;
}
} while ((e = e.next) != null);
}
}
return null;
}
简单说：先通过 hash 快速定位桶，再在桶内部查找。
如果桶内的数据结构是红黑树，那么查找就是 O(log n)；
若是普通链表，则最坏是 O(n)，但平均来说还挺快——只要哈希分布得够均匀。
六、扩容机制：为什么 2 的幂次方这么重要？
另一个常被问到的问题：
“HashMap 为什么容量总是 2 的幂次方？扩容的时候是怎么迁移数据的？”
6.1 2 的幂的好处
index = (n - 1) & hash
这里的 n 是数组长度（capacity），如果 n 是 2 的幂，比如 16、32、64，那么 (n - 1) 的二进制形式全是 1：
16 = 10000(2)16 - 1 = 01111(2)
(n - 1) & hash 就相当于取 hash 的低几位，这样：
- 运算速度快（位运算）
- 分布还比较均匀
6.2 扩容时如何重新分布元素（JDK8 的小聪明）
当容量从 oldCap 扩成 newCap = oldCap * 2 时，每个元素要么还在原位置，要么移动到“原位置 + oldCap”。
比如原来数组长度是 16，扩容到 32：
- 原来在 index = 5 的元素
- 新位置要么还是 5，要么变成 5 + 16 = 21
这个优化可以减少重新 hash 的计算，提升扩容性能。
你在面试中提到这一点，会非常加分。
七、HashSet 的底层：其实就是“只用 key 的 HashMap”
面试官很喜欢问：
“HashSet 底层是怎么实现的？”
7.1 HashSet 如何存数据？
其实非常简单粗暴：用一个 HashMap，当作 Set 的底层容器。
简化版源码思路如下：
public class HashSet<E> extends AbstractSet<E> implements Set<E> {
// 真正存东西的是这个 Map
private transient HashMap<E, Object> map;
// 所有 value 都用同一个哨兵对象
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
@Override
public boolean add(E e) {
// key = e，value = PRESENT（没意义，只占个位）
return map.put(e, PRESENT) == null;
}
@Override
public boolean contains(Object o) {
return map.containsKey(o);
}
@Override
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}
所以 HashSet 的“去重”和“判断元素是否存在”，完全是借用 HashMap 的key 唯一性和 hashCode + equals 逻辑。
——这也是为什么：自定义对象放到 HashSet 里必须重写 hashCode 和 equals。
八、hashCode / equals：你要是说不清这个，基本凉一半
面试必问：
“HashMap 判断两个 key 相等的依据是什么？”
“为什么重写了 equals 还要重写 hashCode？”
8.1 HashMap 判断 key 是否“相等”的条件
hashCode相等equals返回 true
顺序上，一般是：
- 先比 hash（快）
- 再比 equals（精确判断）
8.2 为什么要同时重写？
看一个错误示例：
class User {
String name;
public User(String name) {
this.name = name;
}
// 注意：这里没有重写 equals 和 hashCode
}
public class Demo {
public static void main(String[] args) {
Set<User> set = new HashSet<>();
set.add(new User("Tom"));
set.add(new User("Tom"));
System.out.println(set.size()); // 很可能是 2，而不是 1
}
}
因为默认的 equals 和 hashCode 来自 Object，是基于对象地址的，两个 new User("Tom") 地址不同，自然被认为是两个不同的元素。
正确做法：重写 equals 和 hashCode，让“业务上认为相等”的对象真的被认为相等。
class User {
String name;
public User(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof User)) return false;
User user = (User) o;
return name != null && name.equals(user.name);
}
@Override
public int hashCode() {
return name == null ? 0 : name.hashCode();
}
}
九、几道高频面试题，帮你提前背台词 😏
9.1 HashMap 线程安全吗？为什么？
答法建议：
-
HashMap在多线程环境下不是线程安全的。 -
并发 put 时可能导致：
- 数据丢失（覆盖）
- 扩容时出现链表丢失、死循环（早期 JDK) 等问题（JDK8 已优化结构，但依然不推荐并发使用）。
-
如果需要线程安全，可以使用：
Collections.synchronizedMap(new HashMap<>())（粗暴的同步，性能一般）；- 或者用
ConcurrentHashMap，它做了细粒度锁分段 / CAS 等优化（JDK8 使用synchronized + CAS + Node/TreeBin等机制）。
9.2 HashMap 和 Hashtable 有什么区别？
要点可以这样说：
-
线程安全性：
Hashtable是线程安全的，几乎所有方法都加了synchronized；HashMap不是线程安全的。
-
性能：
Hashtable粗暴锁，性能较差；- 高并发场景推荐
ConcurrentHashMap，而不是Hashtable。
-
null 支持：
Hashtable不允许 key 或 value 为null；HashMap允许一个nullkey，多值null。
-
历史包袱：
Hashtable属于比较老的类（JDK1.0），现在基本算是“历史遗留”；- 新项目都用
HashMap / ConcurrentHashMap。
9.3 HashMap JDK7 与 JDK8 有什么差别？
你要是能说出下面几点，面试官会觉得你真写过点东西：
-
链表插入方式
- JDK7：头插法（可能导致扩容时链表反转，在多线程下有死链问题）。
- JDK8：尾插法。
-
桶内数据结构
- JDK7：数组 + 链表。
- JDK8：数组 + 链表 + 红黑树（当链表长度大于 8 时可能转树）。
-
扩容细节 & hash 扰动方式
- JDK8 对 hash 扰动和扩容迁移做了优化，逻辑更简洁。
十、几个容易被忽略但很“致命”的坑
10.1 把“可变对象”当作 key
比如你把一个包含 List 的对象当 key，结果中途改了里面的字段——那就再也找不到这个 key 了。
示意代码：
class Person {
String name;
int age;
// equals / hashCode 基于 name + age
// 略...
}
public static void main(String[] args) {
Map<Person, String> map = new HashMap<>();
Person p = new Person("Tom", 18);
map.put(p, "Student");
// 中途修改了 key 的字段
p.age = 20;
// 这时再去 get，很可能拿不到
System.out.println(map.get(p)); // 可能是 null
}
原因是：hashCode 变了，但它还在旧桶里，就像你搬了家但不改快递地址，快递员压根找不到你。
面试时可以顺带说一句：
“所以业务里一般不推荐把可变对象当 key，或者至少要保证参与 hash 的字段在存进 Map 后不要再改。”
10.2 初始容量设置不当导致频繁扩容
默认构造函数：
Map<String, Object> map = new HashMap<>();
默认初始容量是 16，负载因子 loadFactor = 0.75。
能容纳的元素数量阈值（threshold）是：16 * 0.75 = 12。
如果你预计要放 10 万条数据，结果还用默认配置，那 HashMap 会反复扩容、迁移，非常浪费时间。
更好的做法：
// 粗略估算一下：需要 100_000 个元素
// 容量建议 >= 100000 / 0.75 ≈ 133334 => 2 的幂 => 131072 或 262144
Map<String, Object> map = new HashMap<>(131072);
面试时可以顺带说：
“我们在实际开发中，如果能预估数据量，会选择手动指定一个合理的初始容量，减少扩容次数。”
十一、手撸一个极简版 MyHashMap，展示你真懂
如果你在面试中说：“其实我之前自己撸过一个简化版的 HashMap，用数组 + 链表实现的。”
——这话一出，感觉就不一样了 😏
下面我们写一个极简版，只为了说明“思想”，不考虑扩容、红黑树之类的细节。
public class MyHashMap<K, V> {
// 简单起见，固定容量
private static final int DEFAULT_CAPACITY = 16;
static class Node<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private Node<K, V>[] table;
@SuppressWarnings("unchecked")
public MyHashMap() {
table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
}
private int hash(Object key) {
if (key == null) return 0;
int h = key.hashCode();
// 简化版扰动：高 16 位异或低 16 位
return h ^ (h >>> 16);
}
private int index(int hash) {
return (DEFAULT_CAPACITY - 1) & hash;
}
public void put(K key, V value) {
int hash = hash(key);
int idx = index(hash);
Node<K, V> head = table[idx];
if (head == null) {
table[idx] = new Node<>(hash, key, value, null);
return;
}
Node<K, V> node = head;
while (true) {
// key 已存在 => 覆盖
if (node.hash == hash &&
(node.key == key || (key != null && key.equals(node.key)))) {
node.value = value;
return;
}
if (node.next == null) {
node.next = new Node<>(hash, key, value, null);
return;
}
node = node.next;
}
}
public V get(K key) {
int hash = hash(key);
int idx = index(hash);
Node<K, V> node = table[idx];
while (node != null) {
if (node.hash == hash &&
(node.key == key || (key != null && key.equals(node.key)))) {
return node.value;
}
node = node.next;
}
return null;
}
public static void main(String[] args) {
MyHashMap<String, Integer> map = new MyHashMap<>();
map.put("Java", 1);
map.put("Python", 2);
map.put("Java", 3);
System.out.println(map.get("Java")); // 3
System.out.println(map.get("Python")); // 2
System.out.println(map.get("Go")); // null
}
}
你可以在面试中顺带一句：
“我自己实现的版本当然很简陋，没做扩容、负载因子、红黑树这些，但通过自己写一遍，对 HashMap 整体结构会理解得更清晰。”
这就不是“背八股”，而是“真动过手”。
十二、面试时如何“有剧情”地讲 HashMap / HashSet？
如果你想在面试中既显得专业，又别太机械，我建议你可以用这种讲述顺序（你可以照着练一下口径）：
-
从日常使用切入：
“平时我用 HashMap 主要是做 xxx，比如缓存某些配置，或者按 id 存用户信息。” -
过渡到底层结构：
“HashMap 底层其实就是数组加链表（再加红黑树），可以简单理解为一个桶数组，每个桶里是一条链表，链表太长就转树。” -
详细展开 put/get 流程：
“以 put 为例，大概会经历 hash 计算、定位桶、判断是否冲突、链表/树插入、必要时扩容等步骤……”（把前面说的八股讲一遍）。 -
顺带带出 HashSet：
“HashSet 底层其实就是用 HashMap 来存 key，value 是一个固定的哨兵对象，所以它的去重完全依赖 hashCode + equals。” -
补充几个坑 & 性能点：
- 自定义对象不重写 equals/hashCode 导致重复 / 查不到
- 可变对象当 key 的问题
- 合理设置初始容量、防止频繁扩容
-
最后点一嘴并发场景：
“在多线程下我一般不会直接用 HashMap，而是用 ConcurrentHashMap，或者根据场景用本地缓存 / 分布式缓存等方式。”
整个讲完，面试官基本会觉得：
“好，这人不是背一段话，是有体系的。”
十三、最后小结：HashMap / HashSet，你得记住这几句
如果你现在有点信息过载，那我帮你压缩成几条“记忆点”，面试前看一眼就能回魂那种👇
-
HashMap 底层：数组 + 链表 + 红黑树，利用 hash 定位桶，再在桶内查找。
-
put 流程：
- 首次使用 -> 初始化 table
- 计算 hash -> 定位 index
- 桶为空 -> 直接插入
- 桶不空 -> 遍历链表/树，key 相同则覆盖，否则插到尾部
- 链表太长 -> 可能转红黑树
- size 超过阈值 -> 扩容
-
HashSet 底层：用 HashMap 存储元素，元素当 key，所有 value 共用一个固定对象。
-
hashCode + equals：
- HashMap 判断 key 相等 =
hashCode 相等 && equals 为 true - 重写 equals 必须重写 hashCode，否则集合行为会非常诡异。
- HashMap 判断 key 相等 =
-
线程安全：
- HashMap 不是线程安全
- 高并发用 ConcurrentHashMap
- Hashtable 老古董，了解就行。
-
常见坑：
- 可变对象当 key
- 初始容量估计不足导致频繁扩容
- 忘了重写 hashCode / equals
… …
文末
好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。
… …
学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！
wished for you successed ！！！
⭐️若喜欢我，就请关注我叭。
⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。
版权声明：本文由作者原创，转载请注明出处，谢谢支持！
- 点赞
- 收藏
- 关注作者
评论（0）