Java高频面试之集合-17

hello啊，各位观众姥爷们！！！本baby今天来报道了！哈哈哈哈哈嗝🐶

面试官：JDK 8 对 HashMap 主要做了哪些优化呢？为什么要这么做？

JDK 8 对 HashMap 的主要优化及原因

JDK 8 对 HashMap 的实现进行了多项关键优化，显著提升了其在高冲突场景下的性能和内存效率。以下是主要优化点及其设计动机：

一、链表转红黑树（Treeify）

优化内容：
当单个桶（Bucket）中的链表长度超过阈值（默认 8）且哈希表容量 ≥ 64 时，链表会被转换为红黑树；当树节点数 ≤ 6 时，红黑树退化为链表。

原因：

• 解决链表过长导致的性能问题：
  链表查询的时间复杂度为 O(n)，而红黑树的查询复杂度为 O(log n)。在高冲突场景下，树化能显著减少查找时间。
• 平衡内存与性能：
  红黑树节点（TreeNode）的内存开销高于链表节点（Node），因此设置退化的阈值（6）以避免小规模数据下的内存浪费。

源码示例：

// 链表转红黑树的条件（容量 ≥ 64 且链表长度 ≥ 8）
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
    break;
}

二、哈希函数优化

优化内容：
JDK 8 改进了哈希值计算方式，通过 高位异或（XOR） 增强散列性：

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

原因：

• 减少哈希冲突：
  将哈希码的高 16 位与低 16 位异或，使得更多位数参与索引计算（(n - 1) & hash），避免仅依赖低位导致的冲突。
• 提升分布均匀性：
  例如，若容量为 16（二进制 10000），原哈希码低位重复性高，异或高位后分布更均匀。

三、扩容机制优化

优化内容：
扩容时，通过 高位掩码判断 元素的新位置，避免重新计算哈希值：

if ((e.hash & oldCap) == 0) {
    // 新索引 = 原索引
} else {
    // 新索引 = 原索引 + 原容量
}

原因：

• 减少计算开销：
  原扩容需重新计算所有元素的哈希值和索引，JDK 8 直接通过哈希值的特定位判断位置，性能提升显著。
• 元素均匀拆分：
  扩容后，原桶中的元素被均分到两个新桶中（低位桶和高位桶），减少链表或树的深度。

四、树化条件优化

优化内容：
链表转红黑树需满足 容量 ≥ 64，否则优先扩容而非树化。

原因：

• 避免小容量下过早树化：
  若容量较小（如 16），扩容可有效减少冲突概率，此时树化反而增加内存开销且收益有限。
• 优先利用扩容分散冲突：
  扩容后哈希分布更均匀，可能自然解决冲突，减少树化需求。

五、性能对比与设计权衡

六、总结与适用场景