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 线程安全

但真正深入思考过下面问题的人并不多：

1. Kotlin 的mutableMapOf()底层到底是什么？

2. HashMap 为什么会线程不安全？具体在哪些操作上？

3. ConcurrentHashMap 为什么性能比Hashtable高几十倍？

4. ConcurrentHashMap 的CAS + synchronized是如何协作的？

5. Android Framework为什么大量使用 ArrayMap，而不是 HashMap？

6. Repository、ViewModel、全局缓存分别应该选择什么 Map？

本文将从Android 16 源码角度，彻底讲清这些问题。

二、Map 家族全景图

2.1 Java 集合体系

Map │ ┌────────────┼────────────┐ │ │ │ HashMap LinkedHashMap TreeMap │ │ │ │ Hashtable ConcurrentHashMap │ EnumMap

2.2 Kotlin 常见 API 的真实面目

关键结论：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 的考虑：

1. 可预测性：大多数开发者期望 Map 保持插入顺序

2. 调试友好：打印日志时顺序固定

3. 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 演进历史

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;

这是一个多状态复用的控制字段，通过不同的值表示不同状态：

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？

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 // 多线程并发写！ } } }

问题分析

1. mutableMapOf()实际是LinkedHashMap

2. LinkedHashMap非线程安全

3. 多协程在Dispatchers.IO上并发执行put()

4. 发生数据覆盖，导致缓存错乱

解决方案

object UserCache { // ✅ 修改为 ConcurrentHashMap val cache = ConcurrentHashMap<String, User>() }

十四、高频面试题汇总

Q1: HashMap 为什么线程不安全？（3个点）

1. 数据覆盖：多线程同时put到空桶，后覆盖前

2. 可见性问题：数组非volatile，线程间修改不可见

3. 扩容问题（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块内完成了：

1. 双重检查 key 是否存在

2. 创建新值

3. 插入 Map

整个过程原子执行。

Q7: Android 为什么提供 ArrayMap？

1. 内存效率：无需创建 Node 对象，减少 GC 压力

2. 移动端特性：大多数场景数据量小（< 1000），二分查找足够快

3. 避免装箱：配合SparseArray可避免 int→Integer 转换

十五、总结与选型建议

最终选型矩阵

核心原则

┌─────────────────────────────────────────────────┐ │ 1. 默认使用 mutableMapOf()（简单、可读、有顺序） │ │ 2. 多线程并发 → 立即切换 ConcurrentHashMap │ │ 3. Android Framework 风格 → 考虑 ArrayMap │ │ 4. Int 作为 Key → SparseArray 优先 │ └─────────────────────────────────────────────────┘

一句话总结

Android 开发中，大部分业务代码使用mutableMapOf()即可；一旦涉及线程池、协程并发、全局缓存或共享状态，应优先选择ConcurrentHashMap；而在 Framework 风格的小数据量场景下，则优先考虑ArrayMap与SparseArray。

附录：推荐阅读

• Java HashMap 源码（OpenJDK 17）

• ConcurrentHashMap 源码分析（Doug Lea 论文）

• Android ArrayMap 源码

• Kotlin Collections Guide

相关推荐

Android 16（API Level 36）Activity 启动流程源码级解析

Android 高级工程师面试参考答案：性能优化