一句话总结
HashMap 底层采用数组（Node[] table）+ 链表 + 红黑树（JDK 8+）实现。通过 key 的 hashCode 经扰动函数计算 hash 值，再用 (n-1) & hash 定位桶下标。冲突用拉链法解决，链表长度 ≥ 8 且数组长度 ≥ 64 时树化为红黑树。当 size > capacity × loadFactor 时触发扩容（容量翻倍），rehash 时元素只可能留在原位或移到"原位+旧容量"。非线程安全，多线程环境用 ConcurrentHashMap。
初级理解
底层数据结构
JDK 8 中 HashMap 由三部分组成：
| 结构 | 作用 | 特点 |
|---|
| 数组 Node[] table | 主干，每个位置称为"桶（bucket）" | 容量必须是 2 的幂，默认 16 |
| 链表 | 解决 hash 冲突（拉链法） | Node 节点包含 hash、key、value、next |
| 红黑树 | 链表过长时转为树，提升查询效率 | JDK 8 新增，O(n) → O(log n) |
Node 节点结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // key 的 hash 值，put 时计算好存起来
final K key; // 键
V value; // 值
Node<K,V> next; // 指向下一个节点（链表结构）
}
put 流程（简化版）
1. 计算 key 的 hashCode()，再经扰动函数得到最终 hash
2. 通过 (n - 1) & hash 计算桶下标（n 是数组长度）
3. 桶为空 → 直接放入新节点
4. 桶有值 → 判断是链表还是红黑树，遍历比较 key
5. key 相同（hash 相等且 == 或 equals 为 true）→ 覆盖旧值
6. key 不同 → 追加到链表末尾或红黑树中
7. 插入后检查 size 是否超过 threshold，超过则扩容
// 最简单的使用示例
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("apple", 3); // 覆盖，size 仍为 2
System.out.println(map.get("apple")); // 3
System.out.println(map.size()); // 2
System.out.println(map.containsKey("banana")); // true
一句话总结：HashMap = 数组 + 链表 + 红黑树，通过 hash 值定位桶，冲突用链表/红黑树解决。
中级深入
hash 扰动函数 — 为什么不是直接用 hashCode？
Object.hashCode() 返回 int（32 位），如果直接用，当数组长度较小时（如默认 16），只有低 4 位参与取模运算，高位完全浪费，碰撞概率大增。
HashMap 的做法：将 hashCode 的高 16 位与低 16 位做异或运算，让高位特征也融入低位，使 hash 分布更均匀。
// JDK 8 HashMap.hash() 源码
static final int hash(Object key) {
int h;
// key 为 null 时 hash = 0（所以 HashMap 允许 null key）
// 否则：hashCode 高 16 位 异或 低 16 位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 举例：假设 hashCode = 0x12345678
// h >>> 16 = 0x00001234
// h ^ (h >>> 16) = 0x12345678 ^ 0x00001234 = 0x1234444C
// 高位 1234 的特征融入了低位 444C
putVal 源码逐行分析
以下是 JDK 8 HashMap.putVal() 的核心逻辑（省略部分细节）：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① table 为空则初始化（延迟初始化，节省内存）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ② 桶为空，直接新建节点放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// ③ 桶首节点就是目标 key，直接命中
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 桶中是红黑树，走树的插入逻辑
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// ⑤ 桶中是链表，遍历查找
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 尾插法
// 链表长度 ≥ 8，转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // 找到相同 key
p = e;
}
}
// ⑥ 存在相同 key，覆盖旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
// ⑦ 修改次数 +1（fail-fast 机制）
++modCount;
// ⑧ size 超过 threshold 则扩容
if (++size > threshold)
resize();
return null;
}
扩容机制（resize）— JDK 8 的关键优化
当 size > capacity × loadFactor（默认 16 × 0.75 = 12）时触发扩容，容量翻倍。扩容时需要将所有元素 rehash 到新数组。
JDK 8 的优化：因为容量始终是 2 的幂，扩容后每个元素的新位置只有两种可能：
- 原位置（hash 的新增位为 0）
- 原位置 + 旧容量（hash 的新增位为 1）
不需要重新计算 hash，只需判断 hash 在旧容量二进制位上的值即可。
// JDK 8 resize() 中的核心 rehash 逻辑
// oldCap = 16 (二进制 10000)
// 判断 hash & oldCap 是否为 0
// 为 0 → 留在原位
// 不为 0 → 移到 原位 + oldCap
Node<K,V> loHead = null, loTail = null; // 低位链表（留在原位）
Node<K,V> hiHead = null, hiTail = null; // 高位链表（移到原位+oldCap）
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 加入低位链表
if (loTail == null) loHead = e; else loTail.next = e;
loTail = e;
} else {
// 加入高位链表
if (hiTail == null) hiHead = e; else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位链表放回原位
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
// 高位链表放到 原位 + oldCap
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
链表树化条件
两个条件同时满足才会树化：
| 条件 | 阈值 | 原因 |
|---|
| 链表长度 | ≥ 8（TREEIFY_THRESHOLD） | 泊松分布：长度达到 8 的概率约 0.00000006 |
| 数组长度 | ≥ 64（MIN_TREEIFY_CAPACITY） | 数组太小时优先扩容而非树化 |
如果链表长度 ≥ 8 但数组长度 < 64，不会树化，而是优先扩容（扩容能有效分散元素，降低链表长度）。
// treeifyBin 源码片段
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组长度 < 64，不树化，优先扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 真正执行树化...
}
}
中级要点：扰动函数让 hash 更均匀；putVal 包含初始化、定位、冲突处理、覆盖、扩容五个步骤；扩容时用 hash & oldCap 判断新位置，避免重新计算 hash。
高级拓展
为什么容量必须是 2 的幂？
三个原因：
1. 位运算代替取模：(n - 1) & hash 等价于 hash % n，位运算比取模快一个数量级。前提是 n 为 2 的幂，(n-1) 的二进制才全是 1。
2. 均匀分布：如果 n 不是 2 的幂，(n-1) 的二进制低位会有 0，导致某些桶永远用不到，碰撞严重不均。
3. 扩容优化：扩容后只需判断新增的那一位，不需要重新 hash。
// 举例：n = 16 (2^4)，n-1 = 15 (0b1111)
// hash = 0x1234，hash & 15 = 0x1234 & 0b1111 = 4
// 等价于 0x1234 % 16 = 4
// 如果 n = 10（不是 2 的幂），n-1 = 9 (0b1001)
// 二进制第 1、3 位永远是 0，导致 index 只能是 0,1,8,9
// 中间 2~7 的桶永远用不到！
负载因子为什么是 0.75？
| 负载因子 | 空间利用率 | 查询效率 | 适用场景 |
|---|
| 0.5 | 低（一半空着） | 高（碰撞少） | 内存充足、追求极致性能 |
| 0.75 | 适中 | 适中 | 通用场景（默认） |
| 1.0 | 高（装满才扩） | 低（碰撞多） | 内存紧张、可接受低性能 |
0.75 是根据泊松分布计算出的最优值：在 0.75 的负载因子下，桶中元素数量的分布最接近理想情况，链表长度 ≥ 8 的概率仅约千万分之六。
JDK 7 扩容死循环问题（经典面试题）
原因：JDK 7 扩容时使用头插法（新元素插在链表头部），多线程并发扩容时可能形成环形链表，导致 get() 时 CPU 100%。
// JDK 7 transfer() 简化版 — 头插法
void transfer(Entry[] newTable) {
for (Entry<K,V> e : table) {
while (e != null) {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newTable.length);
e.next = newTable[i]; // 头插！新元素指向当前链表头
newTable[i] = e; // 新元素成为链表头
e = next;
}
}
}
// 多线程场景：
// 线程 A 执行到 e.next = newTable[i] 后挂起
// 线程 B 完成扩容，链表顺序反转
// 线程 A 恢复后继续执行，形成 A→B→A 的环形链表
JDK 8 的修复：改用尾插法（新元素插在链表尾部），扩容时保持原有顺序，不会形成环形链表。但 HashMap 仍然不是线程安全的，多线程 put 可能导致数据丢失。
HashMap 线程安全问题
| 问题 | JDK 7 | JDK 8 |
|---|
| 扩容死循环 | ✅ 存在（头插法） | ❌ 已修复（尾插法） |
| 数据丢失 | ✅ 存在 | ✅ 仍存在 |
| size 不准确 | ✅ 存在 | ✅ 仍存在 |
正确方案：多线程环境使用 ConcurrentHashMap 或 Collections.synchronizedMap()。
// 错误做法
Map<String, String> map = new HashMap<>();
// 多线程 put → 数据丢失、size 不准
// 正确做法 1：ConcurrentHashMap（推荐）
Map<String, String> map = new ConcurrentHashMap<>();
// 正确做法 2：同步包装
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());
自定义初始容量 — 避免扩容
如果预知要存 N 个元素，应设置 initialCapacity = N / 0.75 + 1，避免扩容带来的性能损耗。注意 HashMap 会自动调整为最近的 2 的幂。
// 预计存 100 个元素
// initialCapacity = 100 / 0.75 + 1 ≈ 134
// HashMap 自动调整为 256（最近的 2 的幂）
Map<String, Object> map = new HashMap<>(134);
// JDK 8 的 tableSizeFor 方法：找到 ≥ cap 的最小 2 的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 输入 134 → 输出 256
高级加分项：能说出扰动函数的设计意图、扩容时用 hash & oldCap 判断新位置、树化前先检查数组长度、JDK 7 头插法死循环的根因，说明你真正读过 HashMap 源码。
实战场景
场景一：用 HashMap 做简单缓存
public class SimpleCache<K, V> {
private final Map<K, V> cache = new HashMap<>();
public V get(K key, Function<K, V> loader) {
return cache.computeIfAbsent(key, loader);
}
public void invalidate(K key) {
cache.remove(key);
}
}
// 使用
SimpleCache<String, User> userCache = new SimpleCache<>();
User user = userCache.get("userId_123", id -> userDao.findById(id));
场景二：用 HashMap 做分组统计
// 统计每个部门的员工数量
List<Employee> employees = employeeDao.findAll();
Map<String, Integer> deptCount = new HashMap<>();
for (Employee emp : employees) {
deptCount.merge(emp.getDepartment(), 1, Integer::sum);
}
// 结果：{"技术部": 25, "产品部": 8, "市场部": 12}
常见坑
| 坑 | 原因 | 解决方案 |
|---|
| 自定义对象作 key 时 get 返回 null | 没重写 hashCode() 和 equals() | 必须同时重写两个方法 |
| 多线程 put 导致数据丢失 | HashMap 非线程安全 | 改用 ConcurrentHashMap |
| 频繁扩容导致性能下降 | 没预估容量 | 构造时指定 initialCapacity |
| key 可变导致"丢失"元素 | key 被修改后 hashCode 变了 | 使用不可变对象作 key |
// 坑：可变对象作 key
class BadKey {
int id;
String name;
// 重写了 hashCode 和 equals，但字段可变
}
Map<BadKey, String> map = new HashMap<>();
BadKey key = new BadKey(1, "test");
map.put(key, "value");
key.id = 2; // 修改了 key！
map.get(key); // 可能返回 null，因为 hashCode 变了
面试模拟
Q：HashMap 的底层数据结构是什么？
A：JDK 8 采用数组 + 链表 + 红黑树。数组是主干，每个位置叫桶；hash 冲突时用链表解决（拉链法）；当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树，查询从 O(n) 优化到 O(log n)。
Q：HashMap 的 put 过程是怎样的？
A：① 计算 hash（hashCode 高 16 位异或低 16 位）；② (n-1) & hash 定位桶下标；③ 桶为空直接插入；④ 桶有值则判断是链表还是红黑树，遍历比较 key（先比 hash，再比 == 或 equals）；⑤ key 相同覆盖，不同追加；⑥ 检查是否需要扩容。
Q：为什么容量是 2 的幂？负载因子为什么是 0.75？
A：2 的幂是为了用位运算 (n-1) & hash 代替取模，更快且分布均匀。0.75 是泊松分布下的最优值，平衡了空间利用率和查询效率。
Q：JDK 7 的 HashMap 有什么致命问题？
A：多线程扩容时头插法可能导致环形链表，get() 时 CPU 100%。JDK 8 改用尾插法修复了环形链表，但数据丢失问题仍存在，多线程仍需用 ConcurrentHashMap。
Q：为什么链表长度到 8 才转红黑树？
A：根据泊松分布，在负载因子 0.75 下，链表长度达到 8 的概率仅约 0.00000006（千万分之六）。如果真达到了，说明 hashCode() 设计有问题或遭遇了 hash 碰撞攻击，此时转为红黑树是合理的防御措施。同时数组长度必须 ≥ 64，否则优先扩容。