Android 深度实践

Appearance

高性能不可变集合 ​

源：kotlinx.collections.immutable

在 Kotlin 标准库中，List 接口仅仅承诺了“只读视图 (Read-only View)”，而非“不可变 (Immutability)”。这意味着，虽然你无法通过 List 接口修改数据，但底层的数据源可能依然是可变的，甚至被其他线程修改。

为了解决并发安全与状态一致性问题，JetBrains 推出了 kotlinx.collections.immutable 库，基于 HAMT (Hash Array Mapped Trie) 实现了真正的持久化数据结构。

依赖配置 ​

该库并未包含在 Kotlin 标准库中，需单独引入：

kotlin
implementation("org.jetbrains.kotlinx:kotlinx-collections-immutable:0.3.7")
groovy
implementation 'org.jetbrains.kotlinx:kotlinx-collections-immutable:0.3.7'

痛点：标准库 List 的“谎言” ​

标准库的 List 是接口。当你拿到一个 List 时，你无法保证它是真的不可变。

kotlin
val mutableList = mutableListOf(1, 2, 3)
val readOnlyList: List<Int> = mutableList // 向上转型

println(readOnlyList) // [1, 2, 3]

// 另一个线程或者逻辑修改了源数据
mutableList.add(4)

// readOnlyList 竟然变了！这在并发编程和 Compose 状态管理中是致命的。
println(readOnlyList) // [1, 2, 3, 4]

核心原理：结构共享 (Structural Sharing) ​

如果你有一个包含 100 万个元素的不可变列表，当你想添加一个元素时，拷贝整个列表的代价是 $O(N)$，这显然不可接受。 持久化集合通过 结构共享 解决了这个问题。

基于 Trie 的实现 ​

持久化 List 和 Map 底层通常实现为 位图字典树 (Bit-mapped Trie)。

  1. 树状结构：集合被组织成一棵宽树（通常分叉因子为 32）。
  2. 路径复制：当你修改某个节点时，不需要复制整棵树，只需要复制从根节点到该叶子节点路径上的几个节点。
  3. 节点复用：未被修改的分支会直接指向旧版本的节点。

性能复杂度

由于树非常“宽”且“浅”（32 叉树），即使存 10 亿个数据，树高也仅为 7 层左右。 因此，增删改查的操作复杂度接近常数级 $O(log_{32} N)$，几乎等同于 $O(1)$。

接口辨析：Immutable vs Persistent ​

理解这两个接口的区别对于正确使用该库至关重要。

接口说明特性
ImmutableList纯粹的不可变视图只有读取方法。不保证底层实现是高效的 Trie。
PersistentList具备修改能力的不可变集合继承自 ImmutableList。提供修改方法 (add/remove)，每次修改返回新实例。

核心 API 与用法 ​

该库定义了两套核心接口：

  • ImmutableList: 真正的不可变。完全没有 add/remove 方法。
  • PersistentList: 继承自 ImmutableList，提供了“修改并返回新实例”的方法。

1. 创建与修改 ​

kotlin
// 创建持久化列表
val list = persistentListOf("A", "B", "C")

// ❌ 错误：list 是不可变的，没有 add 方法
// list.add("D") 

// ✅ 正确：add 返回一个新的列表实例
val newList = list.add("D")

// 原列表保持不变（结构共享）
println(list)    // [A, B, C]
println(newList) // [A, B, C, D]

### 转换函数：toImmutableList vs toPersistentList

这是最容易被忽视的性能陷阱：

- **`toPersistentList()`**: 执行真正的**深度转换**，将数据搬运到高性能的 Trie 结构中。适用于后续需要频繁进行修改（增删）并产生新版本的场景。
- **`toImmutableList()`**: 仅将集合转换为 `ImmutableList` 接口。如果原集合已经是不可变的，它直接返回；否则，它可能会创建一个简单的**不可变包装器**。适用于仅为了解决 Compose 稳定性、后续不再进行任何修改的场景。

2. 批量修改：mutate ​

如果你需要进行一系列复杂的修改，频繁生成中间对象会造成浪费。可以使用 mutate 临时转换为可变构建器。

kotlin
val result = list.mutate { mutableList ->
    // 在这个 lambda 内部，mutableList 是可变的
    // 所有的修改都是基于临时结构的，性能极高
    mutableList.add("E")
    mutableList.remove("A")
    mutableList[0] = "X"
}
// lambda 结束后，自动转换回 PersistentList

Jetpack Compose 实战：性能救星 ​

在 Compose 中，ImmutableList 是优化重组（Recomposition）的神器。

问题：Unstable 的 List ​

Compose 编译器认为标准的 List 是 Unstable（不稳定的），因为它无法确定底层的实现是否可变。因此，每当重组发生时，即便 List 内容没变，Compose 也会被迫重新测量和绘制使用该 List 的组件。

解决方案：使用 PersistentList ​

kotlinx.collections.immutable 中的集合被标记为 @Immutable。

kotlin
@Composable
fun ItemList(items: List<String>) { // List 被视为不稳定的
    LazyColumn {
        items(items) { Text(it) }
    }
}
kotlin
@Composable
fun ItemList(items: ImmutableList<String>) { // 编译器确信它是不可变的
    // 只有当 items 引用发生变化时，才会触发重组
    LazyColumn {
        items(items) { Text(it) }
    }
}

性能对比与选型建议 ​

操作类型ArrayList (可变)PersistentList (持久化)
随机读取 (get)$O(1)$ (极快)$O(log_{32} N)$ (很快)
尾部追加 (add)$O(1)$ (摊销)$O(log_{32} N)$ (很快)
中间插入/删除$O(N)$ (慢，需数组拷贝)$O(log_{32} N)$ (很快，仅需路径复制)
内存占用紧凑较高 (节点对象开销)
线程安全不安全天然安全

什么时候用？ ​

  1. Redux/MVI 架构：State 必须是不可变的，使用持久化集合可以极低成本生成新 State。
  2. Jetpack Compose：为了获得最佳的 UI 性能稳定性。
  3. 多线程共享：无需加锁即可安全读取数据。

什么时候不用？ ​

  1. 紧凑循环中的局部变量：如果只是在函数内部处理数据，不需要跨线程或跨层级，普通的 ArrayList 性能更好且不产生垃圾对象。
  2. 超大规模数据初始化：建议先用 ArrayList 构建，最后调用 toPersistentList() 转换。