阅读 768

SparseIntArray原理分析

系列文章地址:
Android容器类-ArraySet原理解析(一)
Android容器类-ArrayMap原理解析(二)
Android容器类-SparseArray原理解析(三)
Android容器类-SparseIntArray原理解析(四)

SparseArray优化了intObject键值对的存储,SparseIntArray优化了intint键值对的存储。android中在键值对存储上的优化主要做了一下几种类型的优化:

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

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

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

继承结构

继承结构

以上为SparseIntArray的继承体系。SparseIntArray只实现了Cloneable接口,结构比较简单。其实阅读源码可以发现,SparseArraySparseIntArraySparseBooleanArraySparseLongArray都只实现了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),先使用二分查找,找到keymKeys的下标,如果找到即i >= 0,则直接删除mKeysmValues指定位置的元素。

总结

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

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

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

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

优势:

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

缺点:

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

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

image src=

关注下面的标签,发现更多相似文章
评论