SparseArray源码分析

类似于Map中存放键值对, 只不过key存放在使用int数组中,而value存放在Object数组中;
核心思想: 采用二分法查询key对应的位置,然后取出值或者插入值

put方法
1.采用二分法查找,获取key在mKeys数组的下标 i
2.如果i >= 0, 说明key在mKeys数组已存在, mValues[i] = value
3.如果i < 0, 说明key在mKeys数组中不存在, i = ~i 按位取反, i 为要添加的元素在数组中的下标
3.1 mValues[i] == DELETED, 表示下标 i 位置的元素有移除过, 如果新添加的元素也是下标 i,mKey[i]和mValues[i] 重新赋值
3.2 mValues[i] != DELETED, 如果mKeys数组中还有元素未赋值, 可能会偏移mKeys数组和mValues数组中的元素; 如果mKeys数组中的元素都赋值过了,对mKeys数组和mValues数组进行扩容,并偏移mKeys数组和mValues数组中的元素.最后都会将key和value分别赋值给mKey[i]和mValues[i];

    public void put(int key, E value) {

        /**
         * 采用二分法查找key,返回的是key在在mKeys数组的下标
         */
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        //1.mKeys中包含key,value替换
        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~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);
            }

            //添加元素 2.mKeys中不包含key,并且mKeys中元素没有添加满,添加元素;3.mKeys中不包含key,并且mKeys中元素添加满了,扩容,并添加元素
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

get方法
采用二分法查找,获取key在mKeys数组的下标 i,并返回 i

通过反射,查看添加元素后的变化情况

SparseArray<String> sparseArray = new SparseArray<>(3);
sparseArray.put(5, "wislie");
sparseArray.put(1, "kotlin");
sparseArray.put(1, "java");
sparseArray.put(9, "python");
sparseArray.put(6, "react");
sparseArray.put(4, "flutter");
//打印结果
keys:[5, 0, 0] values:[wislie, null, null] size:1 isGarbage:false
keys:[1, 5, 0] values:[kotlin, wislie, null] size:2 isGarbage:false
keys:[1, 5, 0] values:[java, wislie, null] size:2 isGarbage:false
keys:[1, 5, 9] values:[java, wislie, python] size:3 isGarbage:false
keys:[1, 5, 6, 9, 0, 0, 0, 0, 0] values:[java, wislie, react, python, null, null, null, null, null] size:4 isGarbage:false
keys:[1, 4, 5, 6, 9, 0, 0, 0, 0] values:[java, flutter, wislie, react, python, null, null, null, null] size:5 isGarbage:false 

优点
1.使用二分法, key以升序的方式排列, 提升了内存的利用率及访问效率
2.使用int数组存储int类型的key，避免了int到Integer的自动装箱机制

使用场景
元素个数少于1000, 增删不频繁, key是整型