HashMap 是 Java 面试和日常开发中的重中之重。本文将从底层数据结构、核心存取原理、扩容机制以及并发安全四个维度，结合 JDK 1.7 与 1.8 的差异进行彻底拆解。

1. 底层数据结构

HashMap 的本质是 数组 + 链表 (散列表)。

• JDK 1.7: 纯粹的 数组 + 链表。
• JDK 1.8: 升级为 数组 + 链表 + 红黑树。

核心参数：

• 默认初始化容量 (Capacity): 16
• 默认负载因子 (Load Factor): 0.75 (当元素达到 16 * 0.75 = 12 时触发扩容)

为什么要引入红黑树？

当 Hash 冲突非常严重时，链表会变得很长。

• 链表查询复杂度: $O(n)$
• 红黑树查询复杂度: $O(\log n)$

转换条件 (JDK 1.8):

当满足以下两个条件时，链表转换为红黑树：

1. 链表长度 $>8$
2. 数组长度 $\ge 64$ (若链表长于8但数组小于64，优先选择扩容而不是转树)

---

2. 核心原理：存 (Put) 与 取 (Get)

2.1 Hash 算法与索引定位

HashMap 不是直接使用 Key 的 hashCode()，而是进行了二次 Hash (扰动函数)，目的是减少 Hash 冲突。

步骤 1：计算 Hash 值

JDK 1.8 源码算法：让高 16 位参与运算。

Java

static final int hash(Object key) {
    int h;
    // 如果 key 为 null，hash 为 0
    // 否则：h = key.hashCode() ^ (h >>> 16)
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

步骤 2：计算数组索引

利用位运算替代取模，效率更高（前提是数组长度必须是 2 的幂次方）：

$$Index=(n-1)\&hash$$

2.2 Put 方法流程 (JDK 1.8)

1. 判断数组: 若数组为空，先进行初始化（扩容）。
2. 计算下标: 根据 Hash 值计算下标 i。
3. 无冲突: 若 table[i] 为空，直接插入 Node。
4. 有冲突:
   • 覆盖: 若 key 相同 (hash 一样且 equals 为 true)，覆盖 value。
   • 红黑树: 若该节点是 TreeNode，调用红黑树插入方法。
   • 链表: 若是链表，遍历到尾部插入 (尾插法)。
     • 插入后，判断链表长度是否 $>8$，若是则尝试转为红黑树。
5. 检查扩容: 插入成功后，若 size > threshold，触发扩容。

2.3 Get 方法流程

1. 计算 key 的 hash 值。
2. 通过 (n-1) & hash 找到数组下标。
3. 如果不为空，检查第一个节点（对比 hash 和 equals），命中则返回。
4. 如果是红黑树，按照树查找。
5. 如果是链表，遍历链表查找。

---

3. 扩容机制 (Resize) 的奥秘

当 HashMap 中的元素个数超过 容量 * 负载因子 时，会创建一个大小为原数组 2倍 的新数组。

关键点：数据迁移 (Rehash)

将旧数组的数据移动到新数组，JDK 1.7 和 1.8 有巨大区别。

• JDK 1.7: 重新计算每个元素的 Hash 值，重新计算下标。

• JDK 1.8 (高低位优化):

  不需要重新计算 Hash。因为数组扩容是 2 倍，索引的变化只取决于 Hash 值在新增的高位 bit 是 0 还是 1。

  • 位是 0 (低位): 索引不变 [Original Index]
  • 位是 1 (高位): 索引变为 [Original Index + Old Cap]

优势: 省去了重新计算 Hash 的时间，且将冲突的链表元素拆分到了两个位置，降低了链表长度。

---

4. 线程安全性分析

结论：HashMap 是线程不安全的。

为什么不安全？

1. JDK 1.7 (头插法 - 死循环):

   在并发扩容时，多线程迁移链表。因为是头插法，会颠倒链表顺序。如果线程挂起再恢复，可能导致链表形成环状 (Circle)。后续 get 操作会陷入死循环。

2. JDK 1.8 (尾插法 - 数据覆盖):

   虽然修复了死循环问题（保持顺序），但在并发插入时：

   • 线程 A 计算出下标，准备插入（还没插）。
   • 线程 B 刚好也插入该位置，并完成。
   • 线程 A 继续执行，直接覆盖了线程 B 的数据，导致数据丢失。

---

5. 并发解决方案：ConcurrentHashMap

如果需要线程安全，请放弃 HashMap，选择以下方案。

5.1 备选方案

• Hashtable: 全局锁，性能极差（不推荐）。
• Collections.synchronizedHashMap(): 包装类，也是粗粒度锁（一般不推荐）。
• ConcurrentHashMap: 推荐方案，高并发首选。

5.2 ConcurrentHashMap 深度解析

JDK 1.7：分段锁 (Segment)

• 原理: 将数据分为 16 个段 (Segment)，每个 Segment 就是一个小的 HashMap。
• 锁机制: 继承 ReentrantLock。
• 效果: Put 操作时，只锁住当前 key 所在的那个 Segment，其他段不受影响。理论上支持 16 个线程并发写。

JDK 1.8：CAS + Synchronized (性能起飞)

抛弃了 Segment，结构与 HashMap 1.8 保持一致（数组+链表+红黑树）。

• 锁粒度更细: 锁的不是段，而是数组的头节点 (Node/Bucket)。
• 实现原理:
  1. 没有冲突时 (空桶): 使用 CAS (Compare And Swap) 乐观锁技术直接尝试插入。如果失败（说明有其他线程插入了），则自旋重试。
  2. 有冲突时 (非空): 使用 synchronized 锁住当前链表或红黑树的头节点。
  3. 扩容时: 检测到节点 hash 为 MOVED (-1)，当前线程会通过 helpTransfer 方法协助扩容，而不是阻塞等待。

---

6. 面试必问：HashMap vs HashTable

特性	HashMap	HashTable
线程安全	不安全	安全 (方法全带 synchronized)
Null 值	Key 和 Value 都可以为 null	Key 和 Value 都不允许为 null
效率	高 (无锁竞争)	低 (全表锁，并发度为 1)
Hash 算法	二次 Hash (混合高位)	直接使用 key 的 hashCode
底层结构	数组+链表+红黑树	数组+链表
扩容方式	当前容量 $\times 2$	当前容量 $\times 2+1$

---

总结

1. 结构: JDK 1.8 引入红黑树优化了极端情况下的查询性能。
2. 扩容: 1.8 使用高低位运算代替取模，扩容更高效。
3. 并发: HashMap 绝对不要在多线程下使用。
4. 替代: 并发场景请使用 ConcurrentHashMap，JDK 1.8 版本通过 CAS + synchronized 达到了极高的并发性能。