SparseIntArray原理分析

SparseArray 优化了 int 到 Object 键值对的存储， SparseIntArray 优化了 int 到 int 键值对的存储。android中在键值对存储上的优化主要做了一下几种类型的优化:

• int --> Object (SparseArray)
• int --> int (SparseIntArray)
• int --> boolean (SparseBooleanArray)
• int --> long (SparseLongArray)
• int --> Set (SparseSetArray)

SparseSetArray目前在sdk中还处于hide状态，故在做总结的时候就不分析它了。

之前已经分析过 SparseArray ，本文就分析下 SparseIntArray 的实现，并在最后总结下这几种键值对在实现上的共同点。

继承结构

以上为 SparseIntArray 的继承体系。 SparseIntArray 只实现了 Cloneable 接口，结构比较简单。其实阅读源码可以发现， SparseArray ， SparseIntArray ， SparseBooleanArray ， SparseLongArray 都只实现了 Cloneable 接口。

存储结构

以上为 SparseIntArray 的存储结构，mKeys存储的是int类型的键，mValues存储的是int类型的value。

查找元素

// 查找键key在mKeys的下标
    public int indexOfKey(int key) {
        return ContainerHelpers.binarySearch(mKeys, mSize, key);
    }
    
    // 查找value在mValues的下标
    public int indexOfValue(int value) {
        for (int i = 0; i < mSize; i++)
            if (mValues[i] == value)
                return i;
        return -1;
    }
复制代码

元素的查找分键查找和值查找，键查找使用二分查找，值查找直接使用循环遍历。

添加元素

public void put(int key, int value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~i;

            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }
复制代码

添加元素首先使用二分查找找到key在mKeys数组的下标，也就是value在mValues数组的下标。如果 ContainerHelpers.binarySearch(mKeys,mSize,key) 在mKeys数组中没有找到key，则返回key待插入位置的下标的取反，如果找到了key，则直接更新mValues对应位置的值即可。 GrowingArrayUtils.insert 函数的实现如下：

public static int[] insert(int[] array, int currentSize, int index, int element) {
        assert currentSize <= array.length;
    
        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
    
        int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }
复制代码

函数的逻辑很简单，首先断言了currentSize <= array.length；如果array在不需要扩大容量的情况下可以添加一个元素，则先将待插入位置index开始的元素整体后移一位，然后插入元素，否则先扩容，然后将元素拷贝到新的数组中。

删除元素

public void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            removeAt(i);
        }
    }
    
    public void removeAt(int index) {
        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
        mSize--;
    }
复制代码

删除元素主要涉及以上两个方法， delete(int key) 根据 key 进行删除， removeAt(int index) 删除指定下标的元素。这两个方法都是 public ，故都可以直接使用。 delete(int key) ，先使用二分查找，找到 key 在 mKeys 的下标，如果找到即 i >= 0 ，则直接删除 mKeys 和 mValues 指定位置的元素。

总结

SparseBooleanArray , SparseLongArray 还没有分析，他们的实现规则是一样的，只是存储的数据类型的 mValues 数组是 boolean 和 long ，接下来就对 SparseIntArray , SparseBooleanArray , SparseLongArray 进行下总结。

• 他们的设计目的是优化 int 到 int , boolean , long 映射的存储
• 使用 int 类型的数组 mKeys 存储映射的键，使用对应类型的数组 mValues 存储值
• int 类型的键在存储上是有顺序的
• 在查找值时，先使用二分查找，在 mKeys 中查找值在 mValues 中的下标，然后返回值

以上三种数据类型和 SparseArray 最大的区别在于 SparseArray 在删除元素的时候会将元素设置为 DELETED ，后续会有 gc 的过程。

相对于使用HashMap，这样的设计的优势和缺点：

优势：

• 避免 int 类型的键自动装箱
• 相较于 HashMap 使用 Node ，这样的设计使用更小的存储单元即可存储 key 到 value 的映射

缺点：

• 在进行元素查找时使用二分查找，元素较多（谷歌给出的数字是大于1000）时，查找效率较低
• 在进行元素的添加和删除时，可能会频繁进行元素的移动，运行效率可能会降低