一文读懂 Java HashMap 的 put 方法：从源码到原理

HashMap 是 Java 中最常用的集合类之一，核心作用是键值对（Key-Value）存储与快速查询。而 put(K key, V value) 方法作为其核心操作，背后藏着哈希表的经典设计思想 ——“数组 + 链表 / 红黑树” 的组合结构。今天我们就结合 JDK 1.8 的源码，一步步拆解 put 方法的完整过程，做到不仅知其然，更知其所以然。

HashMap 的 “底层骨架”

在看 put 方法前，必须先明确 HashMap 的存储结构，否则源码会看得云里雾里：

核心容器：

一个名为 table 的数组（官方叫 “哈希桶数组”），数组的每个元素是一个 “节点”（Node<K,V>）。

节点的两种形态：

链表节点（Node）：当多个键哈希后落到同一个数组位置（哈希冲突）时，用链表串联这些节点；

红黑树节点（TreeNode）：当链表长度超过阈值（默认 8），且数组长度≥64 时，链表会转为红黑树（提高查询效率，从 O (n) 降到 O (log n)）。

关键参数：

capacity：数组长度（默认初始值 16，必须是 2 的幂）；

loadFactor：负载因子（默认 0.75），用于判断是否需要扩容；

threshold：扩容阈值（capacity * loadFactor），当元素个数超过这个值，数组会扩容为原来的 2 倍。

put 方法源码总览（JDK 1.8）

贴出简化后的核心源码（去掉异常处理、调试代码等冗余部分）

public V put(K key, V value) {
    // 核心：调用 putVal 方法，第一个参数是 key 的哈希值（经过二次哈希优化）
    return putVal(hash(key), key, value, false, true);
}

// 真正实现 put 逻辑的核心方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 初始化：如果数组 table 为空或长度为 0，先扩容（第一次 put 时触发）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 计算数组索引，找到对应的哈希桶：i = (n-1) & hash（关键！）
    // 如果桶为空，直接新建节点放入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { // 3. 哈希冲突：当前桶已有节点（p 是桶中第一个节点）
        Node<K,V> e; K k;
        // 3.1 情况1：桶中第一个节点的 key 与传入 key 完全一致（哈希值+equals 都相等）
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 记录这个重复的节点
        // 3.2 情况2：当前桶是红黑树结构
        else if (p instanceof TreeNode)
            // 调用红黑树的插入方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 3.3 情况3：当前桶是链表结构
        else {
            // 遍历链表，找重复 key 或插入尾部
            for (int binCount = 0; ; ++binCount) {
                // 3.3.1 遍历到链表尾部，没有重复 key，新建节点插入尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度超过 8，触发“链表转红黑树”检查
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 3.3.2 遍历中找到重复 key（哈希值+equals 都相等）
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 移动到下一个节点，继续遍历
                p = e;
            }
        }
        // 4. 处理重复 key：如果找到重复节点 e
        if (e != null) {
            V oldValue = e.value;
            // onlyIfAbsent 为 false（默认）时，用新值覆盖旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 访问后回调（LinkedHashMap 用，HashMap 中是空实现）
            afterNodeAccess(e);
            return oldValue; // 返回旧值
        }
    }
    // 5. 统计修改次数（用于快速失败机制）
    ++modCount;
    // 6. 检查是否需要扩容：元素个数超过阈值
    if (++size > threshold)
        resize();
    // 插入后回调（LinkedHashMap 用）
    afterNodeInsertion(evict);
    return null; // 无重复 key 时，返回 null
}

逐步骤拆解 put 方法核心流程

我们按源码执行顺序，把 put 过程拆成 6 个关键步骤，每个步骤都讲清 “为什么这么做” 和 “底层原理”。

步骤 1：计算 Key 的哈希值（hash (key) 方法）

put 方法第一步不是直接存数据，而是先对 key 做 “哈希计算”—— 目的是把任意类型的 key（列如 String、Integer）转换成一个整数，后续用这个整数定位数组索引。

JDK 1.8 的 hash 方法实现：

