一、 底层存储结构的演变

HashMap 的本质是一个哈希表。为了平衡查询效率与内存开销，它的形态随数据量动态演变：

• JDK 7 及以前：数组 + 链表。

• JDK 8 及以后：数组 + 链表 + 红黑树。

引入红黑树的原因：当哈希冲突严重导致链表过长时，查询复杂度会从 $O(1)$ 退化为 $O(n)$。红黑树可以将极端情况下的查询效率提升至 $O(\log n)$。

---

二、 核心参数（性能的天平）

在 HashMap 源码中，这四个常数决定了它的空间利用率和查询速度：

参数	默认值	作用
INITIAL_CAPACITY	16	初始桶（Bucket）数量，必须是 2 的幂次方。
LOAD_FACTOR	0.75	负载因子。衡量数组填满程度，是“空间”与“时间”的权衡。
TREEIFY_THRESHOLD	8	树化阈值。链表长度 $\ge 8$ 且数组长度 $\ge 64$ 时转为红黑树。
UNTREEIFY_THRESHOLD	6	退化阈值。红黑树节点减少到 6 时，退回链表。

---

三、 寻址算法：位运算的艺术

HashMap 性能极高的核心原因在于其索引定位算法：

1. 扰动处理（Hash Function）

为了防止低质量哈希函数导致碰撞，HashMap 执行了“高低位异或”：

Java

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

目的：让 hashCode 的高 16 位也参与到索引计算中，增加随机性，减少碰撞。

2. 取模优化

定位下标公式：index = (n - 1) & hash （n 为数组长度）。

• 设计精妙点：由于 $n$ 始终是 2 的幂次方，(n - 1) & hash 的效果等同于 hash % n。

• 性能提升：位运算的性能远高于取模运算。

---

四、 扩容机制（Resize）深度解析

当 size > capacity * loadFactor 时，HashMap 会发起“搬家”操作：

1. 容量翻倍：创建一个两倍大小的新数组（如 $16 \rightarrow 32$）。

2. 数据迁移（Rehash）：

   • JDK 7：头插法迁移。多线程环境下可能导致链表形成闭环（死循环）。

   • JDK 8：尾插法迁移。不再重新计算 hash，而是利用 2 的幂次方特性：元素要么留在原位，要么移动到“原位置 + 旧容量”的位置。

   • 判定逻辑：只需判断 (e.hash & oldCap) == 0，极其高效。

---

五、 那些面试中的“终极追问”

Q1：为什么是 8 树化，6 退化？

• 为什么选 8？：根据泊松分布，在负载因子 0.75 下，同一个桶碰撞 8 次的概率约为千万分之六。选择 8 是为了让红黑树仅在遭到哈希攻击或极端罕见情况下才启用。

• 为什么退化是 6 而不是 7？：防止抖动（Hysteresis）。如果阈值设为相同，当一个桶的元素在临界点反复增删时，会触发频繁的树与链表转换，严重损耗性能。

Q2：HashMap 为什么线程不安全？

1. 数据覆盖：多线程并发 put 导致数据互相覆盖。

2. 死循环（JDK 7）：扩容时的头插法会导致环形链表。

3. Fast-Fail：迭代时修改结构会抛出 ConcurrentModificationException。

Q3：如何解决线程安全问题？

• ConcurrentHashMap（首选）：JDK 8 锁的是桶的头节点（Node），结合 CAS 与 synchronized，并发度极高。

• Collections.synchronizedMap：锁住整个对象，性能较差。

• Hashtable：全表锁，已过时。

---

六、 总结

HashMap 的设计集中体现了 Java 对于性能的极致追求：通过位运算代替取模，通过扰动函数均衡分布，通过红黑树保底性能，通过双阈值防止抖动。

---

作者：Li Caijun

关注我，带你深入 Java 底层架构！