sparseArray作为google推出的在android上替代hashmap的容器类，相信大家使用的也比较频繁。就像自己一直都在使用该类，但是要说具体涉及到内部的代码说实话还真没怎么留意过，这段时间正好有点空闲，顺便去看了下内部原理。整体来说还是不那么复杂的，这里就大概说下自己看sparseArray源码的一些心得，具体的源码分析实在不想写了，网上有很多不错的文章很容易找到。
这里列出几个问题，如果你都知道的话那么肯定是看过源码的，如果一脸懵逼的话，劝你有时间也看看源码。
1 为什么使用sparseArray
2 sparseArray如何减少内存的使用
3 为什么SparseArray不适合存储大量的数据
4 SparseArray删除操作理解
为什么使用sparseArray
关于这个问题，以前是一直觉得sparseArray是google针对android定制的容器类，在性能上更优才有使用的必要，但是要说哪方面性能更优，毛估下可能是增删改查速度更快，如果有人和我有一样的想法，那么只能说对sparseArray的理解还不到位，其实在看过sparseArray源码后你会发现，包括网上的一些针对hashmap和sparseArray性能对比的文章，在增删改查方面sparseArray是没有优势可言，甚至在一些极端情况下如逆序插入数据，性能上是不如hashmap的。google提倡使用sparseArray是从内存使用方面来考虑的，在牺牲一定的增删改查性能的同时减少内存的使用，换句话说也就是以时间换空间的做法。
如何减少内存的使用
其实很简单就是去掉了拆箱装箱的操作，改用int来代替Integer。以下是SparseArray的官方表述一部分内容，明确说到了auto-boxing这个问题。
/**
* SparseArrays map integers to Objects. Unlike a normal array of Objects,
* there can be gaps in the indices. 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在内存方面优化做的主要一件事就是将hashmap中要使用的Integer的key换成了int类型，java当中int只占2个字节大小而一个Integer的大小肯定不止2字节，所以在大量存储数据的时候SparseArray能减少一定数量的内存使用，这也正是SparseArray的主要作用。
为什么SparseArray不适合存储大量的数据
这里说的大量数据是指存储超过千条，按照一些文章得出的结论就是
SparseArray不适用于数量级过大的存储，通常在千级以内
为什么会有这么个说法，这里就不累述源码，只说下自己大概理解。
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
DELETED就是一个标志位，用来表示对应index上的数据被删除了，后面再讲，mGarbage表示是否需要合并操作和DELETED有一定的关系，后面再讲。mSize很简单就表示存储了多少个数据，主要的成员变量就是mKeys和mValues，可以看出SparseArray内部是将key和value分开存储到不同数组里面的，这两个数组的length是一样的大小的。以demo代码来说明mkeys的存储顺序
SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(1, "v1");
sparseArray.put(5, "v2");
sparseArray.put(9, "v3");
sparseArray.put(2, "v4");
Log.e("mandy", "result==" + sparseArray);
打印结果为result=={1=v1, 2=v4, 5=v2, 9=v3}，和我们的存储顺序是不一致的，实际上mKeys中的存储的key是按从小到大进行排序的，SparseArray在插入数据的时候通过二分查找法已经确定了每一个要插入数据的正确位置，当你要插入的数据在mkeys的中间位置时，SparseArray就需要通过移动该位置以及后面的数据腾出空间来存放该key，所以说SparseArray在插入数据时往往会伴随着数据的大量移动，当数据量很大时这种开销是不可忽略的，这也就是为什么网上很多分析SparseArray和hashmap的文章常说的“SparseArray不适用于数量级过大的存储，通常在千级以内”的主要原因。不过话又说回来，在移动端要存储这么多的数据这种使用场景似乎比较难遇到。
关于SparseArray的删除操作
这个应该说是SparseArray比较特别的地方，看下源码中关于delete的代码
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
先通过二分查找得到对应的index，然后判断下标志位，如果不是DELETED就直接设置为DELETED并将mGarbage设置为true，就是这么简单，可以看出删除操作和插入操作有一个明显的不同点在于，插入操作往往伴随着其他位置数据的移动，而删除操作就要简单很多，仅仅设置下标志位就完事了。这其实就是google针对删除操作的一点小优化，把真正删除被标志为DELETED的数据的时机放到了真正要执行的时候。所谓的真正要执行的时候在代码里面有所体现，比如在put代码里有如下代码
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
当mGarbage为true并且mKeys里面"满员"的情况下，这里的满员并非是真正意义上的满员，如果之前执行过delete操作，那么那些被标志为DELETED的数据也会被当成"满员"中的一员，显然这些DELETED是无效，需要被删除掉的，所以这时候才会真正执行删除操作也就是调用gc方法。代码就不黏贴了，里面的操作就是删除被标志为DELETED的数据，然后将后面的数据往前移位。
总结
关于sparseArray代码本身是不多的，源码也就400多行，花点时间也就看完了，也算了却了自己的一个心里疙瘩，之前面试有被问到sparseArray的源码，答曰有使用过，没时间去看具体实现，现在可以非常确定地说自己看过源码了。sparseArray的存储结构也就是两个长度一样的数组，其中mkeys是按增序排序的，这个需要留意一下。在插入数据时其实和arraylist比较类似，都需要执行移位操作，这也是在极端情况下如倒序插入大量数据的时候性能差的原因。sparseArray的删除操作做了一点优化，把删除延迟到真正需要执行的时候
网友评论