HashMap中put()方法的执行流程

HashMap 是 Java 中最常用的数据结构之一，用于存储键值对。其 put() 方法是向哈希表中插入或更新键值对的核心操作。本文将详细解析 put() 方法的执行过程，涵盖哈希值计算、桶定位、冲突处理和扩容等步骤。

一、put() 方法的执行过程

put() 方法通过一系列步骤实现键值对的高效存储和更新。以下是详细的执行流程：

1. 计算键的哈希值

• 步骤：HashMap 首先调用键的 hashCode() 方法获取其哈希码。
• 扰动处理：为了减少哈希冲突，HashMap 对哈希码进行扰动处理，具体通过 (h = key.hashCode()) ^ (h >>> 16)，将高 16 位与低 16 位进行异或操作，增加哈希值的随机性。
• 特殊情况：如果键为 null，哈希值固定为 0（HashMap 允许一个 null 键）。

2. 确定桶位置

• 计算索引：使用哈希值通过公式 index = hash & (table.length - 1) 计算键值对在数组（桶）中的索引位置。
• table 初始化：table 是 HashMap 内部用于存储节点的数组。如果 table 未初始化（即 table == null 或 table.length == 0），会调用 resize() 方法初始化数组。

3. 处理桶中的情况

根据目标桶（table[index]）的状态，put() 方法会执行不同的逻辑：

情况 1：桶为空

• 如果桶中没有节点，直接创建一个新的 Node（包含键、值、哈希值等信息）并放入该桶。

情况 2：桶中已有节点

• 3.2.1 检查第一个节点

  • 如果桶中第一个节点的键与插入的键相同（通过哈希值比较和 equals() 方法确认），直接更新该节点的值。

• 3.2.2 处理红黑树

  • 如果桶中节点数量较多（超过 TREEIFY_THRESHOLD，默认为 8），且桶已转为红黑树结构，调用红黑树的插入方法（putTreeVal）处理插入或更新。

• 3.2.3 处理链表

  • 如果桶中是链表结构，遍历链表：
    • 如果找到键相同的节点，更新其值。
    • 如果没有找到相同键，将新节点添加到链表末尾。
  • 插入后，如果链表长度大于等于8且数组长度达到64时，调用 treeifyBin() 将链表转换为红黑树。

情况 3：桶中键为 null

• 如果插入的键为 null，存储到索引为 0 的桶中（HashMap 只允许一个 null 键）。

4. 更新大小和检查扩容

• 更新 size：插入新键值对后，HashMap 的 size（键值对数量）加 1。
• 检查扩容：如果 size 超过阈值（threshold = table.length * loadFactor，默认负载因子为 0.75），触发 resize() 方法进行扩容。
• 扩容：将数组的容量扩大为原来的2倍。

5. 返回旧值

• 如果插入的键已存在，put() 方法返回该键对应的旧值。
• 如果是新插入的键值对，返回 null。

二、核心代码分析

以下是 put() 方法的核心逻辑：

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

// 计算哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 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;
    // 如果 table 未初始化，调用 resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算索引，检查桶是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 直接插入新节点
    else {
        Node<K,V> e; K k;
        // 检查第一个节点是否匹配
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树，调用树插入逻辑
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 遍历链表
        else {
            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;
            }
        }
        // 如果找到已有键，更新值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 增加 size，检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}