HashMap 全过程原理

HashMap 是 Java 后端最常用的数据结构之一。它看起来只是 put/get，但背后包含数组、链表、红黑树、hash 扰动、容量为什么是 2 的幂、扩容迁移、equals/hashCode、JDK 7/JDK 8 差异和线程安全边界。HashMap 学不透，后面的 ConcurrentHashMap、缓存、分库分表 hash、布隆过滤器、热点 key、面试题都会断层。

学习目标

目标	要能说清楚
基本结构	HashMap 为什么是数组 + 链表 + 红黑树
put 流程	初始化、定位桶、覆盖、追加、树化、扩容
get 流程	hash、下标、首节点、链表、红黑树查找
resize 流程	为什么扩容翻倍，节点为什么只会留原位或去 原位 + oldCap
2 的幂	为什么不用任意容量，为什么用 (n - 1) & hash
树化	为什么链表长度到 8 不一定立刻树化
equals/hashCode	为什么重写 equals 必须重写 hashCode
JDK 差异	JDK 7 头插法和 JDK 8 尾插法/红黑树差异
生产风险	可变 key、多线程写、初始容量、内存占用怎么处理

HashMap 解决什么问题

数组按下标查很快，但如果只知道业务 key，比如订单号、用户 ID、报告号，就不知道下标是多少。

链表可以动态添加，但查找要从头遍历，数据多了很慢。

HashMap 的思路是：

flowchart TD
    A["业务 key"] --> B["计算 hash"]
    B --> C["映射到数组下标"]
    C --> D["定位桶"]
    D --> E["桶内少量比较"]
    E --> F["找到 value"]

理想情况下，HashMap 不需要遍历所有数据，只要通过 hash 快速定位到一个桶，再在桶里比较少量节点。

底层结构

JDK 8 的 HashMap 是：

数组 + 链表 + 红黑树

flowchart TD
    A["HashMap"] --> B["Node[] table"]
    B --> C["桶0: null"]
    B --> D["桶1: 单个Node"]
    B --> E["桶2: 链表"]
    B --> F["桶3: 红黑树"]

结构	作用
数组 table	快速按下标定位桶
Node	保存 key、value、hash、next
链表	解决多个 key 落到同一个桶的问题
红黑树	极端 hash 冲突时避免链表过长

Node 可以简化理解为：

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

为什么需要 hash 扰动

HashMap 不是直接用 key.hashCode() 定位下标，而是会做一次扰动：

int h = key.hashCode();
int hash = h ^ (h >>> 16);

为什么？

HashMap 用 (n - 1) & hash 定位桶。当容量不大时，只用到了 hash 的低位。如果某些 key 的低位分布不好，高位再优秀也参与不到下标计算。扰动就是把高位信息混到低位，降低冲突概率。

flowchart TD
    A["原始 hashCode"] --> B["高16位和低16位异或"]
    B --> C["高位信息参与低位"]
    C --> D["减少低位分布差导致的冲突"]

为什么容量必须是 2 的幂

HashMap 定位桶下标使用：

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

如果 table.length 是 16：

length     = 16  -> 10000
length - 1 = 15  -> 01111

hash & 01111 的结果一定在 0 ~ 15 之间，等价于对 16 取模，但位运算通常更快。

容量是 2 的幂还有一个重要好处：扩容迁移更高效。

设计	好处
容量是 2 的幂	可以用 & 代替 %
扩容翻倍	新下标只取决于新增的那一位
节点迁移	只会留原位或移动到 原位 + oldCap

tableSizeFor：传 10 为什么变 16

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

HashMap 内部不会真的把容量设成 10，而是调整成大于等于 10 的最小 2 的幂，也就是 16。

流程：

flowchart TD
    A["传入 initialCapacity=10"] --> B["计算 >=10 的最小2的幂"]
    B --> C["得到16"]
    C --> D["后续 table 初始化容量为16"]

为什么不是立刻创建数组？

HashMap 是懒初始化。构造方法里通常只记录阈值，真正的 table 数组在第一次 put 时才创建。这样创建空 HashMap 时不会立刻占用数组内存。

put 全流程

