JDK 1.8 对 HashMap 进行了多维度的优化，是以空间换时间的典型案例，通过引入红黑树、简化哈希计算、优化扩容逻辑，在保持线程不安全特性的同时，显著提升了在大数据量和高冲突场景下的性能。以下是对比分析：

1. 数据结构底层实现

• JDK 1.8 之前：由数组 + 链表组成，数组是 HashMap 的主体，链表则是为了解决哈希冲突而存在的
• JDK 1.8 及之后：由数组 + 链表 + 红黑树组成，当链表长度超过阈值（默认 8）且数组容量≥64 时，链表转为红黑树，链表会转换为红黑树，以提高查询效率

• 版本	核心结构
  JDK 1.7 及之前	数组 + 单向链表 所有哈希冲突的元素都通过链表存储
  JDK 1.8 及之后	数组 + 单向链表 + 红黑树 当链表长度超过阈值（默认 8）且数组容量≥64 时，链表转为红黑树； 当红黑树节点数少于 6 时，退化为链表

红黑树引入的意义：
链表查询时间复杂度为 O (n)，红黑树为 O (log n)。在哈希冲突严重（如恶意构造哈希值）时，JDK 1.8 性能提升显著。

2. 哈希冲突解决策略

（1）元素插入方式

• JDK 1.7：采用 头插法（新元素插入链表头部）
  原因：认为新插入的元素更可能被访问，提升缓存命中率。
  问题：多线程扩容时可能导致链表成环（扩容时转移节点顺序反转，引发死循环）。

• JDK 1.8：采用 尾插法（新元素插入链表尾部）
  解决：避免了多线程下的链表成环问题（但 HashMap 本身仍非线程安全，需用 ConcurrentHashMap）。

（2）链表转红黑树的触发条件

JDK 1.8 新增逻辑：
当链表长度 > 阈值（TREEIFY_THRESHOLD = 8），且数组容量 ≥ MIN_TREEIFY_CAPACITY = 64 时，链表转为红黑树。
若数组容量 < 64，则优先扩容而非树化（避免因数组过小导致频繁树化 / 退化）。

3. 哈希值计算逻辑

哈希值计算的核心是减少哈希冲突，让元素在数组中分布更均匀。

• JDK 1.7：复杂的扰动计算（4 次移位 + 3 次异或）

  static int hash(int h) {
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
  }
  

   

  目的：通过多次扰动让哈希值的高位也参与运算，减少冲突。

• JDK 1.8：简化的扰动计算（1 次移位 + 1 次异或）

  static final int hash(Object key) {
      int h;
      // key为null时hash值为0，否则取hashCode的高16位异或低16位
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

   

  优化点：保留高位信息（高 16 位与低 16 位异或），同时减少计算量。

4. 扩容机制

扩容是当元素数量超过阈值（capacity * loadFactor）时，将数组容量翻倍（始终为 2 的幂）的过程。

（1）元素迁移逻辑

• JDK 1.7：需重新计算每个元素的哈希值，并通过 indexFor(hash, newCapacity) 定位新位置

  // 1.7中重新计算索引
  static int indexFor(int h, int length) {
      return h & (length - 1);
  }
  

• JDK 1.8：无需重新计算哈希值，通过以下逻辑定位新位置：
  若元素哈希值与原容量的与运算结果为 0（(e.hash & oldCap) == 0），则新索引 = 原索引；否则，新索引 = 原索引 + oldCap。
  原理：容量翻倍后（从 2ⁿ到 2ⁿ⁺¹），新索引仅取决于哈希值的第 n 位（0 或 1），无需全量重算。

（2）扩容时的节点处理

• JDK 1.7：扩容时会将链表节点逆序迁移（头插法导致）。
• JDK 1.8：扩容时保持链表节点顺序（尾插法），且红黑树会拆分并可能退化为链表（若节点数少于 6）。

5. 初始化与阈值计算

• JDK 1.7：
  构造函数中若指定初始容量，会先计算大于等于该值的最小 2 的幂（如指定 10，则初始容量为 16），阈值初始化为 capacity * loadFactor。

• JDK 1.8：
  构造函数中仅记录初始容量，不立即计算 2 的幂，而是在第一次 put 时通过 tableSizeFor() 计算实际容量（懒加载）。
  阈值计算逻辑：

  • 首次 put 时，阈值 = 初始容量（已调整为 2 的幂） * 负载因子
  • 后续扩容时，阈值 = 新容量 * 负载因子

6.性能对比

• 查询效率：
  JDK 1.8 在哈希冲突严重时优势明显（红黑树 O (log n) vs 链表 O (n)）。
• 插入效率：
  JDK 1.8 因哈希计算简化、扩容迁移逻辑优化，插入速度更快。
• 内存占用：
  红黑树节点（TreeNode）比链表节点（Node）占用更多内存（需存储父节点、左右孩子等信息），但在大数据量下性价比更高。