系列文章地址:
Android 容器类 - ArraySet 原理解析(一)
Android 容器类 - ArrayMap 原理解析(二) https://mp.weixin.qq.com/s/Mq5Ndu4vJvMbeharOq5GGw
Android 容器类 - SparseArray 原理解析(三) https://mp.weixin.qq.com/s/Ii1yYgqeswfy44RXkaS8vA
Android 容器类 - SparseIntArray 原理解析(四) https://mp.weixin.qq.com/s/uSheoYGNrBHomyoQyD8XZw
相较于其他设备, 移动设备有自己的特点, 内存小是一个很突出的问题, Google 针对 Android 设备的这一特点, 开发了一套容器框架, 目的就是为了更加高效地利用内存. 接下来就对这些容器进行一下总结.
组织结构
以上是 Android 中容器的实现继承结构, 简单梳理一下:
ArraySet 实现了 Set 和 Collections 接口, 在 API 23 中添加
ArrayMap 实现了 Map 接口, 在 API 19 中添加
SparseArray,SparseIntArray,SparseBooleanArray 实现了 Cloneable 接口, 在 API 1 中添加
SparseLong 实现了 Cloneable 接口, 在 API 18 中添加
分类
从 ** 功能 ** 上划分, 可以将以上容器划分为两类:
存储元素
ArraySet 优化了 HashSet 对元素的存储
存储键值对 相较于 HashMap, 具体的优化方向如下:
ArrayMap 优化了 HashMap 存储 Object --> Object 的键值存储;
SparseArray 优化了 int --> Object 的键值存储;
SparseIntArray 优化了 int --> int 的键值存储;
SparseBooleanArray 优化了 int --> boolean 的键值存储;
SparseLongArray 优化了 int --> long 的键值存储.
优化方法
从组织结构可以看出, 可以将这些容器分为 3 类: ArraySet,ArrayMap 和剩余的容器. 通过前面的分析可以知道, ArraySet 和 ArrayMap 使用的相同的优化方式, SparseArray 在进行优化的时候使用 gc 垃圾回收策略, 故从优化方法上进行分类的话可以分一下三类:
ArraySet, ArrayMap 使用数组 mKeys 存储 key 的 hash 值, hash 值在 mKeys 的位置为 index, 并将 value 存储到 mValues 数组对应下标的位置(ArrayMap 中 key 和 value 分别在 mValues 的 index * 2 和 index * 2 + 1 的位置). 查找或者修改元素时, 使用二分查找在 mKeys 中找到元素在 mValues 的下标, 然后进行修改或者返回.
SparseArray 使用 int 类型的 mKeys 数组存储 int 类型的键, 下标为 index, 将 Object 类型的 value 存储在在 Object 类型的数组 mValues 的 index 位置, 在查找和修改时, 使用二分查找在 mKeys 中找到元素在 mValues 的下标, 然后进行修改或者返回. 在删除 value 时, SparseArray 并不直接进行数组元素的移动, 而是将待删除的 value 标记为 DELETED 状态, 在 gc 的过程中将所有非 DELETED 状态的元素移动到数组的最前面, 从而减少二分查找的时间.
SparseIntArray, SparseLongArray, SparseBooleanArray 这 3 个容器可以理解成专用容器, 使用 int 类型数组和对应类型的数组; 使用二分查找快速查找元素, 然后进行删除, 修改, 添加操作.
优化共同点与差异
虽然这些容器存储的元素类型不同, 但是通过分析可以发现他们在内存优化中的共同点, 接下来就分析下这些容器在优化上存在的共同点和差异.
共同点
数据结构
这里的数据结构是指容器的底层存储结构, 虽然在 ArrayMap 中 mValues 的长度是 mKeys 的 2 倍, 但也仅仅是数组长度上的差异, 底层存储使用的思想仍然是一样的; int 类型的数组 mKeys 里的元素时按照升序进行排列的. 相较于 HashMap 使用 Node 结构存储, 这样的存储方式使用更小的存储空间存储 k-v, 同时避免了原始数据类型的自动装箱.
查找方法 在组织结构中列出的容器, 他们在进行元素查找时, 都会先在 mKeys 数组中利用二分查找找到元素的下标 index, 然后使用 index 到 mValues 数组中对 value 进行操作.
获取带插入下标 在进行元素插入时, 会首先使用二分查找在 mKeys 数组中查找元素的下标, 如果元素不存在, 则二分查找会返回元素待插入位置的取反.
不同点
对 key 的处理 ArraySet, ArrayMap 底层实现时, 会计算待插入元素的 hash 值, 根据 hash 值, 在 mKeys 找到待插入位置; SparseArray 和 SparseXXXArray 存储的时候直接使用 key 值, 不会进行 hash 计算.
对 null 的处理 ArraySet 和 ArrayMap 允许插入 key 为 null 的元素, key 的 hash 值为 0;SparseArray 和 SparseXXXArray 存储的时由于直接使用 int 类型的数据作为 key, 故不存在 key 为 null 的情况.
缓存 为了避免频繁的内存回收, ArraySet 和 ArrayMap 添加了缓存结构, SparseArray 和 SparseXXXArray 没有缓存
扩容规则 ArraySet 和 ArrayMap 在进行扩容的时, 容量的变化规则为
4, 8 , size * 2 / 3
,SparseArray 和 SparseXXXArray 使用
ArrayUtils.newUnpaddedArray
建立新的数据, 将原来的数据拷贝到新数组中.
使用建议
虽然这些容器在 Android 设备上可以更高效地利用内存, 但是还是存在使用使用限制.
兼容性 在组织结构中, 可以看到, 并不是所有的容器都是从 API 1 就开始提供的, 在使用具体的容器时, 需要考虑应用的兼容.
对性能的影响 虽然 ArrayMap 在删除时不直接使用移动元素的方式删除元素, 但是在获取数组元素等操作中还是
对数量的限制 在对元素进行查找时会使用二分查找, 元素数量较大 (超过 1000) 时, 查找效率会降低, 相较于 HashMap 只要数量不超过 1000, 效率最多不会下降 50%.
总结
前面说了很多, 其实 Android 容器优化的根本思想就是使用 int 到其他类型的映射, 使用数组保存着两个映射, 用以优化 HashMap 对 k-v 的存储. 这种优化适用于元素数量较少 (少于 1000) 的情况.
来源: https://juejin.im/post/5be8e3856fb9a049bb7bd9f9