前言

HashMap 面试必问，但很多同学答得磕磕巴巴。

什么数组 + 链表 + 红黑树、什么负载因子 0.75、什么线程不安全，这些概念背得很熟，但底层到底怎么实现的，为什么这么设计，说不清楚。

今天我们用图示把 HashMap 给拆解透彻。

HashMap 基本结构

整体架构

HashMap 的核心就是一个 Node 数组，每个数组元素可能是：

HashMap内部结构：

table数组:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │ <- 数组索引
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│null │Node │null │Node │List │null │Tree │null │ <- 存储内容
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
          │           │     │           │
          ▼           ▼     ▼           ▼
      单个节点      单个节点  链表      红黑树

情况1 - 单个节点：
┌──────────────┐
│ key: "name"  │
│ value: "米虫" │
│ hash: 12345  │
│ next: null   │
└──────────────┘

情况2 - 链表（哈希冲突）：
┌────────────┐    ┌────────────┐    ┌────────────┐
│key: "age"  │───▶│key: "city" │───▶│key: "job"  │
│value: 18   │    │value:"上海" │    │value:"码农" │
│hash: 998   │    │hash: 1892  │    │hash: 3721  │
│next: ──────┼────┼────────────┤    │next: null  │
└────────────┘    └────────────┘    └────────────┘
​

哈希函数设计

哈希过程：

1. 计算key的hashCode:
   "mebugs".hashCode() = 123456789

2. HashMap的hash函数处理:
   原始hash: 123456789
   高16位与低16位异或
   
3. 计算数组索引:
   hash & (length-1) = hash & 15 = 9
   所以存储在 table[9] 位置
​

核心操作原理

put 操作流程

put("key", "value") 执行流程：

1. 计算hash值和数组索引
2. 检查table[index]位置
   - 位置为空：直接插入
   - key相同：替换value
   - key不同：链表尾部插入
3. 检查是否需要树化
4. 检查是否需要扩容
​

扩容机制

扩容的关键：容量翻倍后，元素要么在原位置，要么在"原位置+oldCap"位置

判断方法：hash & oldCap
- 结果为0：位置不变
- 结果非0：新位置 = 原位置 + oldCap

链表会被拆分成两个链表：
- 低位链表：留在原位置
- 高位链表：移动到新位置
​

线程安全问题

问题根源

HashMap 不是线程安全的，根本原因是操作不是原子的：

// put操作的关键步骤
if (table[i] == null)           // 步骤1：检查
    table[i] = newNode(...);    // 步骤2：设置
​

多线程执行时的时序问题：

时间轴分析：

线程T1                     线程T2
────────────────────────────────────────
hash("key1") → index=5
检查 table[5] == null ✓
                              hash("key2") → index=5
                              检查 table[5] == null ✓
                              table[5] = Node2
table[5] = Node1            
                            
结果：Node2被覆盖，数据丢失！
​

主要问题类型

1. 数据丢失

put操作覆盖问题：

初始状态：table[0] = null

T1: put("a", 1) → 准备写入table[0]
T2: put("b", 2) → 也准备写入table[0]

结果：只有一个数据存活，另一个丢失
​

2. 扩容时的问题

扩容过程中的数据可见性问题：

T1开始扩容：创建新数组，迁移数据...
T2执行操作：可能看到旧table、新table或null

导致：
- get返回null（明明刚put的）
- 数据不一致
- 数组越界异常
​

3. 无限循环（JDK 1.7）

JDK 1.7头插法导致的环形链表：

扩容前：A → B → null

多线程扩容可能形成：A → B → A （环形）

get操作遍历链表时死循环：
A.next → B → A.next → B ...
CPU 100%，程序卡死！
​

解决方案对比

┌─────────────────┬─────────────┬─────────────┬─────────────┐
│     方案        │ 线程安全性   │   性能      │  复杂度     │
├─────────────────┼─────────────┼─────────────┼─────────────┤
│ HashMap         │     ❌      │    ⭐⭐⭐    │    简单     │
│ Hashtable       │     ✅      │    ⭐       │    简单     │
│ SynchronizedMap │     ⭐      │    ⭐       │    简单     │
│ ConcurrentHashMap│     ✅      │    ⭐⭐     │    复杂     │
│ 手动加锁         │     ✅      │    ⭐       │    中等     │
└─────────────────┴─────────────┴─────────────┴─────────────┘
​

ConcurrentHashMap 的优势

HashMap vs ConcurrentHashMap 并发表现：

HashMap (不安全):
┌───────────────┐
│   全局table   │ ← 多线程操作同一数组，相互覆盖
│ [0][1][2][3]  │
└───────────────┘

ConcurrentHashMap (JDK 1.8):
┌─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │ ← 数组头节点分别加锁
│     │ 🔒  │     │ 🔒  │   更细粒度的控制
└─────┴─────┴─────┴─────┘
​

小结

HashMap 的核心是数组 + 链表 + 红黑树的组合结构。

线程不安全的根本原因：

• put 操作不是原子的
• 扩容过程复杂且耗时
• 没有任何同步机制

主要问题：

• 数据丢失（最常见）
• 无限循环（JDK 1.7）
• 扩容时的各种异常

解决思路：

• 单线程场景继续用 HashMap
• 多线程场景选 ConcurrentHashMap
• 特殊需求才考虑手动加锁

掌握这些原理，HashMap 相关的面试题基本就没问题了。