ScatterMap，更好用的 HashMap（一）
前言
Hashmap 是一种非常常见的数据结构，不出意外 Jetpack Compose 在编写的时候也有大量用到。Kotlin 可以通过调用mutableMapOf()轻松创建一个新的可变 Hashmap，然后根据需要使用映射（map），大多数开发者基本上也都这样用。然而，在搞 Jetpack Compose 这样的工具包时，我们想尽量降低工具包对应用程序性能的影响。
所以让我们先看一下mutableMapOf()的实现：
public inline fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()
LinkedHashMap 是一个 expected类，在 Android 平台的实现取决于 Java 的 同名类
public actual typealias LinkedHashMap<K, V> = java.util.LinkedHashMap<K, V>
由于这个 API 身经百战，见得多了，在 Kotlin 中作为标准 Hashmap 确实是个不错的选择1。然而LinkedHashMap 的实现并不算“内存友好”，因为每个插入到映射（map）中的条目都会创建一个新的 LinkedHashMapEntry 实例（对于 HashMap 、HashMap.Node 这样的基类也一样），在我们的使用场景之下，就带来了一些负面影响：
- 每个条目使用的内存比必要的多。在
LinkedHashMap中存储一个Int需要额外的 3 个指针以及哈希副本，外加一个对象的开销。 - 内存访问，特别是调用迭代（iterations）时不够友好，尤其是随着堆内存的混乱而逐渐加剧。
- 增大 GC 的压力，尤其在旧设备和/或旧版本的 Android Runtime（ART）上跑的时候压力山大。
为了解决这些问题，我们开发了一个名为 ScatterMap 的新Hashmap，旨在更加高效利用内存。这个新的 API 已经作为 androidx.collection 库的一部分，并在版本 1.4 中最近达到了候选发布（RC）状态。
ScatterMap 的一些特性包括：
- 每个条目的开销为 1 字节。
- 除非映射需要扩展其内部存储，否则插入不会产生分配。
- 迭代（iterations）无需额外分配内存。
- 常见 API 的实现都无需额外分配内存（例如，
removeIf()是inline的，以避免分配 predicate lambda）。 - 键（Key）和值（Value）被线性存储，当在映射（
map）上进行迭代时，可以更好地进行内存缓存，无需额外的间接引用。 - 在插入、移除、检索和迭代方面的性能要优于
LinkedHashMap，或至少与LinkedHashMap相当。 - API 与 Kotlin 的映射（
map）一致（工厂函数、ScatterMap与MutableScatterMap等）。 - 提供专门的变体以存储基本类型（例如
IntIntMap或ObjectFloatMap），无需自动装箱。
以下是在一台运行 Android 13 的 Pixel 6 手机上的性能跑分数据2：
| 测试项 | LinkedHashMap | ScatterMap |
|---|---|---|
| 插入 1000 个元素 | 43,073 ns |
24,654 ns |
| 移除 1000 个元素 | 6,642 ns |
7,840 ns |
| 迭代 1000 个元素 | 10,308 ns |
4,044 ns |
| 查询 1000 个元素3 | 9,832 ns |
10,678 ns |
| 内存分配4 | 1,003 |
4 |
请注意，在这个测试前提之下，LinkedHashMap 的迭代测试成绩已经是它能够跑出的最高分数了，因为所有元素都是一个接一个立刻创建的，这就使得它们具有了良好的内存局部性。而 ScatterMap 的性能则能够做到随时间保持不变。
ScatterMap 的主要缺点是它没有实现标准的 Map 接口，这会导致不友好的内存行为。不过你可以通过调用 asMap() 方法从 ScatterMap 中获取一个 Map或者 MutableMap，因为默认的 API 尽量提供了很多 Map 中的常见功能，如 forEach()、removeIf()、any()、count() 等。
所以，ScatterMap 是更好的 HashMap 吗？答案是肯定的，如果你需要优化内存分配、内存使用和内存访问，我认为它是值得一试的，你的职责就是根据实际使用场景去选择最终要用哪种数据结构。
在未来的文章中，我将解释 ScatterMap 的由来，它的内部工作原理，以及如何优化为生成高效的 ARM 64 汇编5，以及如何利用 SIMD 指令进一步提升性能。
- 我其实对这个结论也持保留意见，
LinkedHashMap保证了可预测的迭代顺序，如果你依赖这种行为，在实际开发过程中接受Map或MutableMap这样的泛型类型，可能会导致一些微妙的错误。 - 这些是最初的跑分数据，在这之后
ScatterMap有进行一些小的优化。︎ - 方法就是调 1000 次
get(key: K)。 - 指的是插入 1000 个元素。
