问题

1. HashMap的底层数据结构是什么？JDK 1.8之后有哪些优化？

标准答案

HashMap 的底层数据结构是 数组（table）+ 链表 + 红黑树 的组合。在 JDK 1.7 及之前，HashMap 采用 数组 + 链表 结构，在哈希冲突严重时，查询性能可能退化到 O(n)。JDK 1.8 之后进行了以下优化：

1. 引入红黑树优化查询性能：当单个桶内的链表长度 ≥ 8 且数组大小 ≥ 64 时，链表会转换为红黑树，将最坏情况下的查找复杂度从 O(n) 降至 O(log n)。
2. 扩容时采用尾插法，解决 JDK 1.7 的并发死循环问题：JDK 1.7 采用头插法，在多线程扩容时可能导致环形链表，而 JDK 1.8 采用尾插法，避免了这一问题。
3. 优化哈希函数，提高哈希分布均匀性：JDK 1.8 采用高位与低位异或（h ^ (h >>> 16)） 的方式减少哈希冲突，使 key 分布更加均匀。

答案解析

1. HashMap 的底层数据结构

在 JDK 1.8 及之后，HashMap 的底层采用 数组 + 链表 + 红黑树 结构，其核心数据结构如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 链表的下一个节点
}

数组（table）
HashMap 通过 table 数组存储键值对，每个索引位置（桶）可能包含一个 Node<K,V> 或 TreeNode<K,V>。

链表
如果发生哈希冲突（多个 key 计算出的哈希值相同），则会在该桶内形成链表，查找性能为 O(n)。

红黑树
当桶内链表长度 ≥ 8 且数组长度 ≥ 64 时，链表会转换为红黑树，查找复杂度从 O(n) 降至 O(log n)。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent, left, right;
    boolean red;  // 是否是红色节点
}

当链表长度 ≤ 6 时，红黑树会退化回链表，以降低红黑树的维护成本。

2. JDK 1.8 之后的优化

(1) 引入红黑树优化链表查询性能

JDK 1.7 采用纯链表结构，哈希冲突严重时，查询性能可能降至 O(n)。JDK 1.8 之后，当链表长度 ≥ 8 且数组大小 ≥ 64 时，会转换为红黑树，查询复杂度优化为 O(log n)。

转换逻辑如下：

if (binCount >= TREEIFY_THRESHOLD) // TREEIFY_THRESHOLD = 8
    treeifyBin(tab, hash);

为什么转换条件是 ≥ 8 而不是更早？

• 统计分析表明，哈希表的负载因子 0.75 时，链表长度 ≥ 8 的概率较低，因此 8 作为阈值是一个平衡点。
• 过早转换为红黑树，会引入额外的维护成本（插入/删除需要 O(log n)）。

(2) 解决 JDK 1.7 并发扩容的死循环问题

JDK 1.7 采用头插法扩容，在多线程环境下可能形成环形链表，导致 get() 方法陷入死循环。

e.next = table[i];  
table[i] = e;  // 头插法

JDK 1.8 采用尾插法，避免链表顺序反转，防止死链问题。

if (p.next == null) { 
    p.next = newNode(hash, key, value, null); // 尾插法
}

(3) 哈希函数优化

JDK 1.7 计算索引时，采用多个位运算扰动哈希值，计算开销较大。JDK 1.8 采用高低位异或运算，提高了计算效率，并减少哈希冲突。

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

这样可以降低低位哈希冲突，提高哈希分布均匀性，使查找性能更加稳定。

(4) 扩容机制优化

HashMap 采用 懒加载，首次插入数据时才初始化数组。

扩容步骤：

1. 计算新容量（原数组容量 2x）。
2. 重新计算 key 的索引，重新分配节点。
3. JDK 1.8 采用高低位拆分法，避免重新计算哈希值，提高性能。

int newIndex = (oldIndex & oldCap) == 0 ? oldIndex : oldIndex + oldCap;

这样可以保证数据均匀分布在新数组中，减少数据迁移的计算量。

JDK 1.7 vs JDK 1.8 主要区别

版本	结构	哈希冲突处理	扩容策略	线程安全问题
JDK 1.7	数组 + 链表	头插法（容易引发死链）	先扩容再迁移数据	存在死循环风险
JDK 1.8	数组 + 链表 + 红黑树	尾插法（防止死循环）	先迁移再扩容	解决死循环问题

深入追问

🔹 为什么 HashMap 采用 0.75 作为负载因子？能改成 0.5 或 1.0 吗？
🔹 HashMap 在多线程环境下有哪些问题？如何解决？
🔹 ConcurrentHashMap 与 HashMap 的数据结构有何不同？
🔹 扩容时的 rehash 是如何优化的？会不会影响性能？

相关面试题

• ConcurrentHashMap 的实现原理是什么？
• HashMap 与 TreeMap 的区别？
• 为什么 HashMap 的初始容量建议设置为 2 的幂？
• 为什么 HashMap 的默认初始容量是 16？能改成 10 吗？

这就是 JDK 1.8 之后对 HashMap 的优化和底层细节分析。想深入研究某个部分，可以继续讨论！