前言

在 Java 社区有句话：“如果你不懂 HashMap 的源码，你就不算真正掌握了 Java。” 确实，HashMap 的底层设计是空间与时间权衡的艺术。在 JDK 1.8 中，为了解决极端情况下的哈希冲突，它引入了红黑树结构。今天，作为资深后端开发，我带大家逐行分析那些面试官最爱问的“硬核细节”。

---

一、 HashMap 的核心参数：理解“阈值”的艺术

在阅读 put 逻辑前，必须先记住这几个关键常量：

• DEFAULT_INITIAL_CAPACITY: 默认初始容量为 16（必须是 2 的幂）。

• MAXIMUM_CAPACITY: 最大容量 230。

• DEFAULT_LOAD_FACTOR: 默认负载因子 0.75。

• TREEIFY_THRESHOLD: 链表转红黑树的阈值，固定为 8。

• UNTREEIFY_THRESHOLD: 红黑树退化为链表的阈值，固定为 6。

• MIN_TREEIFY_CAPACITY: 只有当数组长度达到 64 时，才允许链表转红黑树，否则优先扩容。

---

二、 扰动函数：如何让数据分布更均匀？

HashMap 并不是直接拿 hashCode() 去用的，而是经过了一次位运算：

java

static final int hash(Object key) { int h; // 将哈希值的高 16 位与低 16 位进行异或运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

资深视角：这叫“扰动函数”。因为数组长度通常较小，直接取模只有低位起作用。通过 (h >>> 16) 让高位参与运算，可以有效减少碰撞，增加随机性。

---

三、 核心方法 putVal 源码解析（重难点）

当我们执行 map.put(key, value) 时，底层发生了什么？

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. 如果数组为空，先调用 resize() 进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
// 2. 计算索引 (n - 1) & hash，如果没碰撞，直接创建新节点
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node<K,V> e; K k;
    // 3. 碰撞了：如果 key 完全相同，直接覆盖
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    // 4. 碰撞了：如果是红黑树节点，调用树的插入逻辑
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        // 5. 碰撞了：如果是链表，循环寻找末尾或相同 Key
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                // 链表长度达到 8，尝试转红黑树
                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;
        }
    }
    // ... 后续处理：如果 key 存在，返回旧值，维护 modCount
}

四、 扩容机制（Resize）：老瓶装新酒

HashMap 的扩容不仅仅是翻倍，它在 JDK 1.8 中有一个非常巧妙的优化。

传统做法：扩容后，每个元素都要重新计算哈希（Rehash），非常耗时。 JDK 1.8 优化：由于数组长度是 2 的幂次方，扩容后的新位置要么在原位置，要么在原位置 + 旧数组长度。

• 通过 (hash & oldCap) 运算，如果是 0，位置不变；如果是 1，位置移动。

• 这种方式避免了重新计算 hash，大大提升了扩容效率。

---

五、 红黑树：最后的护城河

为什么阈值是 8？

• 概率论依据：根据泊松分布（Poisson distribution），在负载因子为 0.75 的情况下，同一个桶中元素达到 8 个的概率不到千万分之一。

• 性能考量：

  • 链表查询 O(n)。

  • 红黑树查询 O(logn)。

  • 但是红黑树占用空间是链表的 2 倍，且插入时需要进行左旋、右旋和变色。

  • 所以，8 是一个“防止恶意 Hash 攻击”与“内存效率”之间的平衡点。

---

六、 避坑指南：千万别在并发下使用 HashMap

虽然 JDK 1.8 修复了 JDK 1.7 中扩容可能导致的死循环（死链）问题，但在并发环境下，HashMap 依然是不安全的：

1. 数据丢失：两个线程同时触发 put，可能会互相覆盖。

2. 数据不一致：一个线程在扩容，另一个线程在查询，可能查到 null。

建议：高并发场景请出门左转找 ConcurrentHashMap。

---

七、 总结：如何优雅地回答 HashMap 流程？

1. 计算哈希：通过扰动函数处理 hashCode。

2. 查找桶位：通过 (n-1) & hash 定位。

3. 处理碰撞：

   • 无碰撞：直接存。

   • 有碰撞：equals 比较 Key。相同覆盖，不同则挂在链表后。

4. 形态转换：链表长度达到 8 且数组长达 64，转红黑树。

5. 检查扩容：size > threshold，触发 resize 翻倍扩容。

---

结语： 掌握了 HashMap 的源码，你对 Java 集合的理解就上了一个大台阶。它不仅是面试的重点，更是我们理解高性能代码设计的绝佳案例。

如果你对红黑树的左旋右旋依然感到头大，评论区留言！