zzTzz的博客

引言

HashMap 是 Java 面试中的高频考点，几乎每场 Java 后端面试都会涉及。本文将从底层数据结构出发，深入解析 HashMap 的工作原理，帮助你从容应对面试。

---

一、HashMap 的数据结构

1.1 核心结构

HashMap 在 JDK 1.8 中采用数组 + 链表 + 红黑树的复合结构：

数组: [null, Node1, null, Node3, null, ...]
           ↓
        链表/红黑树
           ↓
       [Key1=Value1] → [Key2=Value2] → ...

1.2 关键字段

字段	含义	默认值
table	Node 数组	null
size	元素个数	0
threshold	扩容阈值	16
loadFactor	负载因子	0.75

1.3 源码节选

// HashMap 核心字段
transient Node<K,V>[] table;
transient int size;
int threshold;
final float loadFactor;

// 默认配置
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;  // 链表转红黑树阈值
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树转链表阈值

---

二、put() 方法的执行流程

2.1 流程图解

put(key, value)
    ↓
计算 hash: (h = key.hashCode()) ^ (h >>> 16)
    ↓
计算索引: (n - 1) & hash
    ↓
数组该位置为空?
    ↓ 是 → 直接插入新 Node
    ↓ 否
key 已存在?
    ↓ 是 → 覆盖旧值
    ↓ 否
链表长度 >= 7?
    ↓ 是 → 转红黑树后插入
    ↓ 否 → 链表尾部插入
    ↓
size > threshold?
    ↓ 是 → 扩容 (resize)
    ↓ 否 → 返回 null

2.2 核心源码分析

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 计算 hash：高 16 位与低 16 位异或，减少碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

---

三、扩容机制（resize）

3.1 扩容时机

当 size > threshold（容量 × 负载因子，默认 16×0.75=12）时触发扩容。

3.2 扩容优化：高位链与低位链

JDK 1.8 的优化：扩容时不需要重新计算 hash，只需要看 hash & oldCap 的结果：

• 结果为 0：索引不变（低位链）
• 结果不为 0：索引 = 原索引 + oldCap（高位链）

---

四、线程安全问题

4.1 HashMap 为什么线程不安全？

问题	原因	后果
数据丢失	多线程同时 put，计算出的索引相同，后插入的覆盖先插入的	数据丢失
死循环	JDK 1.7 扩容时链表头插法导致环形链表	CPU 100%
读写不一致	读取时正好扩容，读到不一致状态	读取脏数据

4.2 线程安全的替代方案

// 推荐：使用 ConcurrentHashMap
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();

---

五、高频面试题与回答技巧

面试题 1：HashMap 的底层原理是什么？

HashMap 底层使用数组 + 链表 + 红黑树的数据结构。当 put 元素时，先计算 key 的 hash 值，再通过 (n-1) & hash 计算出数组索引。如果该位置为空，直接插入；如果已有元素，则比较 key，相同则覆盖，不同则追加到链表尾部。当链表长度超过 8 且数组长度超过 64 时，链表会转换为红黑树以优化查询性能。

---

面试题 2：为什么 HashMap 的容量是 2 的幂次方？

两个原因：

1. 位运算效率高：用 (n-1) & hash 代替 % 取模运算，位运算速度更快。
2. 均匀分布：2 的幂次方减 1 得到全 1 的二进制（如 15 = 1111），能使 hash 值均匀分布在数组中，减少碰撞。

---

面试题 3：HashMap 是线程安全的吗？有什么替代方案？

HashMap 不是线程安全的。多线程环境下可能出现数据丢失或死循环问题。线程安全的替代方案有：

1. ConcurrentHashMap：推荐，使用 CAS + synchronized，锁粒度小，性能高。
2. Collections.synchronizedMap：包装 HashMap，性能较差。
3. Hashtable：不推荐，遗留类，全局加锁性能差。

---

六、总结

核心要点	内容
数据结构	数组 + 链表 + 红黑树（JDK 1.8+）
容量设计	2 的幂次方，支持位运算取模
线程安全	不安全，使用 ConcurrentHashMap 替代
性能优化	链表长度 > 8 转红黑树，查询从 O(n) 到 O(log n)
扩容机制	容量翻倍，元素重新分散到高位/低位链

面试建议：

1. 能够手绘 HashMap 结构图
2. 熟练讲解 put() 方法流程
3. 理解扩容和线程安全原理
4. 对比 HashMap 与 ConcurrentHashMap

掌握这些要点，HashMap 相关的面试题将不再是难点！