Android之SparseArray 源码解析

前言

SparseArray是安卓特有的一种数据结构，跟HashMap相似，都是存储<Key,Value>的实体。但是SparseArray的Key只能是Int类型的。在存储的时候Key按照顺序进行了排序，当查询的时候采用了二分查找法来定位位置。这种方式相对来说更加迅速

变量

private boolean mGarbage = false;//是否可以进行回收，也就是进行key，value的整理

private int[] mKeys;//存储的key值

private Object[] mValues;//存储的value值

private int mSize; //数组的大小

可以看到，对于key和value的存储，是分别存储在两个不同的数组中的。而且key的类型是int，而不是封装后的Integer。

这里面有个 mGarbage 变量，它标志着我们当前的数据是否可以进行数据的整理工作。比如说，当我们移除某个key以后，会将这个标志位设置为true，在需要的时候（比如说我们要进行数据的存储），会根据这个标志位进行一次数组的整理工作。

构造函数

public SparseArray() {
    //默认数组的大小是10
    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;
}

从构造函数可以看出来，SparseArray的数组 默认大小是10 ，如果我们在实际的使用过程中能够确定要保存的数据量的大小，最好直接初始化，这样就不会出现扩容的问题。

源码分析

添加元素

既然和HashMap相似，那么肯定是有数据的增删改的

    public void put(int key, E value) {
        //通过ContainerHelpers进行二分查找。如果存在则返回key的位置
        // 如果不存在则返回key在数组中可以存储的位置i的负值。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果key已经存在，则直接赋值
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //binarySearch 方法的返回值分为两种情况：
            //1、如果存在对应的 key，则直接返回对应的索引值
            //2、如果不存在对应的 key
            //  2.1、假设 mKeys 中存在"值比 key 大且大小与 key 最接近的值的索引"为 presentIndex，则此方法的返回值为 ~presentIndex
            //  2.2、如果 mKeys 中不存在比 key 还要大的值的话，则返回值为 ~mKeys.length
            //可以看到，即使在 mKeys 中不存在目标 key，但其返回值也指向了应该让 key 存入的位置
            //通过将计算出的索引值进行 ~ 运算，则返回值一定是 0 或者负数，从而与“找得到目标key的情况（返回值大于0）”的情况区分开
            //且通过这种方式来存放数据，可以使得 mKeys 的内部值一直是按照值递增的方式来排序的
            i = ~i;
            //如果搜索到的i位置可以使用，并且没有数据，则将对应的key，value存入到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.
                //GC 后再次进行查找，因为值可能已经发生变化了
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //通过复制或者扩容数组，将数据存放到数组中
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

这里有个辅助类 ContainerHelpers ，它的 binarySearch 方法会根据实际情况返回key所对应的位置值

如果mKeys数组中存在key，那么直接返回key所对应的索引值
如果mKeys中不存在key
- key比mKeys中的所有的数据都大，则返回~mKeys.length
- key处于mKeys中的某个中间位置，则返回那个值比 key 大且大小与 key 最接近的值的索引。

可以看到，哪怕key在数组中不存在， binarySearch ，也会将key保存的最佳位置给返回回来。

当key的位置确定以后，会根据情况进行数组的重新编排，重新编排的话，当前的key和value在数组中的位置就会发生变化，所以会调用 binarySearch 重新获取适合的插入位置。

最后调用 GrowingArrayUtils.insert 方法进行数据的插入。

这个方法会判断当前的数组大小是否能够继续插入key，如果不可以的话，会进行扩容。如果可以，会将i位置以后的数据往后移动一位，然后将i位置插入我们的key值。

移除元素

移除元素的函数有多个，我们一个个来看。

    public void remove(int key) {
        delete(key);
    }
    public void delete(int key) {
        //通过二分查找，获取key所在位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            //将所在位置的value设置为DELETED,然后标记需要进行整理。
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
    public E removeReturnOld(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            //如果key所在的index的值不为DELETED，则返回数据，并标记对应index的值为DELETED，
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
    //删除指定索引对应的元素值
    public void removeAt(int index) {
        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

可以看到，不管哪种remove方法。实际的移除操作，只是把key所在的位置的value值设置为了 DELETED ，然后设置了 mGrabage 标志位。并没有进行key数组和value数组的移动操作。

查找元素

    public E get(int key) {
        return get(key, null);
    }

    //获取指定key的值，如果获取不到，则返回指定对象。
    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        //获取key对应的index位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果不存在，或者i位置的数据已经回收了，则直接返回
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }
    public E valueAt(int index) {
        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (mGarbage) {
            gc();
        }
        return (E) mValues[index];
    }
    //根据value值，获取其对应的index信息
    public int indexOfValue(E value) {
        if (mGarbage) {
            gc();
        }
        for (int i = 0; i < mSize; i++) {
            if (mValues[i] == value) {
                return i;
            }
        }
        return -1;
    }

查找方法有的返回的是key所对应的的信息，有的是获取index信息。这里面进行了区分操作。因为如果只是根据key值获取value值的话，不需要进行数组的整理工作。而一旦涉及到了index的查找工作，那么就需要根据 mGrabage 先进行一次整理工作，然后才能进行index的相关处理。

垃圾回收

SparseArray的垃圾回收并不是我们平时所理解的JVM的垃圾回收，只是因为当我们进行移除value的情况下，并没有进行数据的移除，只是设置了 mGrabage ，而且将对应位置的value设置为了 DELETED 来表示当前位置是可以回收的。所以当我们需要适应索引时，就会出现索引无效的问题。所以需要通过垃圾回收来进行数组的整理，将数组整理为连续的数据。

    //用于移除无用的引用，通过移动，将现在所有的key和value连续保存到数组中，而不会使某个位置的value为空
    //而且会将mSize赋值为实际使用的大小
    private void gc() {
        int n = mSize;
        //o 值用于表示 GC 后的元素个数
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            //如果value不是DELETED，证明当前的位置数据是可用的
            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
                o++;
            }
        }
        mGarbage = false;
        mSize = o;
    }

优劣

优势

使用int类型作为key，避免了装箱拆箱操作
延迟了垃圾回收时机，只在需要的时候才进行一次回收
和Map每个存储节点都是一个类对象不同，SparseArray不需要用于包装的结构体，单个元素存储成本更低廉
在小数据量下，二分查找效率更高一些。

劣势

插入新元素会导致大量的数组移动
数据量较大时，二分查找效率会变低

本文由开了肯发布！

同步公众号[开了肯]