Java集合框架深度解析：HashMap
·
Java集合框架深度解析：HashMap
一、核心定义与定位
HashMap 是 Java 集合框架中基于「哈希表」实现的 Map 接口实现类，核心用于存储键值对（Key-Value），支持以平均 O (1) 时间复杂度完成增、删、查操作，是日常开发中最常用的非线程安全键值对容器。
记忆口诀：哈希表核心，O (1) 效率，键值对存储，非线程安全。
HashMap与ArrayList / LinkedList比较：
比 ArrayList / LinkedList 难一档，因为：
- 数组 + 链表 + 红黑树 三种结构随时切换
- 哈希冲突、负载因子、位运算、树化阈值、退化阈值……一堆魔法数字
- resize 时既要重新散列又要拆分链表/树，并发场景还会把节点链成环（JDK7 经典死链）
- JDK8 引入红黑树后代码量直接翻倍，split、untreeify、treeify 全是细节
但抓住一条主线就不乱了：
HashMap = 桶数组 + 哈希码 → 桶下标 → 链表/红黑树 → 扩容再散列，
所有复杂度都藏在“怎么快速定位桶”和“桶里元素太多怎么办”这两件事上。
二、底层数据结构
1. 核心结构：数组 + 链表 + 红黑树
Java 8以后，HashMap 的底层结构是「数组（桶）」为基础，「链表」解决哈希冲突，「红黑树」优化极端冲突场景的组合结构，JDK8 对该结构做了核心优化：
| 结构组件 | 作用说明 | 核心特性 |
|---|---|---|
| 数组（Node [] table） | 又称「桶（Bucket）」，是核心存储载体，每个桶对应一个数组下标 | 随机访问效率 O (1)，下标由 Key 的哈希值计算得出 |
| 链表（Node 节点） | 解决「哈希冲突」（多个 Key 映射到同一下标），JDK8 为双向链表 | 插入 / 删除 O (1)（尾插法），查询 O (n)，长度≥8 时触发转红黑树 |
| 红黑树（TreeNode） | 优化链表过长导致的查询低效问题 | 查询 O (logn)，节点数≤6 时转回链表，避免红黑树维护成本过高 |
核心节点类
// HashMap 基础链表节点（JDK8）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 节点哈希值（Key经扰动后的最终hash）
final K key; // 键（不可修改，保证哈希稳定性）
V value; // 值（可修改）
Node<K,V> next; // 下一个节点（双向链表还会有prev，此处简化）
// 构造方法：初始化节点核心属性
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// 重写equals：保证键值对的相等判断（Key+Value都相等才是同一个Entry）
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// Key和Value都相等，才判定为相等的Entry
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
// 红黑树节点（简化版，仅保留核心属性）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点（红黑树核心属性）
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 前驱节点（双向链表）
boolean red; // 红黑树颜色标记（红/黑）
TreeNode(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
核心字段
//核心字段(需背会)
Node<K,V>[] table; // 桶数组，长度永远是 2 的幂
int threshold; // 扩容阈值 = capacity * loadFactor
final float loadFactor; // 默认 0.75
static final int TREEIFY_THRESHOLD = 8; // 链表→树
static final int UNTREEIFY_THRESHOLD = 6; // 树→链表
static final int MIN_TREEIFY_CAPACITY = 64; // 树化前最低容量
2. 结构演进（JDK7 vs JDK8）
| 对比维度 | JDK7 | JDK8 | 优化目的 |
|---|---|---|---|
| 基础结构 | 数组 + 单向链表 | 数组 + 双向链表 + 红黑树 | 优化极端冲突场景的查询性能 |
| 链表插入方式 | 头插法 | 尾插法 | 解决扩容时链表成环问题 |
| 扩容后节点定位 | 重新计算哈希值 | 仅判断 hash 的某一位 | 提升扩容效率 |
| 空值处理 | 支持 null Key/Value | 支持 null Key/Value | 保持兼容性 |
记忆：JDK8 改头插为尾插，加红黑树，扩容更智能，解决成环和性能问题。
3. 初始容量的合理设置
现有未提 “自定义初始容量” 的坑点：
-
若已知 HashMap 要存储
N个元素，推荐初始容量设置为(N / 0.75) + 1（避免扩容）； -
注意：HashMap 会将自定义初始容量向上取整为最近的 2 的幂（如设置 10 → 实际 16），底层通过
tableSizeFor()方法实现// 核心逻辑：将传入容量转为≥它的最小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; }
容量必须为 2 的幂的原因
- 效率优化：
(n-1) & hash等价于hash % n，位运算效率远高于取模； - 扩容优化：JDK8 扩容时，节点下标仅需判断 hash 的某一位，无需重新计算哈希值；
- 哈希均匀：2 的幂次的容量，(n-1) 的二进制全为 1，能最大化利用 hash 的所有位，减少冲突。
记忆：容量 2 的幂，下标计算快，扩容更智能，哈希更均匀。
三、哈希计算与下标定位
1. 哈希值计算（扰动函数）
HashMap 对 Key 的 hashCode() 做「扰动处理」，核心目的是让 hashCode 的高位也参与下标计算，减少哈希冲突（尤其是数组容量较小时，高位无法通过取模参与计算）。
核心源码
/**
* 计算Key的最终哈希值（扰动函数）
* @param key 要计算的键
* @return 扰动后的哈希值
*/
static final int hash(Object key) {
int h;
// 1. key为null时，hash固定为0（HashMap支持null Key的核心逻辑）
// 2. 非null时：先获取hashCode，再将高16位与低16位异或（扰动）
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h >>> 16 是无符号右移 16 位，把 32 位整数 h 整体向右平移 16 格，左边空出来的位一律补 0（不分正负）。
直观效果：
- 原来高 16 位被搬到“低 16 位”的位置
- 原来低 16 位被直接扔掉
- 高位永远补 0，所以结果永远是非负数
h = 1111 1111 0000 0000 1111 0000 1111 0000
h >>> 16
= 0000 0000 0000 0000 1111 1111 0000 0000
↑ 高位补 0 ↑ 原高 16 位现变成低 16 位
在 HashMap 里就是为了把高位的混乱特征“折”到低位，再跟原低位异或，减少哈希冲突。
扰动函数的作用解析
假设 Key 的 hashCode 是 0x0000FFFF（低 16 位全 1，高 16 位全 0）：
- 未扰动：高 16 位无意义，下标计算仅用低 16 位，冲突概率高；
- 扰动后：
h ^ (h >>> 16) = 0x0000FFFF ^ 0x00000000 = 0x0000FFFF（示例），让高 16 位的特征融入最终 hash 值。
记忆：扰动 = 高 16 位 ^ 低 16 位，让高位也 “干活”，减少冲突。
哈希扰动函数的演进（JDK7 vs JDK8）
// JDK7 扰动函数（4次位运算+5次异或，扰动更“激进”）
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// JDK8 扰动函数（仅1次异或，简化但足够）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
优化原因：JDK8 减少扰动次数，兼顾性能与冲突率 —— 高 16 位异或低 16 位，既让高位参与计算，又避免过度运算。
2. 数组下标计算
通过位运算替代取模，提升效率（仅当数组容量为 2 的幂时等价）：
/**
* 计算Key在数组中的下标
* @param hash 扰动后的哈希值
* @param capacity 数组容量（2的幂）
* @return 数组下标
*/
private static int getIndex(int hash, int capacity) {
// (capacity - 1) & hash 等价于 hash % capacity，但位运算效率更高
// 前提：capacity 必须是 2 的幂（如16、32、64）
return (capacity - 1) & hash;
}
代码验证
public class HashMapHashDemo {
public static void main(String[] args) {
String key = "Java";
// 1. 获取原始hashCode
int hashCode = key.hashCode();
System.out.println("原始hashCode：" + hashCode); // 示例：2301506
// 2. 执行扰动函数
int hash = hashCode ^ (hashCode >>> 16);
System.out.println("扰动后的hash：" + hash); // 示例：2301507
// 3. 计算下标（容量16）
int capacity = 16;
int index = (capacity - 1) & hash;
System.out.println("数组下标：" + index); // 示例：3
}
}
3. null Key 的特殊处理
现有内容提到支持 null Key/Value，但未细化底层逻辑：
- null Key 的 hash 值固定为 0，因此永远落在桶数组下标 0 的位置；
- 查找 null Key 时，无需计算哈希，直接遍历下标 0 的桶即可，是 HashMap 对 null 的专属优化；
- 注意：
ConcurrentHashMap不支持 null Key/Value，这是与 HashMap 的关键区别之一。
4. 补充：>>>和>>符号的作用
>>>是 Java 的无符号右移运算符（unsigned right shift）。
功能：
“把整数的二进制位整体向右移动指定位数，左边空出来的位一律补 0（不管原来正负）。”
>>是 java的带符号右移运算符（signed right shift）。
功能：
把整数的二进制位整体向右移动指定格数，左边空出来的位用“原来的符号位”补齐（正数补 0，负数补 1）。
结果保持原符号（正数仍 ≥ 0，负数仍 < 0）。
对比记忆：
| 运算符 | 名称 | 左侧补位规则 | 结果正负 |
|---|---|---|---|
>> |
带符号右移 | 原符号位（0 或 1） | 保持原符号 |
>>> |
无符号右移 | 永远补 0 | 永远得 非负数 |
示例（8 位演示）：
原始 : 1111 0001 (-15 的补码)
-15 >> 2 : 1111 1100 带符号右移→仍是负数
-15 >>> 2 : 0011 1100 无符号右移→正数 60
在 HashMap 里：
h >>> 16
就是把 32 位哈希值的高 16 位“搬”到低 16 位，同时保证结果为正，再与原低 16 位异或，用来打散低位分布。
记忆口诀：>> 带符号，移后符号不变；>>> 无符号，移后永远非负。
四、扩容（Rehash）机制
1. 扩容触发条件
当 HashMap 满足以下任一条件时，触发扩容：
- 元素总数（size）≥ 数组容量（capacity）× 负载因子（loadFactor）；
- 链表转红黑树时，数组容量 < 64（优先扩容而非转树）。
默认参数：
- 初始容量：16（2^4）；
- 负载因子：0.75；
- 初始阈值：16 × 0.75 = 12（触发扩容的临界值）。
2. 扩容核心逻辑
/**
* 简化版扩容逻辑（保留核心步骤+详细注释）
*/
final Node<K,V>[] resize() {
// 1. 保存原数组和原容量/阈值
Node<K,V>[] oldTab = table; // 原数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原容量
int oldThr = threshold; // 原阈值
int newCap, newThr = 0;
// 2. 计算新容量和新阈值
if (oldCap > 0) {
// 2.1 原容量超过最大值（2^30），不再扩容，阈值设为int最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2.2 容量翻倍（左移1位 = ×2），阈值也翻倍（原容量≥16时）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
newThr = oldThr << 1;
}
}
// 2.3 首次初始化（new HashMap(int initialCapacity) 场景）
else if (oldThr > 0) {
newCap = oldThr;
}
// 2.4 无参构造首次初始化（默认容量16，阈值12）
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 3. 兜底计算新阈值（如自定义容量时）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE;
}
threshold = newThr; // 更新全局阈值
// 4. 创建新数组（容量翻倍）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 5. 迁移原数组节点到新数组（JDK8核心优化）
if (oldTab != null) {
// 遍历原数组的每个桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e = oldTab[j]; // 当前桶的头节点
if (e != null) {
oldTab[j] = null; // 释放原数组引用（GC）
// 5.1 桶中只有单个节点：直接计算新下标放入
if (e.next == null) {
newTab[e.hash & (newCap - 1)] = e;
}
// 5.2 红黑树节点：拆分红黑树（简化）
else if (e instanceof TreeNode) {
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}
// 5.3 链表节点：JDK8优化核心（无需重新计算hash）
else {
Node<K,V> loHead = null, loTail = null; // 留在原下标
Node<K,V> hiHead = null, hiTail = null; // 移到 原下标+oldCap
do {
Node<K,V> next = e.next;
// 判断hash的oldCap位：0→留原下标，1→移新下标
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
3. 负载因子 0.75 的设计原因
负载因子是「时间效率」与「空间效率」的最优平衡：
负载因子 = 0.75 不是算出来的，是**“测” + “估”** 后留下的经验折中值，官方源码注释只给了一句话解释：
“As a general rule, the default load factor (.75) offers a good trade-off between time and space costs.”
把它拆开就是三条量化依据 + 一条工程兜底：
-
冲突概率 vs 空间浪费的实测曲线
哈希表的期望冲突次数服从泊松分布：
λ = 0.5 时，桶里出现 ≥8 个节点的概率已经 <10⁻⁶；
当负载因子 α 从 0.6 升到 0.9 时，平均查找长度（ASL）近似 1/(1-α) 增长：-
α=0.6 → ASL≈2.5
-
α=0.75 → ASL≈4
-
α=0.9 → ASL≈10
0.75 正好处于“ASL 还能接受”与“数组不至于太稀疏”的拐点。
-
-
扩容代价的摊销
0.75 意味着每插入 3 个元素平均才触发一次 2× 扩容，rehash 的 CPU 开销与多占 25 % 内存之间取得平衡；再高一点，节省的内存远抵不过频繁扩容的拷贝成本。 -
与“树化阈值 8”配套
当 α=0.75 时，泊松分布给出：
P(桶长度≥8) ≈ 0.0000001，几乎不可能因自然冲突就出现超长链表；
一旦真出现 ≥8 的桶，大概率是哈希攻击或极劣质 key，此时转成红黑树把查找复杂度从 O(n) 降到 O(log n) 才划算。
换句话说，0.75 让‘树化’成为真正的异常分支，而不是日常路径。 -
工程兜底 —— 经验值好记
3/4 是简单分数，0.75 = 3/4 便于口算与文档描述；同时与 0.5、0.9 拉开明显间隔，减少误调。
一句话总结
0.75 是实测后给出的时间-空间-冲突概率-树化概率四重折中点：
再小 → 浪费数组；再大 → 冲突暴涨、扩容频繁；
它和“链表长度≥8 才树化”一起，把正常场景与攻击/劣质哈希清晰分开。
五、核心方法解析（核心逻辑 + 简化源码）
1. put (K key, V value)：添加 / 修改元素
核心流程（图解）
简化源码
/**
* 添加/修改键值对
* @param key 键
* @param value 值
* @return 旧值（无则返回null）
*/
public V put(K key, V value) {
// 调用核心方法，hash参数为扰动后的hash值
return putVal(hash(key), key, value, false, true);
}
/**
* put的核心实现
* @param hash Key的最终hash值
* @param key 键
* @param value 值
* @param onlyIfAbsent 仅当Key不存在时才插入（false=覆盖已有值）
* @param evict 用于LinkedHashMap的回调标记
* @return 旧值（无则返回null）
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 数组未初始化 → 执行扩容（首次put时）
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
// 2. 计算下标，桶为空 → 直接创建节点放入
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
Node<K,V> e; K k;
// 3. 桶首节点匹配（hash相等且Key相等）→ 记录节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
}
// 4. 首节点是红黑树 → 树中插入/替换
else if (p instanceof TreeNode) {
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}
// 5. 首节点是链表 → 遍历链表
else {
// binCount：记录链表长度（用于判断是否转红黑树）
for (int binCount = 0; ; ++binCount) {
// 5.1 遍历到链表尾部 → 尾插法插入新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度≥8 → 触发转红黑树（还会检查数组容量≥64）
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
break;
}
// 5.2 找到匹配节点 → 跳出循环
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e; // 移动到下一个节点
}
}
// 6. 节点已存在 → 替换Value
if (e != null) {
V oldValue = e.value;
// onlyIfAbsent=false 或旧值为null → 覆盖
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e); // LinkedHashMap回调（此处无实际逻辑）
return oldValue; // 返回旧值
}
}
// 7. 结构修改次数+1（用于Fail-Fast检测）
++modCount;
// 8. 元素总数+1，超过阈值 → 扩容
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict); // LinkedHashMap回调
return null; // 无旧值返回null
}
2. get (Object key)：获取元素
核心流程
- 计算 Key 的 hash 值；
- 定位数组下标，桶为空则返回 null；
- 桶首节点匹配则返回 Value；
- 首节点是红黑树则树中查找，是链表则遍历查找；
- 未找到则返回 null。
简化源码
/**
* 根据Key获取Value
* @param key 键
* @return Value（无则返回null）
*/
public V get(Object key) {
Node<K,V> e;
// 计算hash → 调用核心方法 → 无节点返回null，有则返回Value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* get的核心实现
* @param hash Key的最终hash值
* @param key 键
* @return 匹配的节点（无则返回null）
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 数组非空 + 桶非空 → 继续查找
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 2. 首节点匹配 → 直接返回
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
return first;
}
// 3. 遍历后续节点
if ((e = first.next) != null) {
// 3.1 红黑树 → 树中查找
if (first instanceof TreeNode) {
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
}
// 3.2 链表 → 遍历匹配
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
return e;
}
} while ((e = e.next) != null);
}
}
// 4. 未找到匹配节点 → 返回null
return null;
}
3. 常用方法速查
| 方法名 | 核心功能 | 时间复杂度 | 注意事项 |
|---|---|---|---|
size() |
获取元素总数 | O(1) | 直接返回 size 变量 |
isEmpty() |
判断是否为空 | O(1) | 等价于 size () == 0 |
containsKey(Object) |
判断是否包含指定 Key | O(1) | 基于哈希查找，效率高 |
containsValue(Object) |
判断是否包含指定 Value | O(n) | 需遍历所有元素，效率低 |
remove(Object) |
删除指定 Key 的元素 | O(1) | 找到节点后直接移除，链表 / 红黑树分别处理 |
clear() |
清空所有元素 | O(n) | 遍历所有桶，置 null 并重置 size/modCount |
keySet() |
获取所有 Key 的集合（视图） | O(1) | 视图与原 Map 关联，修改会同步 |
values() |
获取所有 Value 的集合（视图） | O(1) | 同上 |
entrySet() |
获取所有键值对的集合（视图） | O(1) | 遍历 HashMap 的最优方式（减少哈希计算） |
简单演示
import java.util.*;
public class Main {
public static void main(String[] args) {
// 1. 初始化一个 HashMap
HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
//1. size()
System.out.println("size() = " + map.size()); // 3
//2. isEmpty()
System.out.println("isEmpty() = " + map.isEmpty()); // false
//3. containsKey()
System.out.println("containsKey(\"B\") = " + map.containsKey("B")); // true
//4. containsValue()
System.out.println("containsValue(3) = " + map.containsValue(3)); // true
//5. remove()
Integer removed = map.remove("B");
System.out.println("remove(\"B\") 返回值 = " + removed); // 2
System.out.println("删除后 map = " + map); // {A=1, C=3}
//6. clear()
map.clear();
System.out.println("clear() 后 isEmpty = " + map.isEmpty()); // true
// 重新填点数据，方便演示三种视图
map.put("K1", 10);
map.put("K2", 20);
//7. keySet()
Set<String> keys = map.keySet();
System.out.println("keySet() = " + keys); // [K1, K2]
// 8. values()
Collection<Integer> values = map.values();
System.out.println("values() = " + values); // [10, 20]
//9. entrySet()
Set<Map.Entry<String, Integer>> entries = map.entrySet();
System.out.println("entrySet() 遍历：");
for (Map.Entry<String, Integer> e : entries) {
System.out.printf(" %s -> %s%n", e.getKey(), e.getValue());
}
/* -------------- 视图联动演示 -------------- */
System.out.println("修改原 map 后，视图自动同步：");
map.put("K3", 30);
System.out.println(" keySet 现在 = " + keys);
System.out.println(" values 现在 = " + values);
System.out.println(" entrySet 现在 = " + entries);
}
}
六、核心坑点与避坑指南
1. 线程不安全问题
问题表现
- JDK7：多线程扩容时，链表头插法导致链表成环，引发死循环；
- JDK8：多线程 put 可能覆盖数据，遍历可能丢失数据。
解决方案
// 方案1：ConcurrentHashMap（推荐，并发性能优）
Map<String, Integer> chm = new ConcurrentHashMap<>();
// 方案2：Collections.synchronizedMap（全局锁，性能差，适合低并发）
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// 方案3：手动加锁（灵活，适合自定义场景）
Lock lock = new ReentrantLock();
Map<String, Integer> map = new HashMap<>();
// 加锁put示例
lock.lock();
try {
map.put("key", 1);
} finally {
lock.unlock();
}
2. Key 需重写 hashCode/equals
问题根源
HashMap 判定 Key 相等的规则：hash相等 && equals为true，若未重写：
- 不同对象（如两个 new User (“张三”)）的 hashCode 不同，会被判定为不同 Key；
- 即使 hashCode 相同，equals 为 false，也会被判定为不同 Key。
正确示例
class User {
private String id;
private String name;
// 构造方法省略
// 重写equals：基于业务唯一标识（如id）判断相等
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return Objects.equals(id, user.id); // 仅id相等即判定为同一用户
}
// 重写hashCode：基于equals的字段计算
@Override
public int hashCode() {
return Objects.hash(id);
}
}
3. Fail-Fast 机制
之前在Java集合框架深入解析：ArrayList & LinkedList一文中有过详细解释Fail-Fast 机制。
触发条件
遍历 HashMap 时（如 foreach、迭代器），修改集合结构（put/remove），会抛出 ConcurrentModificationException（通过 modCount 检测）。
安全遍历方式
// 方式1：迭代器的remove方法（推荐）
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, Integer> entry = it.next();
if ("test".equals(entry.getKey())) {
it.remove(); // 安全，会同步更新modCount
}
}
// 方式2：遍历前拷贝集合（适合小数据量）
for (String key : new ArrayList<>(map.keySet())) {
if ("test".equals(key)) {
map.remove(key);
}
}
// 方式3：使用ConcurrentHashMap（无Fail-Fast）
Map<String, Integer> chm = new ConcurrentHashMap<>();
chm.put("test", 1);
for (String key : chm.keySet()) {
chm.remove(key); // 不会抛异常
}
4. 性能调优建议
结合实际开发的调优方向：
- 低内存 + 高并发：减小负载因子（如 0.6），降低冲突概率，代价是更频繁扩容；
- 高内存 + 低并发：增大负载因子（如 0.85），减少数组占用空间，代价是冲突略增；
- 避免使用「哈希值分布差」的 Key（如连续整数），可自定义哈希函数优化分布；
- 大批量插入前先
initialCapacity初始化，避免多次扩容。
七、关联
1. HashMap 与 ConcurrentHashMap 的关联
一句话区分：
HashMap = 单机快车，线程不安全；
ConcurrentHashMap = 高并发专车，读无锁、写桶锁，安全且快。
| 维度 | HashMap | ConcurrentHashMap |
|---|---|---|
| 线程安全 | ❌ 完全不行 | ✅ 高并发设计 |
| 读写锁 | 无锁，也不保证可见性 | 读全程无锁，写只锁单个桶 |
| Null 支持 | key/value 都可 null | key/value 都不能 null（防歧义） |
| 结构 | 数组+链表+红黑树 | 同左，但节点全 volatile，迁移用 ForwardingNode |
| 扩容 | 单线程内部完成 | 多线程协同 transfer，CPU 越多越快 |
| 计数 | 普通 int size() | 分段 LongAdder，size() 无锁也精确 |
| 迭代器 | fail-fast，并发修改抛异常 | fail-safe，遍历快照，允许并发更新 |
| 典型用途 | 普通业务缓存 | 全局缓存、并发计算、高吞吐计数器 |
记忆口诀：
普通地图用 HashMap，并发战场换 ConcurrentHashMap。
2. HashMap 与 LinkedHashMap 的关联
补充 LinkedHashMap 基于 HashMap 的扩展逻辑：
-
LinkedHashMap 继承 HashMap，重写
newNode()方法，在节点中增加「前驱 / 后继」指针，维护插入 / 访问顺序； -
可通过
LinkedHashMap实现 “LRU 缓存”（覆写removeEldestEntry()）：// 简单LRU缓存：容量超过5时，移除最久未访问的元素 Map<String, Integer> lruMap = new LinkedHashMap<String, Integer>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) { return size() > 5; } };
八、面试高频考点总结
1. 底层原理核心考点
-
问题一：HashMap JDK7 和 JDK8 的核心区别？
答：
① 结构：JDK7 数组 + 单向链表，JDK8 数组 + 双向链表 + 红黑树；
② 插入：JDK7 头插法（成环风险），JDK8 尾插法；
③ 扩容：JDK8 节点定位更高效；
④ 性能：JDK8 极端冲突场景更优。
-
问题二：红黑树转换条件为什么是链表长度≥8 且数组容量≥64？
答：
① 长度≥8：泊松分布下，链表长度超过 8 的概率极低，避免过度优化；
② 容量≥64：数组容量小时，优先扩容减少冲突，而非转树（红黑树维护成本高）。
-
问题三：负载因子为什么是 0.75？
答：时间与空间的最优平衡，基于泊松分布，该值下哈希冲突概率最低。（见 四.3）
2. 实战避坑核心考点
-
问题一：HashMap 为什么线程不安全？
答：
① JDK7 扩容头插法导致链表成环；
② JDK8 多线程 put 可能覆盖数据；
③ 无同步机制，modCount 非原子更新。
-
问题二：Key 为什么要重写 hashCode/equals？
答：保证 Key 的相等判断与哈希计算一致，避免 “存得进，找不出” 的问题。
-
问题三：如何解决 HashMap 的 Fail-Fast 问题？
答：
① 使用迭代器的 remove 方法；
② 遍历前拷贝集合；
③ 使用 ConcurrentHashMap。
3. 终极记忆口诀
HashMap 三大核心：
- 哈希计算（扰动 + 位运算，少冲突）；
- 扩容机制（翻倍 + 智能定位，平衡时空）；
- 结构优化（链表转红黑树，提性能）。
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
24
0- 0
已为社区贡献14条内容
所有评论(0)