使用 ArrayMap And SparseArray 来优化你的 Android 应用

这篇文章将说明为什么使用 ArrayMap 和 SparseArray 优化你的 Android 应用。

每当你需要存储 key ->value 键值对数据时,第一个的想到的数据结构应该就是 HashMap .它是非常灵活的,我们到处都在使用它,而没有考虑它所带来的副作用.

如果你使用 Android Studio 开发你的应用,当你在项目中使用 HashMap 时它将会警告你使用 ArrayMap 来替代它.所以让我们来探讨为什么你应该使用 ArrayMap,和它的内部是如何工作的.

HashMap VS ArrayMap

HashMap来自 java.util.HashMap 包 ,ArrayMap 来自 amdrpod util.ArrayMap 和 android.support.v4.util.ArrayMap 包,提供support.v4来支持较低安卓的版本.

这个 官方视频 可以让你更进一步的了解它的细节.

ArrayMap是一个通用的 key->value 映射数据结构的,它的设计可以更有效的节省内存，ArrayMap保持它的映射到一个数组数据结构，一个 Integer 数组来存储每一个 item 的哈希码，一个对象数组来存储键值对，这样做避免了为每一个条目都创建一个额外的对象，它也更有效的控制了数组的大小.它自增长的复制你的存储的数据到数组-没有重建一个映射.

请注意,这个数据结构实现的目的不是为了要包含大量的条目.它通常比传统的 HashMap 慢,因为需要使用二分查找.添加和删除操作需要插入或者移除数组中的实例.

HashMap

HashMap 是一个基于 HashMap.Entry 数组对象( Entry 是它的一个内部类)。

Entry 类的实例对象包含:

• 一个泛型key
• 一个泛型 value
• 对象的哈希码
• 指向下一个Entry 的指针

当我们将一个键值对插入到 HashMap 会发生什么?

• 根据 key 计算哈希码
• 如果没碰撞直接放到bucket里
• 如果碰撞了，以链表的形式存在buckets后
• 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树
• 如果插入的数据是预先存在的,则将当前元素替换之前的元素.(保证 key 唯一).

现在当你根据key 查询hashMap 中的 value ,它将花费 O(1) 时间,但是重要的是它花费了更多的内存空间.

缺点:

• 插入每一个实例需要创建一个额外的对象,这将影响内存使用,以及垃圾收集. HashMap.Entry 本身是一个额外的对象需要被垃圾回收.
• HashMap 每一次操作都需要压缩或者扩充.这随着对象的增长这是一个很昂贵的操作.
• 在 Android 内存是一个很重要的,连续分配和回收内存,随着垃圾回收期,将导致你的 Android 应用延迟.

记住,垃圾回收对于 Android 应用的性能是一个重负.当垃圾回收期正在进行,你的应用将不能运行.

ArrayMap

ArrayMap 使用两个数组.

这个对象使用内部的一个 Object[ ] mArray 存储数据, int[] mHashes 来存储哈希码.

当插入一个键值对:

• 这个键值对将自动装箱.
• key 插入到 mArray 可用的下一个位置.
• value 插入到 key 所在的下一个位置.
• 根据 key 计算哈希码,将他放置在 mHashes[ ]的下一个可用的位置.

当你查找这个 key :

• 计算这个key 的哈希码,使用二分查找哈希码在 mHashes所在的索引.
• 一旦我们根据哈希码得到索引,我们就知道了key 在 mArray的2 index 位置, value 在 mArray 的2 index+1的位置.此时,时间复杂度从O(1) 到 O(logN),但是它非常节省内存.
• 当你存储100条数据,你感受不到任何的延迟.但是这将使你的应用程序更加的高效.

推荐数据结构：

ArrayMap<K,V> 替换 HashMap<K,V>
ArraySet<K,V> 替换 HashSet<K,V>
SparseArray 替换 HashMap<Integer,V>
SparseBooleanArray 替换 HashMap<Integer,Boolean>
SparseIntArray  替换 HashMap<Integer,Integer>
SparseLongArray 替换 HashMap<Long,V>
LongSparseArray<V> 替换 HashMap<Long,V>

原文链接: Android App Optimization Using ArrayMap and SparseArray