flowchart TD
    A["put(key,value)"] --> B["计算 hash"]
    B --> C{"table 是否为空"}
    C -->|是| D["resize 初始化 table"]
    C -->|否| E["计算桶下标"]
    D --> E
    E --> F{"桶是否为空"}
    F -->|是| G["创建新 Node 放入桶"]
    F -->|否| H{"首节点 key 是否相同"}
    H -->|是| I["覆盖旧 value"]
    H -->|否| J{"桶是链表还是红黑树"}
    J -->|链表| K["遍历链表"]
    K --> L{"找到相同 key"}
    L -->|是| I
    L -->|否| M["尾插新节点"]
    M --> N{"链表长度是否达到树化阈值"}
    N -->|是| O["treeifyBin"]
    N -->|否| P["size++"]
    J -->|红黑树| Q["按树规则插入或覆盖"]
    G --> P
    I --> R["返回旧 value"]
    O --> P
    Q --> P
    P --> S{"size 是否超过 threshold"}
    S -->|是| T["resize 扩容"]
    S -->|否| U["put 完成"]

关键点：

步骤	原理
table 为空才 resize	懒初始化
桶为空直接放	最理想情况，O(1)
key 相同覆盖	Map 中同一个 key 只能有一个 value
链表尾插	JDK 8 使用尾插，保持链表相对顺序
树化检查	链表太长时可能转红黑树
size 超阈值扩容	控制整体负载

get 全流程

flowchart TD
    A["get(key)"] --> B["计算 hash"]
    B --> C["计算桶下标"]
    C --> D{"桶是否为空"}
    D -->|是| E["返回 null"]
    D -->|否| F{"首节点是否匹配"}
    F -->|是| G["返回 value"]
    F -->|否| H{"是否红黑树"}
    H -->|是| I["按树查找"]
    H -->|否| J["遍历链表"]
    I --> K["找到返回，找不到 null"]
    J --> K

节点是否匹配通常要满足：

hash 相同，并且 key == targetKey 或 key.equals(targetKey)

先比较 hash 是为了快速排除不可能相等的 key，再用 equals 做最终业务相等判断。

remove 全流程

flowchart TD
    A["remove(key)"] --> B["计算 hash 和下标"]
    B --> C{"桶是否为空"}
    C -->|是| D["返回 null"]
    C -->|否| E["查找目标节点"]
    E --> F{"是否找到"}
    F -->|否| D
    F -->|是| G{"节点在链表还是树"}
    G -->|链表| H["断开节点链接"]
    G -->|树| I["树删除并调整"]
    H --> J["size--"]
    I --> J
    J --> K["返回旧 value"]

HashMap 删除后不会自动缩容。因为如果数据量来回波动，自动缩容会导致频繁扩容/缩容，成本很高。HashMap 更倾向于保持容量，等待后续复用。

threshold 和 loadFactor

字段	含义
capacity	table 数组长度
size	当前键值对数量
loadFactor	负载因子，默认 0.75
threshold	扩容阈值，通常是 capacity * loadFactor

默认第一次 put 后容量通常是 16，负载因子 0.75，阈值是 12。插入第 13 个元素后，超过阈值触发扩容。

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

负载因子	结果
太小	空桶多，占内存，但冲突少
太大	数组利用率高，但冲突多，查询变慢
0.75	时间和空间的折中

resize 扩容全过程

HashMap 扩容通常是容量翻倍：

16 -> 32 -> 64 -> 128

流程：

flowchart TD
    A["触发 resize"] --> B["创建 2 倍容量新数组"]
    B --> C["遍历旧 table"]
    C --> D{"旧桶是否为空"}
    D -->|是| E["跳过"]
    D -->|否| F{"桶中是单节点、链表还是树"}
    F -->|单节点| G["计算新下标后放入"]
    F -->|链表| H["拆成低位链表和高位链表"]
    F -->|红黑树| I["拆树，必要时退化链表"]
    H --> J["低位留 oldIndex"]
    H --> K["高位到 oldIndex + oldCap"]

最关键的一句：

扩容翻倍后，旧桶里的节点只会留在原下标，或者移动到 原下标 + oldCap。

为什么？

旧容量是 16，新容量是 32，只是多了一个二进制位参与计算。看 hash & oldCap：

判断	新位置
(hash & oldCap) == 0	仍在原下标
(hash & oldCap) != 0	移动到原下标 + oldCap

这比重新对每个 key 做完整取模更高效。

链表为什么树化

