SparseArray详解及源码简析

一、前言

SparseArray 是 Android 在 Android SdK 为我们提供的一个基础的数据结构，其功能类似于 HashMap。与 HashMap 不同的是它的 Key 只能是 int 值，不能是其他的类型。

二、代码分析

1. demo 及其简析

首先也还是先通过 demo 来看一看 SparseArray 的基本使用方法，主要就是插入方法以及遍历方法。这也会后面的代码分析打下一个基础。

        SparseArray<Object> sparseArray = new SparseArray<>();
        sparseArray.put(0,null);
        sparseArray.put(1,"fsdfd");
        sparseArray.put(2,new String("fjdslfjdk"));
        sparseArray.put(3,1);
        sparseArray.put(4,new Boolean(true));
        sparseArray.put(5,new Object());
        sparseArray.put(8,new String("42fsjfldk"));
        sparseArray.put(20,"jfslfjdkfj");
        sparseArray.put(0,"chongfude");

        int size = sparseArray.size();
        for (int i = 0;i < size;i++) {
            Log.d(TAG, "sparseArraySample: i = " + i + ";value = " + sparseArray.get(sparseArray.keyAt(i)) );
        }

上面代码先是 new 了一个 SparseArray，注意声明时只能指定 value 的类型，而 key 是固定为 int 的。然后再往里面添加 key 以及 value。这里注意一下的是 key 为 0 的情况插入了 2 次。遍历时，是先通过顺序的下标取出 key ，再通过 keyAt 来 get 出 value。当然也可以一步到位通过 valueAt() 直接获取到 value。然后这个 demo 的执行结果如下。

sparseArraySample: i = 0;value = chongfude
sparseArraySample: i = 1;value = fsdfd
sparseArraySample: i = 2;value = fjdslfjdk
sparseArraySample: i = 3;value = 1
sparseArraySample: i = 4;value = true
sparseArraySample: i = 5;value = java.lang.Object@b67a0fa
sparseArraySample: i = 6;value = 42fsjfldk
sparseArraySample: i = 7;value = jfslfjdkfj

然后通过 Debug 来看一看在内存中，SparseArray 实际是如何存储的。如下图分别是 key 与 value 在内存中的形式。可以看出 keys 和 values 的大小都为 13，而且 keys 的值是按从小到大顺序排列的。

keys

values

2.源码分析

下面是 SparseArray 的类图结构，可以看到其属性非常的少，也可以看出其分别用了数组 int[] 和 object[] 来存储 key 以及 value。

SparseArray.jpg

SparseArray 初始化
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;
    }

其有 2 个构造方法，带参与不带参。当然，这个参数就是指定数组初始大小，也就是 SparseArray 的初始容量。而不带参数则默认指定数组大小为 10 个。

插入数据 put() 方法

public void put(int key, E value) {
        // 1.先进行二分查找
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 2. 如果找到了，则 i 必大于等于 0
        if (i >= 0) {
            mValues[i] = value;
        } else {
        // 3. 没找到，则找一个正确的位置再插入
            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++;
        }
    }

这里调用了很多外部的方法以及内部的方法。首先是 ContainerHelpers#binarySearch() 的二分查找算法。

    //This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        while (lo <= hi) {
            // 高位+低位之各除以 2，写成右移，即通过位运算替代除法以提高运算效率
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        //若没找到，则lo是value应该插入的位置，是一个正数。对这个正数去反，返回负数回去
        return ~lo;  // value not present
    }

二分查找的分析属于基础内容，在注释中了。回到 put() 方法首先通过二分查找算法从当前 keys 中查找是否已经存在相同的 key 了，如果存在则会返回大于等于 0 的下标，然后接下来就会将原下标下的 values 中的旧value 替换成新的 value 值，即发生了覆盖。

那如果没有找到，那么将 i 取反就是要插入的位置了，这一结论正好来自 binarySearch() 的返回结果。可以看到其最后如果没有找到的话，就会返回 lo 的取反数。那么这里再把它取反过来那就是 lo 了。

