Android数据结构之SparseArray _Android

文章插图

一、前言在Android开发中，当需要存储键值对时，一般都是用JAVA自带的HashMap 。但是细心的同学可能会发现，有时候如果实际的HashMap的key-vaule中的key是Integer时，AndroidStudio会提示一个warnning，具体是说推荐使用SparseArray替代HashMap：

文章插图

【Android数据结构之SparseArray】虽然说warnning不影响实际功能，但是有个warnning放在那里总让人不爽。因为是lint静态扫描报的，可以用@SuppressLint("UseSparseArrays")忽略掉。但是既然google特地出了这么一个类用来替代key为Integer的HashMap，那是不是真的比HashMap更好用？
二、优缺点

It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mApping.

源码的注释除了提到SparseArray有节约自动装箱开销的优点外，还提到SparseArray因为少了需要Map.Entry<K, V>作为辅助的存储结构引入的内存开销。
因为Map<K, V>的泛型声明，key必须是Integer不能是int，所以确实会带来自动装箱的问题。
这两个优点都是让SparseArraymore memory efficient的，这是因为SparseArray的诞生就是针对某些Android设备内存比较紧张的情况的。
但是一般来说，SparseArray是比Hashmap慢的，在数据集大小只有上百个的时候，差别不大。

文章插图

三、使用不管是HashMap还是SpareArray，他们的作用都是维护一组逻辑上的key-value的对应关系。那么，在这组关系上最常做的操作就是存和取了。
存/取
HashMap的存操作和取操作分别对应方法put(K key, V value)和get(Object key)，大概用过HashMap的没有不知道这两个方法的。而SpareArray对的两个方法分别是put(int key, E value)和get(int key)，和HashMap的方法看起来几乎没有区别，key为Integer的hashmap的相关代码可以无缝换成SpareArray 。

文章插图

遍历
SpareArray的遍历要稍微麻烦些。
首先先建立一个概念，SparseArray执行put的时候其实是按照key的大小有序插入的。简单来说，SparseArray维护了各个键值对的排序关系，具体的规则是以key升序排列。所以不同于HashMap只能通过key查找value，Sparse还能通过index查找value(或者key)，方法是valueAt(int index)(或者keyAt(int index)) 。这里的index是升序排序中键值对的位置，index是SparseArray相比Map多出来的概念，看了后面的源码实现分析就好理解了。
拿上面的代码举例，put了key为100和200的两个键值对，size为2，200-"firstValue"这对key-value对在index 0的位置，100-"secondValue"这对键值对在index 1的位置。顺序是根据key的大小排的，跟put的先后顺序无关。所以valueAt(0)拿到的是"secondValue" 。
具体的遍历代码：

文章插图

文章插图

四、实现细节和hashmap比较
大致讲下hashmao的原理。hashmap使用key的hashcode来决定entry的存放位置，解决hash冲突使用的开散列方法，所以hashmap的底层数据结构看起来是一个链表的数组，链表的节点是包含了key和value的Entry类。看起来就像下图：

文章插图

而SparseArray的底层数据结构更简单，只有int[] mKeys和Object[] mValues两个数组。那这里就有个问题了：不同于HashMap专门用一个Entry的类存放key跟value，SpareArray里key和value分别存放在两个数组里，那key和value是怎么对应上的？
答案就是，是根据index对应的，mKeys和mValues中index一样的key和value就是相互对应的。所以SparseArray实际存储的数据看起来是这样的：

文章插图

HashMap中基于Entry建立的key-value对应关系会导致Entry占用内存，而sparse基于index的对应关系是逻辑的，节省下了Entry类的内存，这又是SparseArray的一个优点。
存/取
前面提到，SparseArray中实际存储的数据是有序的。那么保证有序的关键就在每次的存和删操作中：在原本有序的情况下，保证存和删操作后还是有序的。