HashMap、mutableMapOf 与 ConcurrentHashMap 完全指南
·
—— 从集合使用、线程安全到 Android Framework 实践
基于 Android 16（API Level 36）与 OpenJDK 17
难度：进阶
一、前言
在 Android 开发中，Map 几乎无处不在：
// 临时缓存
val cache = mutableMapOf<String, User>()
// 数据聚合
val userMap = HashMap<String, User>()
// 全局图片缓存
val imageCache = ConcurrentHashMap<String, Bitmap>()
很多开发者都知道：
-
HashMap 线程不安全
-
ConcurrentHashMap 线程安全
但真正深入思考过下面问题的人并不多：
-
Kotlin 的
mutableMapOf()底层到底是什么？ -
HashMap 为什么会线程不安全？具体在哪些操作上？
-
ConcurrentHashMap 为什么性能比
Hashtable高几十倍？ -
ConcurrentHashMap 的 CAS + synchronized 是如何协作的？
-
Android Framework 为什么大量使用 ArrayMap，而不是 HashMap？
-
Repository、ViewModel、全局缓存分别应该选择什么 Map？
本文将从 Android 16 源码 角度，彻底讲清这些问题。
二、Map 家族全景图
2.1 Java 集合体系
Map
│
┌────────────┼────────────┐
│ │ │
HashMap LinkedHashMap TreeMap
│ │ │
│ Hashtable ConcurrentHashMap
│
EnumMap
2.2 Kotlin 常见 API 的真实面目
| Kotlin API | 实际类型 | 是否线程安全 | 是否有序 |
|---|---|---|---|
mapOf() |
EmptyMap / SingletonMap |
✅（不可变） | 否 |
mutableMapOf() |
LinkedHashMap |
❌ | ✅（插入顺序） |
hashMapOf() |
HashMap |
❌ | ❌ |
linkedMapOf() |
LinkedHashMap |
❌ | ✅ |
sortedMapOf() |
TreeMap |
❌ | ✅（自然顺序） |
关键结论：Kotlin 没有提供新的线程安全 Map，只是对 Java 集合的语法糖封装。
三、mutableMapOf 本质揭秘
3.1 源码分析
// Kotlin 标准库源码 (kotlin.collections.MapsKt)
public fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()
因此：
val map = mutableMapOf<String, Int>()
// 完全等价于
val map = LinkedHashMap<String, Int>()
3.2 为什么要设计成 LinkedHashMap？
Google 和 JetBrains 的考虑：
-
可预测性：大多数开发者期望 Map 保持插入顺序
-
调试友好：打印日志时顺序固定
-
Android 兼容性：
LinkedHashMap在所有 API 级别都可用
3.3 实际验证
fun testMapOrder() {
val map = mutableMapOf<String, Int>()
map["B"] = 2
map["A"] = 1
map["C"] = 3
println(map.keys) // 输出: [B, A, C] (保持插入顺序)
val hashMap = hashMapOf<String, Int>()
hashMap["B"] = 2
hashMap["A"] = 1
hashMap["C"] = 3
println(hashMap.keys) // 输出: [A, B, C] 或 [C, A, B] (无序)
}
四、HashMap 底层结构深度解析
4.1 核心数据结构（JDK 8+）
// Android 16 / OpenJDK 17 源码
public class HashMap<K,V> {
// 哈希桶数组（延迟初始化）
transient Node<K,V>[] table;
// 链表节点
static class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// 红黑树节点（当链表长度 > 8 时转换）
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;
}
// 关键常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
}
4.2 结构图示
HashMap 结构图
┌─────────────────────────────────────────────┐
│ table[] │
├─────┬─────┬─────┬─────┬─────┬─────┬─────┬───┤
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │...│
└──┬──┴──┬──┴──┬──┴─────┴─────┴──┬──┴──┬──┴───┘
│ │ │ │ │
▼ ▼ ▼ ▼ ▼
null Node Node TreeNode null
│ │ ↙ ↘
▼ ▼ 左 右
Node Node 子 子
│ 树 树
▼
Node (链表过长会树化)
4.3 为什么树化阈值是 8？（面试高频）
源码注释中有一段泊松分布的计算：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
解读：
-
在
loadFactor = 0.75的默认情况下，桶内节点长度达到 8 的概率仅为 0.000006% -
一旦达到这个阈值，说明哈希冲突已经极其严重
-
此时将链表转为红黑树，查询复杂度从 **O(n) → O(log n)**，收益远大于维护成本
五、HashMap 为什么线程不安全？（深度分析）
5.1 数据覆盖问题
// HashMap.putVal() 简化版
final V putVal(int hash, K key, V value, ...) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
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 {
// 处理冲突...
}
}
并发场景：
-
线程 A 和线程 B 同时执行到
if (p == null) -
都发现桶为空
-
线程 A 创建 Node 并赋值
tab[i] = nodeA -
线程 B 创建 Node 并赋值
tab[i] = nodeB -
线程 B 覆盖了线程 A 的数据
5.2 可见性问题
// 非 volatile 修饰的 Node 数组
transient Node<K,V>[] table; // 没有 volatile！
-
线程 A 修改后，修改可能停留在 CPU L1/L2 缓存
-
线程 B 读取时，可能读到旧值（null 或过期数据）
-
无法建立 happens-before 关系
5.3 扩容时的死循环（JDK 7 历史问题）
JDK 7 使用头插法：
旧链表: 1 → 2 → 3
扩容后: 3 → 2 → 1 (头插法导致反转)
多线程并发扩容时可能形成环形链表，导致 get() 死循环。
JDK 8 已修复（改用尾插法 + 高低位拆分），但 HashMap 仍然不是线程安全的。
六、ConcurrentHashMap 的设计思想
6.1 演进历史
| 版本 | 并发机制 | 锁粒度 | 性能 |
|---|---|---|---|
| JDK 1.7 | Segment 分段锁（继承 ReentrantLock） | 每个 Segment 锁一个 Hash 桶组 | 较好 |
| JDK 1.8+ | CAS + synchronized + volatile | 每个 Hash 桶单独锁 | 极高 |
6.2 核心设计原则
┌─────────────────────────────────────┐
│ 读操作：完全无锁 │
│ (volatile 保证可见性，无需加锁) │
├─────────────────────────────────────┤
│ 写操作：细粒度锁 │
│ (只锁当前操作的 Hash 桶的头节点) │
├─────────────────────────────────────┤
│ 扩容操作：多线程协作 │
│ (每个线程负责一部分桶，加速扩容) │
└─────────────────────────────────────┘
七、ConcurrentHashMap 源码深度解析
7.1 核心成员变量
public class ConcurrentHashMap<K,V> {
// 哈希桶数组（volatile 保证可见性）
transient volatile Node<K,V>[] table;
// 扩容时的临时数组
private transient volatile Node<K,V>[] nextTable;
// 控制标识符（灵魂字段）
private transient volatile int sizeCtl;
// 基础计数器（CAS 更新）
private transient volatile long baseCount;
// 计数器数组（高并发时使用）
private transient volatile CounterCell[] counterCells;
}
7.2 Node 节点设计
static class Node<K,V> {
final int hash;
final K key;
volatile V val; // volatile 保证值可见
volatile Node<K,V> next; // volatile 保证链表可见
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
}
7.3 put() 完整流程
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) { // 自旋，直到成功
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // ① 初始化（CAS 保证单次初始化）
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// ② 桶为空：CAS 尝试插入
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
}
else if ((fh = f.hash) == MOVED) // ③ 正在扩容
tab = helpTransfer(tab, f); // 帮助扩容（多线程协作）
else {
// ④ 桶非空：synchronized 锁住头节点
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) { // 双重检查
if (fh >= 0) {
// 链表插入（尾插法）
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash && ((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
} else if (f instanceof TreeBin) {
// 红黑树插入
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i); // 检查是否需要树化
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); // ⑤ 更新 size，检查扩容
return null;
}
7.4 put() 流程图
┌──────────────────┐
│ 计算 hash 值 │
└────────┬─────────┘
▼
┌──────────────────┐
│ table == null? │──Yes──▶ initTable()
└────────┬─────────┘ (CAS 保证单次初始化)
│No
▼
┌──────────────────┐
│ 桶为空？ │
└────────┬─────────┘
│Yes No
▼ │
┌──────────────────┐ │
│ CAS 插入新节点 │ │
└────────┬─────────┘ │
│成功 ▼
│ ┌──────────────────────┐
│ │ f.hash == MOVED? │──Yes──▶ helpTransfer()
│ └──────────┬───────────┘ (多线程协助扩容)
│ │No
│ ▼
│ ┌──────────────────────┐
│ │ synchronized(f) │
│ │ 锁住头节点 │
│ └──────────┬───────────┘
│ ▼
│ ┌──────────────────────┐
│ │ 链表插入 或 红黑树插入 │
│ └──────────┬───────────┘
│ ▼
│ ┌──────────────────────┐
│ │ binCount >= 8? │──Yes──▶ treeifyBin()
│ └──────────┬───────────┘
│ │No
│ ▼
│ ┌──────────────────────┐
│ │ addCount() 更新 size │
│ └──────────────────────┘
│
▼
[完成]
八、sizeCtl：ConcurrentHashMap 的灵魂
8.1 sizeCtl 的作用
private transient volatile int sizeCtl;
这是一个多状态复用的控制字段，通过不同的值表示不同状态：
| sizeCtl 值 | 含义 |
|---|---|
| 0 | 数组未初始化，使用默认容量 16 |
| >0 | 初始化完成，表示扩容阈值（capacity * 0.75） |
| -1 | 正在初始化（table 正在创建） |
| <0 且 ≠ -1 | 正在扩容（高 16 位：扩容标识戳，低 16 位：参与扩容线程数+1） |
8.2 源码验证
// 初始化时的 CAS 逻辑
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // 其他线程正在初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// CAS 设置为 -1，标记初始化中
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2); // 0.75 * n
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
8.3 扩容时的 sizeCtl
// 扩容标识戳生成
int rs = resizeStamp(n); // 例如: 1000000000011011 (16位)
// 设置 sizeCtl = (rs << RESIZE_STAMP_SHIFT) + 2
// 低 16 位表示参与扩容的线程数
U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
九、ForwardingNode 与扩容机制
9.1 ForwardingNode 设计
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null); // hash = MOVED (-1)
this.nextTable = tab;
}
}
9.2 扩容时的查找流程
// get() 方法遇到 ForwardingNode
if ((fh = f.hash) == MOVED)
return (p = f.find(h, key)) != null ? p.val : null;
// ForwardingNode.find() 会去新表查找
Node<K,V> find(int h, Object k) {
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
// 在新表中查找...
}
}
9.3 扩容协作图
扩容前:
table[0] → NodeA → NodeB → NodeC
table[1] → NodeD
table[2] → null
...
扩容开始:
┌──────────────────────────────────────┐
│ 线程1: 负责 bucket 0-15 │
│ 线程2: 负责 bucket 16-31 │
│ 线程3: 负责 bucket 32-47 │
└──────────────────────────────────────┘
迁移 bucket 0 时:
table[0] → ForwardingNode → nextTable[0] → NodeA
[16] → NodeB
[32] → NodeC
其他线程访问 table[0]:
- get(): 发现 ForwardingNode，自动到新表查找
- put(): 发现 ForwardingNode，协助扩容
十、computeIfAbsent 为什么重要
10.1 错误写法（非原子）
// ❌ 错误：非原子操作
if (!map.containsKey(key)) {
val value = expensiveCreate(key) // 可能被多次调用
map[key] = value
}
问题：两个线程同时调用，会重复创建对象，后一个覆盖前一个。
10.2 正确写法
// ✅ 正确：原子操作
val value = map.computeIfAbsent(key) {
expensiveCreate(it) // 保证只执行一次
}
10.3 源码实现
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
// ...
synchronized (f) {
// 双重检查，确保只在不存在时创建
if (tabAt(tab, i) == f) {
// 查找链表/树，确认 key 不存在
// 调用 mappingFunction 创建
// 插入新节点
}
}
}
}
十一、Android Framework 中的 Map 选型
11.1 ArrayMap 源码分析
// frameworks/base/core/java/android/util/ArrayMap.java
public class ArrayMap<K, V> {
// 两个平行数组存储 key 和 value
int[] mHashes; // 哈希值数组
Object[] mArray; // Key-Value 交替存储
int mSize;
// 二分查找定位 key
int indexOf(Object key, int hash) {
// 使用二分查找在 mHashes 中查找
// 找到后对比 mArray 中的 key
}
}
为什么 Android 使用 ArrayMap？
| 对比项 | ArrayMap | HashMap |
|---|---|---|
| 内存占用 | 两个数组，无额外 Node 对象 | 每个 Node 约 32 字节额外开销 |
| 查找速度 | O(log n) 二分查找 | O(1) 哈希查找 |
| GC 压力 | 小（无大量小对象） | 大（频繁创建 Node） |
| 适用场景 | 小数据量（< 1000） | 大数据量 |
11.2 SparseArray 系列
// Android 特有：避免 int → Integer 装箱
SparseArray<String> map = new SparseArray<>();
map.put(1, "one");
map.put(2, "two");
// Long 版本
LongSparseArray<String> longMap = new LongSparseArray<>();
// 支持 key 和 value 均为 int
SparseIntArray intMap = new SparseIntArray();
Framework 中的典型使用：
// ActivityManagerService 中的进程管理
final SparseArray<ProcessRecord> mProcesses = new SparseArray<>();
// View 系统 ID 映射
private SparseArray<View> mChildren;
十二、Android 开发中的真实场景
12.1 ViewModel 中的缓存
class UserViewModel : ViewModel() {
// ✅ 主线程访问，使用 mutableMapOf
private val userCache = mutableMapOf<String, User>()
fun getUser(id: String): User? {
return userCache[id] // 主线程安全
}
}
12.2 Repository 中的缓存
class UserRepository(private val api: UserApi) {
// ⚠️ 多线程访问（IO 线程、协程）
private val cache = ConcurrentHashMap<String, User>()
suspend fun getUser(id: String): User {
return cache.getOrPut(id) {
api.fetchUser(id) // 网络请求
}
}
}
// Kotlin 扩展函数（非原子，注意使用）
fun <K, V> ConcurrentHashMap<K, V>.getOrPut(key: K, value: () -> V): V {
return this[key] ?: value().also { this[key] = it } // 非原子！
}
12.3 全局单例缓存
object ImageCache {
// ✅ 全局访问，必须线程安全
private val cache = ConcurrentHashMap<String, Bitmap>()
private val maxSize = 50
fun put(url: String, bitmap: Bitmap) {
if (cache.size >= maxSize) {
// 清理逻辑（需要额外同步）
val firstKey = cache.keys.firstOrNull()
firstKey?.let { cache.remove(it) }
}
cache[url] = bitmap
}
fun get(url: String): Bitmap? = cache[url]
fun clear() = cache.clear()
}
十三、真实线上案例
问题描述
某社交 App 的用户信息缓存偶现丢失，用户反馈"我的资料突然变成了别人的"。
问题代码
object UserCache {
// ❌ 错误：使用 mutableMapOf
val cache = mutableMapOf<String, User>()
}
// 多个协程同时写入
class UserManager {
suspend fun updateUser(user: User) {
withContext(Dispatchers.IO) {
UserCache.cache[user.id] = user // 多线程并发写！
}
}
}
问题分析
-
mutableMapOf()实际是LinkedHashMap -
LinkedHashMap非线程安全 -
多协程在
Dispatchers.IO上并发执行put() -
发生数据覆盖，导致缓存错乱
解决方案
object UserCache {
// ✅ 修改为 ConcurrentHashMap
val cache = ConcurrentHashMap<String, User>()
}
十四、高频面试题汇总
Q1: HashMap 为什么线程不安全？（3个点）
-
数据覆盖：多线程同时
put到空桶，后覆盖前 -
可见性问题：数组非
volatile，线程间修改不可见 -
扩容问题（JDK 7）：头插法导致环形链表，CPU 100%
Q2: 为什么树化阈值是 8？
泊松分布计算：在 loadFactor=0.75 下，链表长度达到 8 的概率仅为 **0.000006%**，此时哈希冲突严重，树化收益大于维护成本。
Q3: ConcurrentHashMap 为什么不允许 null？
避免二义性：
-
map.get(key)返回null可能是 key 不存在，也可能是 value 为null -
并发环境下，
containsKey的结果可能在瞬间过期，无法准确判断
Q4: sizeCtl 有什么作用？
一个字段控制三种状态：
-
0：未初始化
-
-1：初始化中
-
>0：扩容阈值
-
<0（且 ≠ -1）：正在扩容（高 16 位：标识戳，低 16 位：参与线程数+1）
Q5: ForwardingNode 有什么作用？
-
扩容期间，替换已迁移的旧桶
-
标记
hash = MOVED (-1) -
get()遇到它时会去新表查找 -
put()遇到它时会协助扩容
Q6: computeIfAbsent 为什么线程安全？
因为它在 synchronized 块内完成了：
-
双重检查 key 是否存在
-
创建新值
-
插入 Map
整个过程 原子执行。
Q7: Android 为什么提供 ArrayMap？
-
内存效率：无需创建 Node 对象，减少 GC 压力
-
移动端特性：大多数场景数据量小（< 1000），二分查找足够快
-
避免装箱：配合
SparseArray可避免 int→Integer 转换
十五、总结与选型建议
最终选型矩阵
| 类型 | 线程安全 | 顺序 | 内存效率 | 推荐场景 |
|---|---|---|---|---|
HashMap |
❌ | ❌ | 中 | 单线程、大数据量 |
LinkedHashMap |
❌ | ✅ | 中 | LRU 缓存、需要顺序 |
mutableMapOf() |
❌ | ✅ | 中 | Kotlin 常规业务代码 |
ArrayMap |
❌ | ✅ | 高 | Android 小数据量（<1000） |
SparseArray |
❌ | N/A | 极高 | Int-Object 映射 |
ConcurrentHashMap |
✅ | ❌ | 中 | 多线程缓存、全局共享 |
核心原则
┌─────────────────────────────────────────────────┐
│ 1. 默认使用 mutableMapOf()（简单、可读、有顺序） │
│ 2. 多线程并发 → 立即切换 ConcurrentHashMap │
│ 3. Android Framework 风格 → 考虑 ArrayMap │
│ 4. Int 作为 Key → SparseArray 优先 │
└─────────────────────────────────────────────────┘
一句话总结
Android 开发中，大部分业务代码使用
mutableMapOf()即可；一旦涉及线程池、协程并发、全局缓存或共享状态，应优先选择ConcurrentHashMap；而在 Framework 风格的小数据量场景下，则优先考虑ArrayMap与SparseArray。
附录：推荐阅读
相关推荐
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
16
0- 0
已为社区贡献8条内容
所有评论(0)