Android性能优化-SparseArray

SparseArray是Android框架独有的类。是Google官方推荐当key为整形的时候，（key，value）的形式，替代HashMap的一种存储结构，使用SparseArray可以避免java的自动装箱，拆箱的过程，而且相比较HashMap，Sparse更节省内存。

我们在使用一种数据结构的时候会关注，这种结构的效率，包括时间和空间两点。实际测试了一下。

正向插入时

long btimeSp=System.currentTimeMillis();
SparseArray sparse=new SparseArray();
for(int i=0;i<100000;i++){
sparse.put(i,i);
}
long ftimeSp=System.currentTimeMillis()-btimeSp;

long btimeHash=System.currentTimeMillis();
HashMap hash=new HashMap();
for(int i=0;i<100000;i++){
hash.put(i,i);
}
long ftimeHa=System.currentTimeMillis()-btimeHash;
正向插入100 000条 Sparse: 17ms Hash: 44ms

正向插入的时候，SparseArray相比较HashMap要快一倍以上。

反向插入时

long btimeSp=System.currentTimeMillis();
SparseArray sparse=new SparseArray();
for(int i=100000;i>0;i--){
sparse.put(i,i);
}
long ftimeSp=System.currentTimeMillis()-btimeSp;

long btimeHa=System.currentTimeMillis();
HashMap hash=new HashMap();
for(int i=100000;i>0;i--){
hash.put(i,i);
}
long ftimeHa=System.currentTimeMillis()-btimeHa;
反向插入100 000条 Sparse: 6561ms Hash: 42ms

可见反向插入的时候在数据量到达10 0000级别的时候，SparseArray比正向插入要慢百倍以上（SparseArray在android性能优化典范中说到适合数量级在千以内）

但如果反向插入1 0000的时候占用内存 SparseArray和HashMap 10 0000条的时候Sparse: 82ms Hash: 6ms，这时就到了相差了10倍左，1000的时候就比较相近了（注意这里我们看的是SparseArray在最差的情况下）

这样可以看出SparseArray的插入效率并不是很稳定,至于其中的原因可以在源码中找到。

public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
...
}

static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;

while (lo <= hi) {
    final int mid = (lo + hi) >>> 1;
    final int midVal = array[mid];

    if (midVal < value) {
        lo = mid + 1;
    } else if (midVal > value) {
        hi = mid - 1;
    } else {
        return mid;  // value found
    }
}
return ~lo;  // value not present

}
put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，SparseArray通过Key值的大小维持了一个有序的数组。

Sparse: 3.52M Hash: 8.14M

我们已经看到了相比较HashMap SparseMap的优势是更节省内存，时间效率上SparseMap没有HashMap稳定，但相对Android对于内存更加敏感，使用SparseArray显然更加合适，SparseArray是时间和空间的一个折中，而且我们测试的是在10 0000这个数量级（而且是最差的情况），在数量级较大的时候，不停地插入数据，由于存储数据的是数组，这样会创建新的数组，数据量较大的时候每次创建与复制的过程都很耗时，SparseArray会在index超出的时候重新创建一个长度是原来二倍的数组（SparseArray 的key和value是用两个数组存储）

mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value)
GrowingArrayUtils的insert

public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
增长长度

public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
这里我们看到了插入数据时的移位的过程，而且超出数组界限会创建一个长度为原来2倍的数组，数据量越大put时需要移位的数据就越多，这也是我们不希望看到的，这也就是推荐使用数量级在千以内的原因。但如果在千数量级内，SparseArray的性能显然要好很多，查找的过程是二分法查找，效率也相当的不错，内存比HashMap至少节省一半。SparseArray还避免了java的自动装箱的行为，key和value分别使用两个数组存储key直接存储的是int，对于HashMap，我们在put的时候就执行了装箱。

我们传入的是int，但这里会装箱为Integer，当我们取值的时候执行的是 i.intValue()，对于HashMap又会将<Key，Value>封装成为HashMapEntry，int占用 4个字节，对于Integer占用的字节数，至少包含实例数据和指向类数据的指针，实例数据是int占用4字节，指向类数据的指针占用4字节，Integer至少包含8字节。

总结：

1.SparseArray只能在key为int时替换HashMap。

2.SparseArray不适用于数量级过大的存储，通常在千级以内。

3.SparseArray效率比较HashMap不是很稳定，数量级较小效率较高，但比较HashMap更节省内存。

还有两个类SparseBooleanArray和SparseIntArray分别对应的是特定 int -> boolean ，int -> int

对于key值比较大的可以使用LongSparseArray