实现原理

一、HashMap底层数据结构

HashMap底层采用**哈希表（数组+链表/红黑树）**结构，结合了数组的快速随机访问和链表/红黑树的冲突处理能力：

• JDK1.7及之前：数组 + 链表（拉链法）
• JDK1.8及之后：数组 + 链表 + 红黑树，当链表长度≥8且数组长度≥64时，链表转为红黑树；当链表节点数≤6时，红黑树退化为链表

---

二、核心操作流程（put操作）

1. 计算哈希值：调用 key.hashCode()，再通过 hash() 方法（(h = key.hashCode()) ^ (h >>> 16)）扰动计算，减少哈希冲突
2. 确定数组下标：通过 tab[i = (n - 1) & hash] 计算元素在数组中的位置（n为数组长度，需为2的幂）
3. 处理下标位置元素：
   • 若该位置无元素，直接插入新节点
   • 若该位置有元素，判断key是否相同：
     • key相同：覆盖原value值
     • key不同（哈希冲突）：将元素存入链表或红黑树中
4. 扩容与树化：当元素数量超过负载因子（默认0.75）×数组长度时，触发扩容；当链表长度≥8且数组长度≥64时，链表转为红黑树

---

三、JDK1.7与JDK1.8的核心区别

特性	JDK1.7	JDK1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
冲突处理	仅链表存储，无红黑树优化	链表长度≥8且数组长度≥64时转为红黑树
插入方式	头插法（新元素插入链表头部）	尾插法（新元素插入链表尾部）
扩容机制	头插法可能导致链表死循环	尾插法避免死循环，红黑树拆分优化

---

四、面试高频问题解析

1. 问：HashMap的实现原理是什么？答： HashMap底层采用数组+链表/红黑树的哈希表结构。put元素时，通过key的hashCode和扰动函数计算数组下标，若下标位置无元素则直接插入；若有元素且key相同则覆盖值，key不同则存入链表/红黑树。当链表过长且数组容量足够时，链表转为红黑树优化查询效率。

2. 问：为什么JDK1.8要引入红黑树？答： 当链表过长时，查询效率会从O(1)退化为O(n)，红黑树可将查询时间复杂度优化为O(log n)，提升极端情况下的性能，同时避免因大量哈希冲突导致的系统性能问题。

3. 问：HashMap的扩容机制是什么？答： 当元素数量超过负载因子（默认0.75）×数组长度时，触发扩容，数组容量变为原来的2倍。扩容时会重新计算元素的下标位置，JDK1.8中红黑树会在节点数≤6时退化为链表，减少维护开销。

4. 问：为什么HashMap的数组长度必须是2的幂？答： 为了使 (n - 1) & hash 能均匀分布元素下标，减少哈希冲突。若n为2的幂，n - 1 的二进制全为1，& 运算可保证结果在 [0, n-1] 范围内，且分布均匀；若n不是2的幂，会导致部分下标无法被访问，冲突概率增加。