SparseArray

参考 Java&Android 基础知识梳理(10) - SparseArray 源码解析

这个类比较简单，解析源码的思路为：先看注释，了解设计初衷，然后从我们平时使用的接口入手查看实现，最后再来验证下设计初衷。

1. 类的注释讲解：

/**
 * 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.
 *
 * <p>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%.</p>
 *
 * <p>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.</p>
 *
 * <p>It is possible to iterate over the items in this container using
 * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
 * <code>keyAt(int)</code> 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 <code>valueAt(int)</code>.</p>
 */

• spaseArray是一个int到object的映射， 设计初衷是在某些情形下比hashmap更有效率，以替代hashmap； 效率体现在：无需自动装包(keys)； 映射很直接，不像hashmap一样依赖其他的存储结构（比如链表）；
• keys直接存在在数组中，二分法查找（因此需保证有序），不适合keys较多的情况，为什么呢：二分法查找的时间复杂度问题+增删数据对数组结构不友好，效率较低；
• sparsearray为了提高效率做了个优化：删除数据时，把对应的value对象设置为deleted对象，不会真正删除，以备后续复用； 当然，在数组增加等一些操作时垃圾回收期(gc)会触发工作；
• 支持遍历

从这里我们了解到：

• keys是一个int数组，values是对象数组，方便！
• keys直接存储key值，二分法查找，因此它是有序的
• values 删除并不是真正的删除，只有gc后才会删除，但删除只是删除values，keys并不受影响（因为无所谓）
• 使用场景：数据量不大的情况下hashmap更有效率，而数据量大了后为什么不行了呢？ 面试要点，自己看注释~~~

2. 我们常用的接口
   我们无非用的是增删查改，开始之前看下存储用的常量吧

private static final Object DELETED = new Object();//标记value已删除，方便复用
private boolean mGarbage = false;//是否要gc
private int[] mKeys;// key的存储
private Object[] mValues; //value的存储
private int mSize; //实际value中有效的值大小~~

二分法实现：这里查看

• 增

 public void put(int key, E value) {
       //二分法找key：实现见上面
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {    //找到
            mValues[i] = value;
        } else {       
            i = ~i;
             //未找到，尝试下可否复用未删除的value空间
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
           // gc  注意：mSize >= mKeys.length
            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++;
        }
    }

• 删
  比较简单，设置deleted标记, 后续会考虑复用或gc

    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 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];
        }
    }

• 改

   public void setValueAt(int index, E value) {
       if (mGarbage) {
           gc();
       }

       mValues[index] = value;
   }

---

其实原理都不难理解，关键是gc是什么时机触发的，怎么进行的，插入数据是怎么进行的？下面重点看下

• gc
  触发条件：

在增加数据时判断条件，符合则触发
if (mGarbage && mSize >= mKeys.length)

在 查询key下标，value下标，设置值，求size()时判断条件
if (mGarbage)

怎么进行：

设置o=0，来重新计算有效数值

过滤条件：！=deleted的且o！=i，则赋值覆盖

o的值就是size()，表示values有效的值，注意values无需的值会置为null，但keys不会

private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        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);
    }

• 数组怎么插入一个值的
  见这里

3. 现在重读下类的注释，很多问题都有答案了
   sparseArray很轻便，需要在一定的情形下使用可大大提高效率！