如果大量 key 落到同一个桶，链表会很长，查询会从接近 O(1) 退化成 O(n)。

JDK 8 引入红黑树，极端冲突下查询可以降到 O(log n)。

但链表长度达到 8，不一定立刻树化。

flowchart TD
    A["链表长度达到8"] --> B{"table容量是否 >= 64"}
    B -->|否| C["优先扩容"]
    B -->|是| D["链表转红黑树"]
    C --> E["扩容后节点可能分散"]
    D --> F["极端冲突下提升查询"]

为什么容量小于 64 先扩容？

因为冲突可能只是数组太短导致的。扩容后节点分散到更多桶，链表自然变短。红黑树维护成本更高，所以只有容量足够大且冲突仍然严重时才树化。

树化阈值为什么是 8

这是一个工程折中，不是数学定律。HashMap 假设 hash 分布合理时，桶内链表长度达到 8 的概率很低。如果真的达到 8，说明可能有比较严重的冲突，需要考虑树化。

为什么退化阈值是 6 而不是 7 或 8？

如果树化阈值和退化阈值太接近，节点数量在边界附近波动时，会频繁链表和红黑树互转。用 8 树化、6 退化，可以形成缓冲区。

JDK 7 和 JDK 8 差异

维度	JDK 7	JDK 8
结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入	头插法	尾插法
极端冲突	链表查询 O(n)	树化后 O(log n)
并发 resize 经典问题	可能形成环链表	仍不线程安全，但迁移逻辑优化

JDK 7 头插法在并发 resize 时为什么危险？

flowchart TD
    A["两个线程同时 resize"] --> B["都在迁移同一条链表"]
    B --> C["头插法会反转节点顺序"]
    C --> D["线程交错修改 next 指针"]
    D --> E["可能形成环链表"]
    E --> F["get 遍历时死循环"]

注意：JDK 8 优化了这个问题，但 HashMap 仍然不是线程安全的。并发写会有数据丢失、覆盖、结构不一致等风险。

equals 和 hashCode 为什么必须一起重写

HashMap 查找分两步：

flowchart TD
    A["key"] --> B["hashCode 定位桶"]
    B --> C["equals 比较桶内节点"]

如果两个对象 equals 相等，但 hashCode 不同，它们会落到不同桶。HashMap 根本不会在同一个桶里调用 equals 比较，结果就是查不到或去重失败。

错误示例：

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class ReportKey {
    private final String patientId;
    private final String reportNo;

    ReportKey(String patientId, String reportNo) {
        this.patientId = patientId;
        this.reportNo = reportNo;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof ReportKey other)) {
            return false;
        }
        return Objects.equals(patientId, other.patientId)
                && Objects.equals(reportNo, other.reportNo);
    }
}

public class BadEqualsDemo {
    public static void main(String[] args) {
        Set<ReportKey> set = new HashSet<>();
        set.add(new ReportKey("P001", "R001"));
        set.add(new ReportKey("P001", "R001"));
        System.out.println(set.size()); // 可能是 2
    }
}

正确写法：

@Override
public int hashCode() {
    return Objects.hash(patientId, reportNo);
}

为什么 key 最好不可变

HashMap 放入 key 时，会根据当时的 hash 定位桶。如果 key 的字段变了，hash 也变了，再查时会去另一个桶。

Map<UserKey, String> map = new HashMap<>();
UserKey key = new UserKey(1L);
map.put(key, "Tom");

key.setId(2L);
System.out.println(map.get(key)); // 可能取不到

流程：

flowchart TD
    A["put 时 id=1"] --> B["按 hash1 放入桶A"]
    C["修改 id=2"] --> D["get 时计算 hash2"]
    D --> E["去桶B查找"]
    E --> F["桶B没有旧节点，返回 null"]

所以 Map key 推荐使用不可变对象，例如 String、包装类型、枚举、record，或者字段全部 final 的值对象。

HashMap 为什么线程不安全

HashMap 没有并发控制：

场景	风险
多线程 put 同一个 key	覆盖更新
多线程 put 不同 key	size 不准，结构修改冲突
put 时同时 resize	迁移结构异常
遍历时另一个线程修改	可能抛 ConcurrentModificationException

多线程写应使用：

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

或者在外层加锁，但大多数高并发场景更推荐 ConcurrentHashMap。

商业 Demo：采集记录去重

