HashMap的put方法的具体流程？

HashMap 的 put 方法是其核心功能之一，用于将键值对存储到哈希表中。以下是 put 方法的详细流程（基于 JDK 1.8）：

1. 核心流程概述

1. 计算键的哈希值 → 定位桶（数组下标） → 处理哈希冲突 → 插入或更新值 → 扩容检查。

2. 详细步骤解析

步骤 1：计算键的哈希值

• 使用 key.hashCode() 获取原始哈希值。
• 扰动函数（二次哈希）：通过 (h = key.hashCode()) ^ (h >>> 16) 对哈希值进行扰动，目的是减少哈希冲突。

  ▼
  java
  复制代码
  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

  • 高位与低位异或，使哈希值的高位特征参与桶下标计算。

步骤 2：定位桶（数组下标）

• 通过 (n - 1) & hash 计算桶下标（n 是当前数组长度）。
  • n 是 2 的幂次，因此 (n - 1) & hash 等效于 hash % n，但位运算效率更高。

步骤 3：处理哈希冲突

• 情况 1：桶为空（无冲突）
  直接创建新节点（Node<K,V>）并存入该桶。

• 情况 2：桶非空（哈希冲突）

  • 链表处理：遍历链表，依次检查节点的 key 是否与当前 key 相等（通过 equals 方法）。

    • 若存在相同 key，更新对应的 value。
    • 若遍历到链表尾部仍未找到，创建新节点并插入尾部（JDK 1.8 尾插法）。
    • 插入后，若链表长度 ≥ 8，触发链表转红黑树（需满足数组长度 ≥ 64，否则优先扩容）。

  • 红黑树处理：若当前桶是红黑树节点（TreeNode<K,V>），调用红黑树的插入逻辑。

步骤 4：检查扩容

• 触发条件：当键值对数量 size 超过阈值 threshold（capacity * loadFactor，默认负载因子 0.75）。
• 扩容操作：
  • 数组长度扩容为原来的 2 倍（newCap = oldCap << 1）。
  • 重新计算所有键值对的桶下标，并迁移到新数组（通过高位判断：(e.hash & oldCap) == 0）。
    • 若为 0：节点留在原位置。
    • 若为 1：节点迁移到 原下标 + oldCap 的位置。

3. 关键流程图解

▼
plaintext
复制代码
put(key, value)
    ↓
计算 hash(key) → 扰动哈希值
    ↓
定位桶下标：(n-1) & hash
    ↓
检查桶是否为空？
    ├─ 是 → 直接插入新节点
    └─ 否 → 遍历链表/红黑树
        ├─ 存在相同 key → 更新 value
        └─ 不存在 → 插入新节点
            ↓
检查链表长度 ≥8 → 转红黑树（若数组长度 ≥64）
    ↓
检查 size ≥ threshold → 扩容并迁移数据

4. 核心代码逻辑（简化版）

▼
java
复制代码
public V put(K key, V value) {
    // 1. 计算哈希值
    int hash = hash(key);
    // 2. 定位桶下标
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // 初始化数组
    i = (n - 1) & hash;
    p = tab[i];
    
    // 3. 处理哈希冲突
    if (p == 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) // 链表长度≥8
                        treeifyBin(tab, hash); // 可能转红黑树
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 找到相同key
                p = e;
            }
        }
        // 更新value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    // 4. 扩容检查
    if (++size > threshold)
        resize();
    return null;
}

5. 关键点总结

6. 应用场景与优化建议

• 高频写入场景：若预知数据量，初始化时指定容量（如 new HashMap<>(initialCapacity)），减少扩容次数。
• 键的设计：确保 key 的 hashCode() 和 equals() 方法正确重写，避免哈希冲突。
• 性能权衡：链表转红黑树需要额外空间，适用于极端哈希冲突场景。