SparseArray

1、前言

SparseArray是android.util下的类，HashMap虽然增加、删除、查找的时间复杂度为O(1)级别的，但它是牺牲空间来换取时间的，而SparseArray占用的内存较小，比较适合移动端。

2、源码分析

//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;

    /**
     * Creates a new SparseArray containing no mappings.
     */
    public SparseArray() {
        //默认容量是10个元素
        this(10);
    }

    /**
     * Creates a new SparseArray containing no mappings that will not
     * require any additional memory allocation to store the specified
     * number of mappings.  If you supply an initial capacity of 0, the
     * sparse array will be initialized with a light-weight representation
     * not requiring any additional array allocations.
     */
    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;
    }

    /**
     * Gets the Object mapped from the specified key, or <code>null</code>
     * if no such mapping has been made.
     */
    /**
     * 获得指定key的映射对象，或者null如果没有该映射。
     */
    public E get(int key) {
        return get(key, null);
    }

    /**
     * Gets the Object mapped from the specified key, or the specified Object
     * if no such mapping has been made.
     */
    @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];
        }
    }

       /**
     * Alias for {@link #delete(int)}.
     */
    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);
    }

    /**
     * Adds a mapping from the specified key to the specified value,
     * replacing the previous mapping from the specified key if there
     * was one.
     */
    /**
     * 添加一个指定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;
    }

}

3、SparseArray性能

• 1、SparseArray内部使用int[] keys数组维护key，而且keys中元素是按照升序进行排序的，使用Object[] values来维护value。
• 2 SparseArray用于映射integers到object。但不像普通数组，SparseArray元素间没有无用的元素。在映射integers到object的过程中，SparseArray采用避免自动装箱的keys而且它的数据结构不依赖于额外的对象来存储映射关系的实现，因此它相比于HashMap占用更少的内存。
• 3、但是SparseArray在查找keys的过程中使用了二分法查找，这种实现不适合大量的数据的情况。在添加和删除时涉及到数组元素的挪动，因此比HashMap慢。
• 4、为了优化性能，SparseArray对remove()进行了优化，在删除时并没有立即挤压数组的空间，而是标记为DELETE。被标记为DELETE的元素，要么被重复利用，要么在多次remove后，通过一次gc操作，进行数组空间的挤压。