医疗采集平台常用“患者 ID + 就诊号 + 报告号”作为业务唯一键。

import java.util.HashSet;
import java.util.Set;

record CollectKey(String patientId, String visitNo, String reportNo) {
}

public class CollectDeduplicateDemo {
    public static void main(String[] args) {
        Set<CollectKey> exists = new HashSet<>();
        exists.add(new CollectKey("P001", "V001", "R001"));

        CollectKey incoming = new CollectKey("P001", "V001", "R001");
        if (exists.contains(incoming)) {
            System.out.println("重复采集，跳过");
        } else {
            System.out.println("新记录，入库");
        }
    }
}

record 默认生成基于全部组件的 equals/hashCode，适合做不可变 key。真实项目要明确唯一键字段，否则会重复采集或误判重复。

商业 Demo：预估容量减少扩容

如果要放入 10 万条映射，默认 HashMap 会多次扩容。

int expectedSize = 100000;
int capacity = (int) (expectedSize / 0.75F) + 1;
Map<String, String> dict = new HashMap<>(capacity);

适用场景：

场景	为什么
字典加载	数据量可预估，减少扩容
批量导入去重	避免导入过程频繁 rehash
编码映射	初始化后大量查询，提前建好容量

线上排查

现象	可能原因	排查
HashMap 查不到刚放的数据	key 被修改	检查 key 字段是否参与 hashCode
HashSet 去重失败	equals/hashCode 不一致	打印 hashCode，检查是否同时重写
批量导入慢	多次扩容	预估容量，观察 CPU 和 GC
多线程统计不准	HashMap 并发写	改 ConcurrentHashMap + LongAdder
内存占用高	Map 长期缓存不清理	dump 看引用链，增加淘汰策略

排查 HashMap 问题时，不要只看 Map 本身，还要看 key 的设计。很多“Map 查不到”的根因不是 HashMap 坏了，而是 key 可变、equals/hashCode 写错或并发写。

面试标准回答

HashMap 底层结构

JDK 8 的 HashMap 底层是数组 + 链表 + 红黑树。数组用于按 hash 快速定位桶，链表用于解决哈希冲突，红黑树用于极端冲突下避免链表过长导致查询退化。Node 中保存 hash、key、value 和 next。

HashMap put 流程

put 时先计算 key 的 hash，如果 table 还没初始化就 resize 初始化；然后用 (n - 1) & hash 定位桶。桶为空就直接放新节点；桶不为空先比较首节点，key 相同就覆盖；否则遍历链表或红黑树，找到相同 key 就覆盖，找不到就追加或插入树中。插入新节点后 size 增加，如果超过 threshold 就扩容。

HashMap 为什么容量是 2 的幂

容量是 2 的幂时，可以用 (n - 1) & hash 快速定位桶下标，效果类似取模但更高效。同时扩容翻倍后，节点只需要根据 hash & oldCap 判断留在原位置还是移动到 原位置 + oldCap，迁移更快。

HashMap 扩容流程

HashMap 超过阈值后会创建 2 倍容量的新数组，然后遍历旧数组迁移节点。JDK 8 中链表迁移会拆成低位链表和高位链表，hash & oldCap == 0 的节点留在原下标，不等于 0 的节点移动到 原下标 + oldCap。这样不用重新完整取模。

HashMap 为什么线程不安全

HashMap 的 put、resize、链表和红黑树结构修改都没有并发保护。多线程写可能出现覆盖、size 不准、结构异常，JDK 7 并发 resize 还可能形成环链表。多线程写应使用 ConcurrentHashMap 或加锁。

为什么重写 equals 必须重写 hashCode

HashMap 先用 hashCode 定位桶，再用 equals 比较桶内节点。如果两个对象 equals 相等但 hashCode 不同，它们会落到不同桶，导致 HashMap 查不到或 HashSet 去重失败。所以 equals 相等的对象必须有相同 hashCode。

关联知识点

知识点	为什么要看
集合框架	集合体系总览和其他容器选择
数据类型与 equals	理解 ==、equals、hashCode 基础语义
JDK版本差异	JDK 7/JDK 8 HashMap 差异
ConcurrentHashMap全过程	理解并发 Map 如何解决 HashMap 并发问题
volatile与Atomic全过程	理解并发容器里 CAS 和可见性基础