SparseArray
在Android中,SparseArray是一个专门用于存储稀疏数据(大部分元素为null或默认值)的数组类。常用于存储与整数键关联的对象,其中键是原始数据类型 int,而不是对象类型 Integer。使得 SparseArray 在内存使用上比使用 HashMap<Integer, E> 更高效,因为避免了自动装箱(autoboxing)和拆箱(unboxing)的开销。
//E对应HashMap的Value public class SparseArray<E> implements Cloneable { // 用来优化删除性能(当有元素被remove delete时),标记已经删除的对象为DELETE private static final Object DELETED = new Object(); // 用来优化删除性能,标记是否需要垃圾回收 private boolean mGarbage = false; // 存储索引,整数索引(key为整数)从小到大被映射在该数组 private int[] mKeys; // 存储对象(Value) private Object[] mValues; // SparseArray实际大小 private int mSize; public SparseArray() { //默认容量是10个元素 this(10); } public SparseArray(int initialCapacity) { if (initialCapacity == 0) { //mKeys的初值等于new int[0],mValues的初值等于new Object[0] mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { //newUnpaddedObjectArray最后指向了VMRuntime的一个native方法,返回一个至少长initialCapacity的数组, mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } mSize = 0; } /** * 获得指定key的映射对象,或者null如果没有该映射。 */ 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); // 如果没找到或者该value已经被标记删除,则返回默认值 if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { // i>0 且该位置的元素未被标记为待删除,返回该值mValues[i] return (E) mValues[i]; } } public void remove(int key) { //调用delete执行删除操作 delete(key); } /** * Removes the mapping from the specified key, if there was any. */ /** * 删除指定key的映射对象。 */ public void delete(int key) { //二分查找 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //找到了 if (i >= 0) { //若未被标记delete,标记为delete,回收mGarbage=true if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } } //目的只有一个压缩空间(压缩数组,把无效的值删除) private void gc() { // Log.e("SparseArray", "gc start with " + mSize); int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; //循环整个元素区间,删除值为DELETED的数,这里比较巧妙,直接对同一个keys和values操作,完成元素的删除和移动! for (int i = 0; i < n; i++) { Object val = values[i]; if (val != DELETED) { if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o;//实际大小 // Log.e("SparseArray", "gc end with " + mSize); } /** * 添加一个指定key到指定object的映射,如果之前有一个指定key的映射则直接替换掉原映射object。注意gc。 */ public void put(int key, E value) { //先二分查找,确定插入位置,保证了key数组的有序性 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { //找到了,直接替换 mValues[i] = value; } else { // 做一个取反运算,获得应该插入的index //没找到的情况下: i = -insertPoint -1,对他取反刚好得insertPoint。 i = ~i; //若i在size范围内,且刚好对应位置标记为delete了,直接放入 if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } //若前面if不成立,即i超出了size范围,或者对应的位置的元素是有效的 // 如果被标记为需要垃圾回收且SparseArray大小不小于keys数组长度 if (mGarbage && mSize >= mKeys.length) { // 压缩空间,会压缩数组,把无效的值都去掉,保证连续有效值 gc(); // Search again because indices may have changed. // 再次查找插入点因为索引可能改变 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } // 插入,如果size不够则会重新分配更大的数组,然后拷贝过去并插入;size足够则用System.arraycopy把插入位置开始的value都后移然后插入 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); // 实际大小加1 mSize++; } } /** * Returns the number of key-value mappings that this SparseArray * currently stores. */ //返回mSize,注意gc。 public int size() { if (mGarbage) { gc(); } return mSize; } }
SparseArray方法:
- put(int key, E value):向数组中放入一个值。
- get(int key):根据键获取值。
- delete(int key):根据键删除值。
- size():返回数组中当前存储的键值对的数量。
- keyAt(int index):根据索引返回键。
- valueAt(int index):根据索引返回值。
- indexOfKey(int key):返回指定键的索引。
- indexOfValue(E value):返回指定值的索引。
SparseArray在处理稀疏数据时非常有效,如果数据结构不是稀疏的,或者需要存储的键不是整数类型,那么使用HashMap或其他数据结构可能更合适。
例如,在自定义视图中处理大量子视图时,可能会使用SparseArray来存储与每个子视图ID关联的视图对象。
SparseArray性能
- SparseArray内部使用int[] keys数组维护key,而且keys中元素是按照升序进行排序的,使用Object[] values来维护value。
- SparseArray用于映射integers到object。但不像普通数组,SparseArray元素间没有无用的元素。在映射integers到object的过程中,SparseArray采用避免自动装箱的keys而且它的数据结构不依赖于额外的对象来存储映射关系的实现,因此它相比于HashMap占用更少的内存。
- 但是SparseArray在查找keys的过程中使用了二分法查找,这种实现不适合大量的数据的情况。在添加和删除时涉及到数组元素的挪动,因此比HashMap慢。
- 为了优化性能,SparseArray对remove()进行了优化,在删除时并没有立即挤压数组的空间,而是标记为DELETE。被标记为DELETE的元素,要么被重复利用,要么在多次remove后,通过一次gc操作,进行数组空间的挤压。
原文地址:https://mp.weixin.qq.com/s/2BIFp186gTU-5IsggRxvqA