SparseArray源码解析

冷不防 2023-10-13 12:55 14阅读 0赞

#### 一、数据结构 ####

SparseArray的数据结构很简单，有mKeys、mValues两个数组，key和value的位置是一一对应的，且key是按照从小到大的顺序的排列的。

![e18a92c912d342ff98363afa00e5acd4.png][]

#### 二、源码解析 ####

**1、成员变量**

//当某个key被删除时，对应的value会置为DELETED
        private static final Object DELETED = new Object();
    
        //是否触发gc，重新整理mKeys、mValues的标志
        private boolean mGarbage = false;
    
        //存放key的数组
        private int[] mKeys;
    
        //存放value的数组
        private Object[] mValues;
    
        
        private int mSize;

**2、构造方法**

public SparseArray() {
             this(10);
        }
    
    
        public SparseArray(int initialCapacity) {
            if (initialCapacity == 0) {//如果初始容量为0，那么mKeys和mValues都赋值为空数组
                mKeys = EmptyArray.INT;
                mValues = EmptyArray.OBJECT;
            } else {//否则，创建指定容量的数组。
                mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
                mKeys = new int[mValues.length];
            }
            mSize = 0;
        }

由此可见，SparseArray的默认初始容量是10。

**3、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];
        }
    }

`ContainerHelpers`是一个工具类，`binarySearch()`表示[二分查找][Link 1]

static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        while (lo <= hi) {
            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
            }
        }
        return ~lo;  // value not present
    }

*注：这里binarySearch方法有两个作用，看binarySearch方法的返回值就可以知道，如果找到就返回对应的索引，如果没找到就返回lo的位非结果。这样做两个好处：*

*（1）返回结果为正数，表示可以查找到，返回的值即为对应的位置*

*（2）返回结果为负数，表示查找不到，但是对结果取反，得到元素待插入的位置，对put()操作可以避免再次查找。*

**4、put方法**

public void put(int key, E value) {
            int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
            if (i >= 0) {//查找得到，为对应位置，直接给对应位置赋值
                mValues[i] = value;
            } else {//如果查找不到，~i为元素待插入的位置
                i = ~i;
    
                if (i < mSize && mValues[i] == DELETED) {
                    //如果刚好待插入的位置是被delete掉的，直接赋值
                    mKeys[i] = key;
                    mValues[i] = value;
                    return;
                }
                
                //mGarbage 表示需要gc
    
                if (mGarbage && mSize >= mKeys.length) {
                    gc();//进行gc
    
                    // Search again because indices may have changed.
                    //重新获取一次待插入的位置（因为经过上面的gc之后，元素的位置发生了变化，所以需要重新查找一次，得到最新的索引）
                    i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
                }
                //插入到目标位置key、value
    
                mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
                mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
                mSize++;
            }
        }

注意：这里调用了GrowingArrayUtils.insert方法来把元素插入到数组中，我们来看一下这个方法：

public static int[] insert(int[] array, int currentSize, int index, int element) {
            if (currentSize + 1 <= array.length) {
                System.arraycopy(array, index, array, index + 1, currentSize - index);
                array[index] = element;
                return array;
            }
    
            int[] newArray = new int[growSize(currentSize)];
            System.arraycopy(array, 0, newArray, 0, index);
            newArray[index] = element;
            System.arraycopy(array, index, newArray, index + 1, array.length - index);
            return newArray;
        }

可以看到这里在插入之前判断了数组是否需要扩容，如果需要扩容就会调用growSize方法进行扩容：

public static int growSize(int currentSize) {
            return currentSize <= 4 ? 8 : currentSize * 2;
        }

从这里我们可以看出，***SparseArray的扩容机制：***

***如果当前大小<=4,经扩容之后变为8；***

***如果当前大小>4,经扩容之后变为之前的2倍。***

mGarbage表示需要进行gc()动作，那mGarbage是在哪里设置的呢？答案是在remove移除键值对的时候，就会设置mGarbage=true

public void delete(int key) {
            int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
            if (i >= 0) {
                if (mValues[i] != DELETED) {
                    mValues[i] = DELETED;
                    mGarbage = true; // 设置需要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不是JVM的GC，指的是从头遍历一遍，让后面的元素向前移动，覆盖掉原有的value为DELETED的元素。

**5、append方法**

和put方法类似，但在存入数据前先对数据大小进行了判断，有利于减少对mKeys进行二分查找的次数，所以“存入的key 比现有的 mKeys 值都大”的情况下会比put方法性能高（省去了二分查找）

public void append(int key, E value) {
            if (mSize != 0 && key <= mKeys[mSize - 1]) {
                put(key, value);
                return;
            }
    
            if (mGarbage && mSize >= mKeys.length) {
                gc();
            }
    
            mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
            mValues = GrowingArrayUtils.append(mValues, mSize, value);
            mSize++;
        }

#### 三、总结 ####

**优点：**

*  SparseArray 避免了基本数据类型的装箱和拆箱操作 ，从而避免key自动装箱产生过多的Object
 *  采用了延迟删除的机制，通过将删除的KEY的value设置为DELETED，方便之后对该下标的存储进行复用
 *  数据量较小的情况下，随机访问的效率更高
 *  不需要创建额外的Entry对象，单个元素的存储成本更低

**缺点：**

*  插入新元素可能会导致移动大量的数组元素，因为SparseArray查找数据时候使用的是二分法，明显比通过hashcode慢，所以数据量越大，查找速度慢的劣势越明显，所以SparseArray适用于数据一千以内的场景中
 *  数据量巨大时，复制数组成本巨大，gc()成本也巨大，且查询效率也会明显下降

**使用场景：**

*  key为整型，数据量较小的场景（一般不超过1000）

[e18a92c912d342ff98363afa00e5acd4.png]: https://img-blog.csdnimg.cn/e18a92c912d342ff98363afa00e5acd4.png
[Link 1]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE&spm=1001.2101.3001.7020