这里如果 i 是在大小 mSizes 的范围内的，且其对应的 values[i] 又刚是被标记为删除的对象，那么就可以复用这个对象，否则就还是要依当前的 i 值进一步寻找要插入的位置，再插入相应的 value。

在插入之前，如果由于之前进行过 delete()，remoeAt() 以及 removeReturnOld() 中的某一个方法，那就可能要进行 gc() 操作。当然，这里不是指的内存的 gc()。

private void gc() {
        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;
    }

通过代码很容易分析得出，这里的 gc ，实际就是压缩存储，简单点说就是让元素挨得紧一点。

而 gc() 完之后，下标 i 可能会发生变化，因此需要重新查找一次，以得到一个新的下标 i。

最后就是通过 GrowingArrayUtils.insert() 来进行 key 和 value 的插入。这个 insert() 根据数组类型重载了多个，这里只分析 int[] 类型的即可。

public static int[] insert(int[] array, int currentSize, int index, int element) {
        //确认 当前集合长度 小于等于 array数组长度
        assert currentSize <= array.length;
        //不需要扩容
        if (currentSize + 1 <= array.length) {
            //将array数组内从 index 移到 index + 1，共移了 currentSize - index 个，即从index开始后移一位，那么就留出 index 的位置来插入新的值。
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            //在index处插入新的值
            array[index] = element;
            return array;
        }
        //需要扩容，构建新的数组，新的数组大小由growSize() 计算得到
        int[] newArray = new int[growSize(currentSize)];
        //这里再分 3 段赋值。首先将原数组中 index 之前的数据复制到新数组中
        System.arraycopy(array, 0, newArray, 0, index);
        //然后在index处插入新的值
        newArray[index] = element;
        //最后将原数组中 index 及其之后的数据赋值到新数组中
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

上面的算法中，如果不需要扩容则直接进行移位以留出空位来插入新的值，如果需要扩容则先扩容，然后根据要插入的位置 index，分三段数据复制到新的数组中。这里再看看 growSize() 是如何进行扩容 size 的计算的。

    public static int growSize(int currentSize) {
        //如果当前size 小于等于4，则返回8， 否则返回当前size的两倍
        return currentSize <= 4 ? 8 : currentSize * 2;
    }

代码相对简单，当前 size 小于等于 4 则为 8 ，否则为 2 倍大小。

get() 方法

    public E get(int key) {
        return get(key, null);
    }
    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];
        }
    }

get() 方法就是通过 key 来返回对应的 value，前面在分析 put() 的时候已经分析过了二分查找。那么这里如果找到了，就会通过下标直接从 mValues[] 中返回。

delete() 方法

public void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

delete() 也非常简单，通过二分查找算法定位到下标，然后将对应的 value 标记为 DELETE，并且标记需要进行 gc 了。这里需要注意的是被标记为 DELETE 的 value 不会在 gc 中被移除掉，而只会被覆盖掉，从而提高了插入的效率。

三、总结

文章对 SparseArray 进行了简要的分析，文章也只对主要的几个方法进行了分析，其他没有分析到的方法在这个基础上再进行分析相信也是很简单的。而总结下来几点是：

其内部主要通过 2 个数组来存储 key 和 value，分别是 int[] 和 Object[]。这也限定了其 key 只能为 int 类型，且 key 不能重复，否则会发生覆盖。
一切操作都是基于二分查找算法，将 key 以升序的方法 “紧凑” 的排列在一起，从而提高内存的利用率以及访问的效率。相比较 HashMap 而言，这是典型的时间换空间的策略。
删除操作并不是真的删除，而只是标记为 DELETE，以便下次能够直接复用。

最后，感谢你能读到并读完此文章。受限于作者水平有限，如果存在错误或者疑问都欢迎留言讨论。如果我的分享能够帮助到你，也请记得帮忙点个赞吧，鼓励我继续写下去，谢谢。