Android 中的SparseArray

文章出处：https://blog.csdn.net/shift_wwx/article/details/47399829

请转载的朋友标明出处~~

前言：关于SparseArray 或者 相关的如SparseIntArray 网上相关的例子还是很多的，个人还是习惯性根据source code 总结一下。

总结版本基于4.4

一、SparseArray与HashMap

SparseArray是专门为Android提供了一种更加适合Android开发的数据结构，与HashMap比较效率会更高。初看之下，好像是一种数组，其实不然。数组的index是连续的。而SparseArray可以不连续，所以导致SparseArray就具有HashMap的一些特性，但是比HashMap的性能要好。

既然性能要好很多，那是不是所有可以用HashMap的地方都可以用SparseArray代替呢？也不尽然。SparseArray的value可以是任意类型，但它的key只能是Integer类型。如果key是Integer的话，用SparseArray还是很方便的，但是如果是string，那只能用HashMap了。

SparseArray 相关的还有SparseIntArray、SparseBooleanArray、LongSparseArray。下面都会做一下说明。

二、SparseArray 

/*** 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.** 
Note that this container keeps its mappings in an array data structure,* using a binary search to find keys.  The implementation is not intended to be appropriate for* data structures* that may contain large numbers of items.  It is generally slower than a traditional* HashMap, since lookups require a binary search and adds and removes require inserting* and deleting entries in the array.  For containers holding up to hundreds of items,* the performance difference is not significant, less than 50%.
** 
To help with performance, the container includes an optimization when removing* keys: instead of compacting its array immediately, it leaves the removed entry marked* as deleted.  The entry can then be re-used for the same key, or compacted later in* a single garbage collection step of all removed entries.  This garbage collection will* need to be performed at any time the array needs to be grown or the the map size or* entry values are retrieved.
** 
It is possible to iterate over the items in this container using* {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using* keyAt(int) with ascending values of the index will return the* keys in ascending order, or the values corresponding to the keys in ascending* order in the case of valueAt(int).
*/
public class SparseArray implements Cloneable {private static final Object DELETED = new Object();private boolean mGarbage = false;private int[] mKeys;private Object[] mValues;private int mSize;/*** Creates a new SparseArray containing no mappings.*/public SparseArray() {this(10);}

从字面的意思来看SparseArray指的是稀疏数组。从注释来看，用SparseArray 来替代java中的HashMap在性能上有更好的提高，定义的空间在delete的时候并没有释放，而是做了标记保留了下来，方便后来重复使用，直到特殊调用时候gc出来。另外就是查找的方式用的是binary search(折半查找)，这也是SparseArray 特殊之处，可以提高效率。

构造函数：

    public SparseArray() {this(10);}public SparseArray(int initialCapacity) {if (initialCapacity == 0) {mKeys = EmptyArray.INT;mValues = EmptyArray.OBJECT;} else {mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);mKeys = new int[mValues.length];}mSize = 0;}

默认是10个，当然里面都是空的。也可以指定数组的最小个数。

查找：

    public E get(int key) {return get(key, null);}@SuppressWarnings("unchecked")public E get(int key, E valueIfKeyNotFound) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i < 0 || mValues[i] == DELETED) {return valueIfKeyNotFound;} else {return (E) mValues[i];}}

不指定默认返回值的时候，返回的是null。

删除：

    public void delete(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {if (mValues[i] != DELETED) {mValues[i] = DELETED;mGarbage = true;}}}public void remove(int key) {delete(key);}public void removeAt(int index) {if (mValues[index] != DELETED) {mValues[index] = DELETED;mGarbage = true;}}public void removeAtRange(int index, int size) {final int end = Math.min(mSize, index + size);for (int i = index; i < end; i++) {removeAt(i);}}

删除方法提供了四个：

remove、delete是一个效果，参数都是key；

removeAt提供的却是value 的index；

removeAtRange删除的是一个范围，参数是value的index 和 偏移size；

注意：remove之后mGarbage都会被置为true，在适当的时候用于gc，gc完才能重置为false。

修改：

    public void put(int key, E value) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {mValues[i] = value;} else {i = ~i;if (i < mSize && mValues[i] == DELETED) {mKeys[i] = key;mValues[i] = value;return;}if (mGarbage && mSize >= mKeys.length) {gc();// Search again because indices may have changed.i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);}mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);mSize++;}}public void setValueAt(int index, E value) {if (mGarbage) {gc();}mValues[index] = value;}public void append(int key, E value) {if (mSize != 0 && key <= mKeys[mSize - 1]) {put(key, value);return;}if (mGarbage && mSize >= mKeys.length) {gc();}mKeys = GrowingArrayUtils.append(mKeys, mSize, key);mValues = GrowingArrayUtils.append(mValues, mSize, value);mSize++;}

修改提供了三个函数：

1）put 分为三种情况，一是数组已经有了，那就直接替换；二是数组中 value 之前被delete了，那就直接赋值；三是数组压根没出现过，用的是insert方式。

虽然这里insert可能影响到了效率，但是相对于binary search还是可以忽略的。

2）setValueAt 参数是values的index 和 value，个人感觉这里存在个漏洞，需要判断index 的存在性的。

3）append 参数换成了key 和 value，如果key 小于mKeys 最大的值，采用的是insert 方式，否则就用append在最后添加了。

SparseArray差不多的接口已经说的差不多了，来看一下几个核心的接口：

1、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;//除以2，无符号右移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}

在找不到的时候，返回的却是 ~lo，不是0也不是-1。

2、mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);

    public static  T[] insert(T[] array, int currentSize, int index, T element) {assert currentSize <= array.length;if (currentSize + 1 <= array.length) {System.arraycopy(array, index, array, index + 1, currentSize - index);array[index] = element;return array;}@SuppressWarnings("unchecked")T[] newArray = ArrayUtils.newUnpaddedArray((Class)array.getClass().getComponentType(),growSize(currentSize));System.arraycopy(array, 0, newArray, 0, index);newArray[index] = element;System.arraycopy(array, index, newArray, index + 1, array.length - index);return newArray;}

用的是System.arraycopy这里就不多解释了。

三、SparseIntArray

与SparseArray差不多，几个接口有点诧异。

1、构造函数

    public SparseIntArray(int initialCapacity) {if (initialCapacity == 0) {mKeys = EmptyArray.INT;mValues = EmptyArray.INT;} else {mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);mValues = new int[mKeys.length];}mSize = 0;}

SparseArray 是new 的mValues：

mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];

2、delete

    public void delete(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {removeAt(i);}}public void removeAt(int index) {System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));mSize--;}

直接删掉了，没有保留一说

3、没有了remove、removeAtRange、setValueAt等接口

四、SparseBooleanArray

与前面两个差不多，value是boolean 型

1、构造函数

    public SparseBooleanArray(int initialCapacity) {if (initialCapacity == 0) {mKeys = EmptyArray.INT;mValues = EmptyArray.BOOLEAN;} else {mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);mValues = new boolean[mKeys.length];}mSize = 0;}

2、delete

    public void delete(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1));System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1));mSize--;}}/** @hide */public void removeAt(int index) {System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));mSize--;}

其实完全可以跟SparseIntArray 一样，直接调用removeAt。

3、没有了remove、removeAtRange等接口，与SparseIntArray 比较多了setValueAt借口

五、LongSparseArray

public class LongSparseArray implements Cloneable {

个人感觉这个就是从SparseArray copy过来的接口，这里为什么要需要E？

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！