说说 Java 中 HashMap 的原理？

HashMap 原理详解

【核心定义】

HashMap 是 Java 中基于哈希表实现的、用于存储键值对（Key-Value）的非线程安全数据结构，它通过计算键的哈希值来快速定位存储位置，提供平均 O(1) 时间复杂度的查找、插入和删除操作。

【关键要点】

数据结构演进：JDK 1.7 采用数组 + 单向链表，JDK 1.8 优化为数组 + 单向链表/红黑树
哈希算法：通过 (h = key.hashCode()) ^ (h >>> 16) 进行二次哈希，减少哈希碰撞
定位机制：使用 (n - 1) & hash 计算数组下标（n 为数组长度）
扩容策略：当元素数量超过阈值（容量 × 负载因子）时，容量翻倍并重新哈希
线程不安全：多线程环境下可能产生死循环、数据丢失等问题

【深度推导/细节】

1. 哈希冲突解决机制

JDK 1.7 链表插入：采用头插法，新节点插入链表头部

// JDK 1.7 头插法代码逻辑
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 新节点指向原头节点
}

JDK 1.8 优化逻辑：

链表转树阈值：当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树
树转链表阈值：当树节点数 ≤ 6 时，红黑树退化为链表
插入方式：改为尾插法，避免多线程下的死循环问题

2. 扩容机制深度分析

扩容触发条件：

元素数量 > 容量 × 负载因子（默认 0.75）
链表长度 ≥ 8 但数组长度 < 64 时（优先扩容而非树化）

扩容过程（JDK 1.8 优化）：

Step 1: 创建新数组，大小为原数组的 2 倍（保持 2 的幂次）
Step 2: 遍历原数组每个桶
Step 3: 对每个节点重新计算位置：
    - 情况 A：节点无后继节点 → 直接计算新位置：newIndex = e.hash & (newCap - 1)
    - 情况 B：节点是树节点 → 调用红黑树的 split 方法
    - 情况 C：节点是链表 → 使用高低位分组法优化

高低位分组法（JDK 1.8 关键优化）：

// 将链表拆分为两个子链表：低位链表和高位链表
Node<K,V> loHead = null, loTail = null; // 低位链表（索引不变）
Node<K,V> hiHead = null, hiTail = null; // 高位链表（索引 = 原索引 + 原容量）

// 判断逻辑：只需检查 hash 值的第 n 位（n = 原容量的二进制位数）
if ((e.hash & oldCap) == 0) {
    // 放入低位链表
} else {
    // 放入高位链表
}

优势：避免对每个节点重新计算哈希，只需一次位运算判断，性能提升显著。

3. 关键数字设计原理

参数	值	设计理由
默认初始容量	16	2 的幂次，便于位运算计算下标
负载因子	0.75	空间与时间的平衡点（数学推导：泊松分布）
树化阈值	8	根据泊松分布，链表长度达到 8 的概率仅 0.00000006
退化阈值	6	避免频繁的树-链表转换（设置 2 的缓冲区间）
最小树化容量	64	避免早期小表过度树化，优先扩容

【关联/对比】

HashMap vs ConcurrentHashMap

维度	HashMap	ConcurrentHashMap（JDK 1.8）
线程安全	不安全	安全（CAS + synchronized）
锁粒度	无锁	桶级别锁（锁住链表头/树根）
空键值	允许 1 个 null key	不允许 null key/value
迭代器	fail-fast	弱一致性

JDK 1.7 vs JDK 1.8 核心差异

数据结构：1.7 纯链表 → 1.8 链表+红黑树
插入方式：1.7 头插法 → 1.8 尾插法（解决死循环）
扩容计算：1.7 全部 rehash → 1.8 高低位分组
哈希算法：1.7 多次扰动 → 1.8 一次扰动 + 高位参与

『面试官追问』

高频追问 1：为什么负载因子是 0.75？

数学依据：基于泊松分布的概率统计

负载因子过高（如 0.9）：空间利用率高，但哈希冲突概率剧增，链表变长
负载因子过低（如 0.5）：冲突减少，但空间浪费严重，频繁扩容
0.75 是经验最优值：在理想哈希函数下，桶中元素个数符合 λ=0.5 的泊松分布

高频追问 2：多线程下 HashMap 的死循环问题（JDK 1.7）

产生场景：两个线程同时执行扩容操作

线程 A 执行到：Entry<K,V> next = e.next;  // 记录 next
线程 B 完成扩容，链表顺序反转
线程 A 继续执行，将 e 插入新表头部，形成环形链表

JDK 1.8 解决方案：

改为尾插法，保持链表原有顺序
使用高低位分组，避免链表反转

高频追问 3：为什么容量必须是 2 的幂次？

位运算优化：

计算下标：index = hash & (n - 1) 等价于 hash % n
当 n 为 2 的幂时，n - 1 的二进制全是 1（如 15=0b1111）
位运算 & 比取模 % 效率高 10 倍以上

高频追问 4：红黑树退化为链表的阈值为什么是 6 而不是 8？

缓冲设计：

树化阈值 8，退化阈值 6，形成 2 的缓冲区间
避免频繁的树-链表转换（如元素数在 7-8 间反复变化）
减少树化/退化的开销，提升稳定性

高频追问 5：HashMap 的 key 为什么要重写 hashCode 和 equals？

哈希一致性原则：

hashCode 相同 → equals 不一定为 true（哈希碰撞）
equals 为 true → hashCode 必须相同（否则找不到对象）
默认 Object.hashCode() 返回内存地址，不满足业务需求

【最佳实践建议】

初始化容量：预估元素数量，避免频繁扩容

// 预估 100 个元素，负载因子 0.75
Map<String, Object> map = new HashMap<>(134); // 100/0.75 ≈ 134

Key 设计：使用不可变对象（如 String、Integer），避免哈希值变化
并发场景：使用 ConcurrentHashMap 或 Collections.synchronizedMap()
遍历优化：使用 entrySet() 而非 keySet() + get()，减少哈希计算

总结：HashMap 的设计体现了空间与时间的精妙平衡，通过哈希算法、动态扩容、数据结构优化（链表→红黑树）等机制，在大多数场景下提供高效的键值存储。理解其底层原理不仅有助于面试，更能指导实际开发中的性能优化和并发安全处理。

# 说说 Java 中 HashMap 的原理？