循序渐进分析源码之 HashMap put 方法的示例分析

发布时间：2021-09-10 14:36:16 作者：柒染
来源：亿速云阅读：157

# 循序渐进分析源码之 HashMap put 方法的示例分析

## 一、前言

HashMap 作为 Java 集合框架中最常用的数据结构之一，其内部实现原理值得深入探究。本文将以 Java 8 的 HashMap 实现为例，通过逐行分析 `put` 方法的源码，揭示其底层数据结构和关键设计思想。我们将从哈希计算开始，逐步深入到数组扩容、链表转红黑树等核心机制。

## 二、HashMap 基础结构回顾

在分析 `put` 方法前，先回顾 HashMap 的核心组成：

```java
// 默认初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;

// 存储数据的 Node 数组
transient Node<K,V>[] table;

// 键值对数量
transient int size;

HashMap 采用 数组 + 链表/红黑树 的存储结构，通过哈希算法确定元素在数组中的位置。

三、put 方法完整流程分析

3.1 put 方法入口

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

put 方法实际调用的是 putVal，其中 hash(key) 是关键的第一步：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希计算特点： 1. 允许 null 键（存储在数组第 0 个位置） 2. 通过高位异或减少哈希冲突（扰动函数）

3.2 putVal 方法详解

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为空时初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 步骤2：计算数组下标并处理空桶情况
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 步骤3：处理哈希冲突
        Node<K,V> e; K k;
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 情况1：key已存在
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 情况2：遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash); // 链表转红黑树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 步骤4：处理key已存在的情况
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 步骤5：检查扩容
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

步骤1：初始化表格

当首次 put 元素时，会触发 resize() 初始化数组：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // ... 计算新容量和新阈值 ...
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // ... 可能的元素迁移 ...
    return newTab;
}

步骤2：计算数组下标

通过 (n - 1) & hash 计算索引（相当于取模运算）：

i = (table.length - 1) & hash

步骤3：处理哈希冲突

当发生哈希冲突时，分为三种情况处理： 1. Key 已存在：直接覆盖值 2. 红黑树节点：调用 putTreeVal 3. 链表结构： - 遍历到链表尾部插入新节点 - 当链表长度 ≥ 8 时转为红黑树

步骤4：覆盖已有值

当检测到 key 已存在时，根据 onlyIfAbsent 参数决定是否覆盖旧值。

步骤5：扩容检查

每次插入后检查 size > threshold，触发扩容：

if (++size > threshold)
    resize();

3.3 树化过程分析

当链表长度达到 8 时，会调用 treeifyBin：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 数组长度小于64时优先扩容
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 转换为TreeNode链表
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        
        // 将TreeNode链表转为红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

树化的两个条件： 1. 链表长度 ≥ 8 2. 数组长度 ≥ 64（否则优先扩容）

四、关键设计思想总结

哈希优化：高位异或扰动减少碰撞
惰性初始化：首次 put 时才分配数组
动态扩容：2倍扩容保持容量为 2^n
渐进式树化：链表→TreeNode链表→红黑树
空间换时间：负载因子 0.75 的平衡选择

五、性能考虑与使用建议

初始容量应根据预估数据量设置，避免频繁扩容
自定义对象作为 key 时，必须正确重写 hashCode() 和 equals()
Java 8 的树化优化显著改善了哈希冲突严重时的查询性能

六、总结

通过对 put 方法的逐步分析，我们可以看到 HashMap 如何优雅地处理： - 哈希冲突（链表+红黑树） - 动态扩容（2倍扩容+元素迁移） - 性能优化（树化阈值、哈希计算等）

理解这些底层机制，有助于我们更好地使用和调优 HashMap。

本文基于 Java 8 HashMap 源码分析，不同版本实现可能有差异 “`

注：本文实际约2300字，可通过扩展以下内容达到2500字： 1. 增加更多源码注释解释 2. 补充红黑树操作细节 3. 添加与Java 7的对比分析 4. 增加实际性能测试数据 5. 扩展线程安全相关讨论