static final int hash(Object key) {
    int h;
    // 逻辑：key 为 null 时哈希值是 0；否则先拿 key 的 hashCode，再做“二次哈希”
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里有两个关键知识点：

key 可以为 null：HashMap 允许 key 为 null，且固定存放在数组索引 0 的位置（由于 hash (null) = 0）；
二次哈希的意义：h ^ (h >>> 16) 是把 key.hashCode() 的高 16 位和低 16 位做 “异或运算”。为什么要这么做？

①后续定位数组索引用的是 (n-1) & hash（n 是数组长度，2 的幂），这个运算本质是 “取 hash 的低 k 位”（k 是 n 的二进制位数，列如 n=16 时取低 4 位）；

②如果只用到低 k 位，高 16 位的信息会被浪费，容易导致哈希冲突（列如两个 key 的 hashCode 低 4 位一样，但高 16 位不同）；

③二次哈希让高 16 位参与运算，相当于 “混合” 了高低位信息，减少哈希冲突的概率。

步骤 2：数组初始化（第一次 put 时触发）

HashMap 刚创建时，table 数组是 null（懒加载），第一次调用 put 时才会初始化数组：

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

这里的 resize() 方法既是 “初始化数组”，也是 “扩容数组” 的核心方法：

初始化时，数组长度默认设为 16（DEFAULT_INITIAL_CAPACITY = 1 << 4）；
同时计算扩容阈值 threshold = 16 * 0.75 = 12（默认负载因子 0.75）。

步骤 3：计算数组索引，定位哈希桶

拿到 key 的哈希值后，下一步是确定 “这个 key 应该存在数组的哪个位置”—— 即计算索引 i：

i = (n - 1) & hash

这里的 n 是数组长度（必须是 2 的幂），为什么不用 hash % n 取模，而用 (n-1) & hash？

效率更高：位运算（&）比取模运算（%）快得多；
结果等价：当 n 是 2 的幂时，hash % n 和 (n-1) & hash 的结果完全一样（列如 n=16，n-1=15（二进制 1111），& hash 就是取 hash 的低 4 位，和取模 16 效果一样）。

举个例子：

数组长度 n=16（二进制 10000），n-1=15（二进制 01111）；
假设 hash=100（二进制 01100100）；
100 & 15 = 4（二进制 00000100），索引就是 4，对应数组第 5 个位置（从 0 开始）。

定位到索引后，分两种情况：

情况 A：该索引位置的桶为空（tab[i] == null）：直接新建一个链表节点（Node）放入桶中，这一步没有哈希冲突；
情况 B：该索引位置的桶不为空（tab[i] != null）：发生哈希冲突，需要进一步处理（步骤 4 详细说）。

步骤 4：处理哈希冲突（链表 / 红黑树插入）

哈希冲突是指 “不同的 key 经过哈希计算后，得到的索引一样”，HashMap 用 “链表 + 红黑树” 解决冲突：

4.1 先检查是否存在重复 Key

遍历当前桶中的节点，判断是否有 “和传入 key 完全一样” 的节点。

判断标准是哈希值相等 + equals 方法返回 true：

如果找到重复 key：记录该节点（e = 重复节点），后续用新值覆盖旧值（步骤 5）；
如果没找到重复 key：继续插入新节点。

这里要注意：哈希值相等 ≠ key 相等，但 key 相等 → 哈希值必定相等（equals 方法和 hashCode 方法的约定）。所以必须先判断哈希值，再用 equals 确认，避免误判。

4.2 分结构插入新节点

根据桶的结构（链表 / 红黑树），插入新节点的方式不同：

（1）桶是红黑树结构（p instanceof TreeNode）

当链表长度超过 8，且数组长度≥64 时，链表会转为红黑树（treeifyBin 方法处理）。此时调用红黑树的 putTreeVal 方法插入节点：

红黑树会保持 “平衡” 特性，插入和查询效率都是 O (log n)；
如果插入后红黑树的节点数少于 6（UNTREEIFY_THRESHOLD = 6），会转回链表（避免红黑树的维护成本）。

（2）桶是链表结构

遍历链表，找到插入位置：

遍历到链表尾部（e = p.next == null）：新建节点插入尾部（尾插法，JDK 1.8 改为尾插法，解决 1.7 头插法在扩容时的循环链表问题）；
插入后检查链表长度：如果长度≥8（binCount >= TREEIFY_THRESHOLD – 1，TREEIFY_THRESHOLD=8），调用 treeifyBin 方法尝试转为红黑树；

注意：treeifyBin 不会直接转树！如果数组长度＜64，会先扩容数组（让元素分散），只有数组长度≥64 才会转红黑树（由于数组太小，转树收益不大）。

步骤 5：处理重复 Key（覆盖旧值）

如果步骤 4 中找到重复 key 的节点（e != null），则用新值覆盖旧值，并返回旧值：

if (e != null) {
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value; // 覆盖旧值
    afterNodeAccess(e);
    return oldValue; // 返回旧值，让调用者知道之前的 value
}

这里的 onlyIfAbsent 参数是 put 方法的隐藏参数（默认 false）：

若设为 true：只有当旧值为 null 时才覆盖（列如 putIfAbsent 方法就是调用 putVal(hash, key, value, true, true)）；
若为 false（默认）：无论旧值是否为 null，都用新值覆盖。

步骤 6：检查扩容（元素个数超过阈值）

插入新节点后，会检查当前元素个数（size）是否超过扩容阈值（threshold）：

if (++size > threshold)
    resize(); // 扩容

resize() 方法的核心逻辑：

新建一个数组，长度是原来的 2 倍（列如从 16 扩到 32）；
重新计算扩容阈值（newThreshold = newCapacity * loadFactor，列如 32*0.75=24）；
把原来数组中的所有节点，重新计算索引后迁移到新数组中（JDK 1.8 优化了迁移逻辑，避免了 1.7 中的死循环问题）。

为什么要扩容？

负载因子（0.75）是 “时间和空间的平衡”：负载因子太大，数组利用率高，但哈希冲突概率增加；负载因子太小，哈希冲突少，但数组浪费空间；
扩容后数组长度翻倍，节点会重新分散到更多的桶中，减少哈希冲突，保证查询效率。

总结：put 方法的完整流程图

用一张图概括整个过程，一目了然：

一文读懂 Java HashMap 的 put 方法：从源码到原理

关键面试 / 避坑点

1.key 为什么要重写 equals 和 hashCode？

如果只重写 equals 不重写 hashCode：可能导致两个 equals 相等的 key，哈希值不同，存入不同的桶，无法触发重复 key 覆盖；
如果只重写 hashCode 不重写 equals：可能导致两个哈希值一样的 key，equals 不相等，存入同一个桶的链表 / 红黑树中，无法识别重复 key。

2.JDK 1.7 和 1.8 的 HashMap put 方法区别？