SparseIntArray原理分析

系列文章地址：
Android容器类-ArraySet原理解析(一)
Android容器类-ArrayMap原理解析(二)
Android容器类-SparseArray原理解析(三)
Android容器类-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）时，查找效率较低
• 在进行元素的添加和删除时，可能会频繁进行元素的移动，运行效率可能会降低

关注微信公众号，最新技术干货实时推送

image src="" width="300"