一、HashMap 的区别（1.7 vs 1.8）

1. 底层数据结构

• JDK 1.7

  • 数组 + 链表（Entry[] + 单向链表）。

• JDK 1.8

  • 数组 + 链表 + 红黑树（Node[]，当链表长度 > 8 且数组容量 > 64 时，链表转为红黑树）。

---

2. 插入方式

• 1.7：头插法

  • 新元素放在链表头部，导致链表反转。

  • 在多线程环境下可能出现 环形链表，导致死循环（扩容时尤为危险）。

• 1.8：尾插法

  • 新元素放在链表尾部，保持插入顺序。

  • 避免了 1.7 中链表反转导致的死循环问题。

---

3. 扩容机制

• 1.7

  • 单线程扩容，迁移时链表会倒置。

• 1.8

  • 扩容时 链表不会反转，并且会根据 hash 高位决定元素去新数组的 原位置 或者 原位置 + oldCap，提升迁移效率。

---

4. 哈希算法

• 1.7

  • 高位参与运算，但扰动函数较复杂，性能一般。

• 1.8

  • 引入更简单高效的扰动函数（hashcode 高位与低位做异或），减少冲突。

---

5. 性能

• 1.7

  • 链表查找：O(n)

  • 插入头插法：快，但容易问题。

• 1.8

  • 链表查找：O(n)，冲突严重时自动转为红黑树，查找降为 O(logn)。

  • 插入尾插法，更安全。

---

📌 小结

• 1.7：数组 + 链表，头插法，链表反转，扩容危险。

• 1.8：数组 + 链表 + 红黑树，尾插法，扩容安全，性能更高。

---

二、ConcurrentHashMap 的区别（1.7 vs 1.8）

1. 底层数据结构

• 1.7

  • Segment + HashEntry

  • 整个 Map 被分成若干 Segment，每个 Segment 内部维护一个 HashEntry 数组。

• 1.8

  • Node[] + 链表 + 红黑树

  • 去掉了 Segment，直接用 Node 数组 + CAS + synchronized。

    • 

    • ConcurrentHashMap[1.8] 的操作流程（以 put 为例）：

      • (1)初始化阶段
        当第一次往 Map 里放数据时，ConcurrentHashMap 还没有内部数组（table）。

        • 它会用 CAS（乐观锁） 去创建数组，避免多个线程同时初始化。

        • 如果 CAS 失败（说明别的线程抢先创建了），那我就不创建了，直接用别人创建的。

      • (2)插入数据阶段

        • 先计算 key 对应的位置（hash 算法 -> index）。

        • 2.1 如果那个位置是空的：直接用 CAS（乐观锁） 把节点放进去。

          如果 CAS 成功 → 插入完成。
          如果 CAS 失败（说明有别的线程也在放数据），那就重试。

        • 2.2  如果那个位置不为空（已经有链表或树）：
          那么就会进入 synchronized（悲观锁），对那个桶（bin）加锁。

          • 在锁的保护下，安全地遍历链表/红黑树，插入或更新节点。

          • 插入完再判断这个桶是否太长，太长就转为红黑树。

      • (3)总的来说

        • CAS（乐观锁）：用于 初始化数组、往空桶插入数据。

        • synchronized（悲观锁）：用于 处理冲突桶（已有数据的链表/树）。

        • 这样设计的好处：

          • 大部分情况下（位置为空），用 CAS 就能完成操作，性能高。

          • 少数情况下（位置冲突），才用 synchronized，保证线程安全。

---

2. 锁机制

• 1.7

  • 分段锁（Segment 锁）

  • 每个 Segment 用 ReentrantLock 控制。

  • 默认并发度 16，意味着最多 16 个线程能同时写。

• 1.8

  • CAS + synchronized

  • 插入时先 CAS，失败才加 synchronized。

  • 锁粒度是 桶（Node 链表头 / 红黑树根），并发度几乎等于桶数，远高于 1.7。

---

3. 插入方式

• 1.7：头插法

  • 新节点插入链表头，链表会反转。

• 1.8：尾插法

  • 新节点插入链表尾，避免链表反转和死循环问题。

---

4. 扩容机制

• 1.7

  • 单线程扩容，锁住整个 Segment。

  • 扩容时链表反转，性能较差。

• 1.8

  • 多线程协助扩容

  • 线程通过分段迁移数据来提升扩容效率。

  • 使用 ForwardingNode 标记已经迁移过的桶，避免重复迁移。

---

5. 查询效率

• 1.7

  • 查找依赖链表，冲突严重时查找效率 O(n)。

• 1.8

  • 链表转为红黑树后，查找效率 O(logn)。

---

6. 性能对比

特性	ConcurrentHashMap 1.7	ConcurrentHashMap 1.8
数据结构	Segment + HashEntry	Node + 链表 + 红黑树
锁机制	Segment 锁（ReentrantLock）	CAS + synchronized
锁粒度	Segment（默认16）	桶级别（Node）
插入方式	头插法	尾插法
扩容机制	单线程扩容，链表反转	多线程协助扩容，ForwardingNode 标记
查询效率	链表 O(n)	链表 O(n)，树化后 O(logn)
并发度	受限于 Segment 数量	接近桶数，远高于 1.7

---

📌 小结

• 1.7：Segment 分段锁 + 头插法 + 单线程扩容，性能受限。

• 1.8：CAS + synchronized + 尾插法 + 多线程扩容 + 红黑树，性能更高。

---

三、整体对比图（记忆口诀）

Map 类型	JDK 1.7	JDK 1.8
HashMap	数组+链表，头插法，单线程扩容，链表 O(n)	数组+链表+红黑树，尾插法，单线程扩容但更安全，树化 O(logn)
ConcurrentHashMap	Segment+HashEntry，分段锁，头插法，单线程扩容	Node+链表+红黑树，CAS+synchronized，尾插法，多线程扩容

---

📌 一句话记忆：

• HashMap：1.7 链表头插反转，1.8 尾插+树化更安全。

• ConcurrentHashMap：1.7 Segment 分段锁，1.8 CAS+synchronized 桶级锁+红黑树+多线程扩容。