—— 从集合使用、线程安全到 Android Framework 实践基于 Android 16API Level 36与 OpenJDK 17难度进阶一、前言在 Android 开发中Map 几乎无处不在// 临时缓存 val cache mutableMapOfString, User() // 数据聚合 val userMap HashMapString, User() // 全局图片缓存 val imageCache ConcurrentHashMapString, Bitmap()很多开发者都知道HashMap 线程不安全ConcurrentHashMap 线程安全但真正深入思考过下面问题的人并不多Kotlin 的mutableMapOf()底层到底是什么HashMap 为什么会线程不安全具体在哪些操作上ConcurrentHashMap 为什么性能比Hashtable高几十倍ConcurrentHashMap 的CAS synchronized是如何协作的Android Framework为什么大量使用 ArrayMap而不是 HashMapRepository、ViewModel、全局缓存分别应该选择什么 Map本文将从Android 16 源码角度彻底讲清这些问题。二、Map 家族全景图2.1 Java 集合体系Map │ ┌────────────┼────────────┐ │ │ │ HashMap LinkedHashMap TreeMap │ │ │ │ Hashtable ConcurrentHashMap │ EnumMap2.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(): MutableMapK, V LinkedHashMap()因此val map mutableMapOfString, Int() // 完全等价于 val map LinkedHashMapString, Int()3.2 为什么要设计成 LinkedHashMapGoogle 和 JetBrains 的考虑可预测性大多数开发者期望 Map 保持插入顺序调试友好打印日志时顺序固定Android 兼容性LinkedHashMap在所有 API 级别都可用3.3 实际验证fun testMapOrder() { val map mutableMapOfString, Int() map[B] 2 map[A] 1 map[C] 3 println(map.keys) // 输出: [B, A, C] (保持插入顺序) val hashMap hashMapOfString, 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 HashMapK,V { // 哈希桶数组延迟初始化 transient NodeK,V[] table; // 链表节点 static class NodeK,V { final int hash; final K key; V value; NodeK,V next; } // 红黑树节点当链表长度 8 时转换 static final class TreeNodeK,V extends LinkedHashMap.EntryK,V { TreeNodeK,V parent; TreeNodeK,V left; TreeNodeK,V right; TreeNodeK,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, ...) { NodeK,V[] tab; NodeK,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 NodeK,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.7Segment 分段锁继承 ReentrantLock每个 Segment 锁一个 Hash 桶组较好JDK 1.8CAS synchronized volatile每个 Hash 桶单独锁极高6.2 核心设计原则┌─────────────────────────────────────┐ │ 读操作完全无锁 │ │ (volatile 保证可见性无需加锁) │ ├─────────────────────────────────────┤ │ 写操作细粒度锁 │ │ (只锁当前操作的 Hash 桶的头节点) │ ├─────────────────────────────────────┤ │ 扩容操作多线程协作 │ │ (每个线程负责一部分桶加速扩容) │ └─────────────────────────────────────┘七、ConcurrentHashMap 源码深度解析7.1 核心成员变量public class ConcurrentHashMapK,V { // 哈希桶数组volatile 保证可见性 transient volatile NodeK,V[] table; // 扩容时的临时数组 private transient volatile NodeK,V[] nextTable; // 控制标识符灵魂字段 private transient volatile int sizeCtl; // 基础计数器CAS 更新 private transient volatile long baseCount; // 计数器数组高并发时使用 private transient volatile CounterCell[] counterCells; }7.2 Node 节点设计static class NodeK,V { final int hash; final K key; volatile V val; // volatile 保证值可见 volatile NodeK,V next; // volatile 保证链表可见 Node(int hash, K key, V val, NodeK,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 (NodeK,V[] tab table;;) { // 自旋直到成功 NodeK,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 NodeK,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 (NodeK,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; } NodeK,V pred e; if ((e e.next) null) { pred.next new NodeK,V(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 红黑树插入 NodeK,V p; binCount 2; if ((p ((TreeBinK,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 │ │ └──────────────────────┘ │ ▼ [完成]八、sizeCtlConcurrentHashMap 的灵魂8.1 sizeCtl 的作用private transient volatile int sizeCtl;这是一个多状态复用的控制字段通过不同的值表示不同状态sizeCtl 值含义0数组未初始化使用默认容量 160初始化完成表示扩容阈值capacity * 0.75-1正在初始化table 正在创建0 且 ≠ -1正在扩容高 16 位扩容标识戳低 16 位参与扩容线程数18.2 源码验证// 初始化时的 CAS 逻辑 private final NodeK,V[] initTable() { NodeK,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; NodeK,V[] nt (NodeK,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 ForwardingNodeK,V extends NodeK,V { final NodeK,V[] nextTable; ForwardingNode(NodeK,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() 会去新表查找 NodeK,V find(int h, Object k) { outer: for (NodeK,V[] tab nextTable;;) { NodeK,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 (NodeK,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 ArrayMapK, V { // 两个平行数组存储 key 和 value int[] mHashes; // 哈希值数组 Object[] mArray; // Key-Value 交替存储 int mSize; // 二分查找定位 key int indexOf(Object key, int hash) { // 使用二分查找在 mHashes 中查找 // 找到后对比 mArray 中的 key } }为什么 Android 使用 ArrayMap对比项ArrayMapHashMap内存占用两个数组无额外 Node 对象每个 Node 约 32 字节额外开销查找速度O(log n) 二分查找O(1) 哈希查找GC 压力小无大量小对象大频繁创建 Node适用场景小数据量 1000大数据量11.2 SparseArray 系列// Android 特有避免 int → Integer 装箱 SparseArrayString map new SparseArray(); map.put(1, one); map.put(2, two); // Long 版本 LongSparseArrayString longMap new LongSparseArray(); // 支持 key 和 value 均为 int SparseIntArray intMap new SparseIntArray();Framework 中的典型使用// ActivityManagerService 中的进程管理 final SparseArrayProcessRecord mProcesses new SparseArray(); // View 系统 ID 映射 private SparseArrayView mChildren;十二、Android 开发中的真实场景12.1 ViewModel 中的缓存class UserViewModel : ViewModel() { // ✅ 主线程访问使用 mutableMapOf private val userCache mutableMapOfString, User() fun getUser(id: String): User? { return userCache[id] // 主线程安全 } }12.2 Repository 中的缓存class UserRepository(private val api: UserApi) { // ⚠️ 多线程访问IO 线程、协程 private val cache ConcurrentHashMapString, User() suspend fun getUser(id: String): User { return cache.getOrPut(id) { api.fetchUser(id) // 网络请求 } } } // Kotlin 扩展函数非原子注意使用 fun K, V ConcurrentHashMapK, V.getOrPut(key: K, value: () - V): V { return this[key] ?: value().also { this[key] it } // 非原子 }12.3 全局单例缓存object ImageCache { // ✅ 全局访问必须线程安全 private val cache ConcurrentHashMapString, 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 mutableMapOfString, User() } // 多个协程同时写入 class UserManager { suspend fun updateUser(user: User) { withContext(Dispatchers.IO) { UserCache.cache[user.id] user // 多线程并发写 } } }问题分析mutableMapOf()实际是LinkedHashMapLinkedHashMap非线程安全多协程在Dispatchers.IO上并发执行put()发生数据覆盖导致缓存错乱解决方案object UserCache { // ✅ 修改为 ConcurrentHashMap val cache ConcurrentHashMapString, User() }十四、高频面试题汇总Q1: HashMap 为什么线程不安全3个点数据覆盖多线程同时put到空桶后覆盖前可见性问题数组非volatile线程间修改不可见扩容问题JDK 7头插法导致环形链表CPU 100%Q2: 为什么树化阈值是 8泊松分布计算在loadFactor0.75下链表长度达到 8 的概率仅为 **0.000006%**此时哈希冲突严重树化收益大于维护成本。Q3: ConcurrentHashMap 为什么不允许 null避免二义性map.get(key)返回null可能是 key 不存在也可能是 value 为null并发环境下containsKey的结果可能在瞬间过期无法准确判断Q4: sizeCtl 有什么作用一个字段控制三种状态0未初始化-1初始化中0扩容阈值0且 ≠ -1正在扩容高 16 位标识戳低 16 位参与线程数1Q5: 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 小数据量1000SparseArray❌N/A极高Int-Object 映射ConcurrentHashMap✅❌中多线程缓存、全局共享核心原则┌─────────────────────────────────────────────────┐ │ 1. 默认使用 mutableMapOf()简单、可读、有顺序 │ │ 2. 多线程并发 → 立即切换 ConcurrentHashMap │ │ 3. Android Framework 风格 → 考虑 ArrayMap │ │ 4. Int 作为 Key → SparseArray 优先 │ └─────────────────────────────────────────────────┘一句话总结Android 开发中大部分业务代码使用mutableMapOf()即可一旦涉及线程池、协程并发、全局缓存或共享状态应优先选择ConcurrentHashMap而在 Framework 风格的小数据量场景下则优先考虑ArrayMap与SparseArray。附录推荐阅读Java HashMap 源码OpenJDK 17ConcurrentHashMap 源码分析Doug Lea 论文Android ArrayMap 源码Kotlin Collections Guide相关推荐Android 16API Level 36Activity 启动流程源码级解析Android 高级工程师面试参考答案性能优化