问题

2. HashMap 的 put 方法执行流程是怎样的？涉及哪些关键操作？

标准答案

HashMap 的 put(K key, V value) 方法用于向 Map 中插入键值对，其执行流程包含 计算哈希值、确定桶索引、插入节点、链表或红黑树处理、扩容检查 等关键步骤。JDK 1.8 采用 数组 + 链表 + 红黑树 结构，优化了哈希冲突处理，同时提升了查询和插入性能。

• 计算 key 的哈希值：通过 (h = key.hashCode()) ^ (h >>> 16) 计算哈希值，降低哈希碰撞概率。
• 确定索引位置：通过 (n - 1) & hash 计算 key 在 table 数组中的索引。
• 插入节点：
  • 如果该索引为空，直接放入新节点。
  • 如果已存在节点，则遍历链表：
    • 如果 key 已存在，则更新 value。
    • 如果是链表，插入到链表尾部。
    • 如果链表长度达到 8，转换为红黑树。
• 扩容检查：若当前存储元素超过 threshold（负载因子 * 数组容量），则触发 resize() 进行扩容。

答案解析

1. put() 方法的核心流程

put() 方法的核心流程如下（JDK 1.8 源码简化版）：

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    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;  // key 已存在，更新 value
        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; // key 已存在，退出循环
                p = e;
            }
        }
        if (e != null) 
            e.value = value;  // 更新已有 key 的 value
    }

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

    return null;
}

2. 关键操作解析

(1) 计算哈希值

调用 hash() 方法计算 key 的哈希值：

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

• 通过 高 16 位和低 16 位进行异或，使高位也参与索引计算，减少哈希冲突。
• 避免了直接使用 hashCode() 可能导致的哈希分布不均问题。

(2) 计算数组索引

i = (n - 1) & hash;

• 由于 n 是 2 的幂，(n - 1) & hash 等价于 hash % n，但 比取模运算更高效（位运算速度更快）。

(3) 处理哈希冲突

• 如果该位置为空，直接插入新节点。
• 如果该位置已有节点：
  • 若 key 已存在，则更新 value。
  • 若是链表，则插入到链表末尾，并检查是否需要转为红黑树。
  • 若是红黑树，则调用 putTreeVal() 进行插入。

(4) 可能转换为红黑树

• 当链表长度 ≥ 8 且数组长度 ≥ 64 时，会调用 treeifyBin() 转换为红黑树：

  void treeifyBin(Node<K,V>[] tab, int hash) {
      if (tab.length < MIN_TREEIFY_CAPACITY)
          resize();
      else {
          // 转换链表为红黑树
      }
  }
  

(5) 可能触发扩容

• 当 size > threshold 时，调用 resize() 进行扩容：

  final Node<K,V>[] resize() {
      Node<K,V>[] oldTab = table;
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      int newCap = oldCap << 1; // 容量翻倍
      Node<K,V>[] newTab = new Node[newCap];
      // 重新计算元素位置
      return newTab;
  }
  

• 由于 n 是 2 的幂，扩容时只需判断 (hash & oldCap) == 0 来决定元素去新索引还是保留原索引，避免了重新计算哈希值，提高性能。

4. HashMap 的常见问题

❌ 常见误区

1. put 过程是线程安全的吗？

• 误区：很多人误认为 put() 是线程安全的，但它在并发环境下可能导致数据丢失、死循环。
• 正确方案：使用 ConcurrentHashMap 或 Collections.synchronizedMap(new HashMap<>())。

2. 哈希冲突是否一定会转换为红黑树？

• 误区：有人认为链表长度达到 8 就一定转红黑树，但实际上，只有数组大小 ≥ 64 时才会转。
• 正确方案：如果数组较小，JDK 1.8 仍然会扩容，而不是立即转换红黑树。

3. 扩容时为什么采用 2 的幂次？

• 误区：有些人认为 10 这样的值也可以作为初始容量，但实际上，HashMap 要求容量始终是 2 的幂，否则会被调整为最接近的 2 的幂次方（如 10 会变为 16）。
• 正确方案：初始化时应直接指定 2 的幂，避免不必要的调整。

深入追问

🔹 为什么 hash() 方法采用 (h = key.hashCode()) ^ (h >>> 16)？
🔹 为什么 HashMap 采用 链地址法 解决哈希冲突，而不是开放地址法？
🔹 扩容时 resize() 为什么不重新计算哈希值？
🔹 为什么链表长度达到 8 才转换为红黑树，而不是更小？

相关面试题

• get() 方法的执行流程是怎样的？
• HashMap 扩容的详细过程？
• ConcurrentHashMap 的 put 操作和 HashMap 有什么不同？
• 为什么 HashMap 采用 0.75 作为默认负载因子？

这就是 HashMap put() 方法的详细执行过程，如果有需要，可以深入解析某个具体的部分！