最近在整顿SparseArray这一知识点的时候，发现网上大多数SparseArray原理剖析的文章都存在很多问题（能够说很多作者并没有读懂SparseArray的源码），也正因而，才有了这篇文章。咱们晓得，SparseArray与ArrayMap是Android中高效存储K-V的数据结构，也是是Android面试中的常客，弄懂它们的实现原理是很有必要的，本篇文章就以SparseArray的源码为例进行深入分析。

一、SparseArray的类构造

SparseArray能够翻译为稠密数组，从字面上能够了解为涣散不间断的数组。尽管叫做Array，但它却是存储K-V的一种数据结构。其中Key只能是int类型，而Value是Object类型。咱们来看下它的类构造：

public class SparseArray<E> implements Cloneable {    // 用来标记此处的值已被删除    private static final Object DELETED = new Object();    // 用来标记是否有元素被移除    private boolean mGarbage = false;    // 用来存储key的汇合    private int[] mKeys;    // 用来存储value的汇合    private Object[] mValues;    // 存入的元素个数    private int mSize;        // 默认初始容量为10    public SparseArray() {        this(10);    }    public SparseArray(int initialCapacity) {        if (initialCapacity == 0) {            mKeys = EmptyArray.INT;            mValues = EmptyArray.OBJECT;        } else {            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);            mKeys = new int[mValues.length];        }        mSize = 0;    }        // ...省略其余代码}

能够看到SparseArray仅仅实现了Cloneable接口并没有实现Map接口，并且SparseArray外部保护了一个int数组和一个Object数组。在无参构造方法中调用了有参结构，并将其初始容量设置为了10。

二、SparseArray的remove()办法

是不是感觉很奇怪？作为一个容器类，不先讲put办法怎么先将remove呢？这是因为remove办法的一些操作会影响到put的操作。只有先理解了remove能力更容易了解put办法。咱们来看remove的代码：

// SparseArraypublic void remove(int key) {    delete(key);}public void delete(int key) {    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);    if (i >= 0) {        if (mValues[i] != DELETED) {            mValues[i] = DELETED;            mGarbage = true;        }    }}

能够看到remove办法间接调用了delete办法。而在delete办法中会先通过二分查找（二分查找代码后边剖析）找到key所在的地位，而后将这一地位的value值置为DELETE，留神，这里还将mGarbage设置为了true来标记汇合中存在删除元素的状况。设想一下，在删除多个元素后这个汇合中是不是就可能会呈现不间断的状况？大略这也是SparseArray名字的由来吧。

三、SparseArray的put()办法

作为一个存储K-V类型的数据结构，put办法是key和value的入口。也是SparseArray中最重要的一个办法。先来看下put办法的代码：

// SparseArraypublic void put(int key, E value) {    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);    if (i >= 0) { // 意味着之前mKeys中曾经有对应的key存在了,第i个地位对应的就是key。        mValues[i] = value; // 间接更新value    } else { // 返回正数阐明未在mKeys中查找到key              // 取反失去待插入key的地位        i = ~i;          // 如果插入地位小于size,并且这个地位的value刚好是被删除掉的，那么间接将key和value别离插入mKeys和mValues的第i个地位        if (i < mSize && mValues[i] == DELETED) {            mKeys[i] = key;            mValues[i] = value;            return;        }    // mGarbage为true阐明有元素被移除了，此时mKeys曾经满了，然而mKeys外部有被标记为DELETE的元素        if (mGarbage && mSize >= mKeys.length) {            // 调用gc办法挪动mKeys和mValues中的元素，这个办法能够后边剖析            gc();                                // 因为gc办法挪动了数组，因而插入地位可能有变动，所以须要从新计算插入地位            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);        }     // GrowingArrayUtils的insert办法将会将插入地位之后的所有数据向后挪动一位，而后将key和value别离插入到mKeys和mValue对应的第i个地位，如果数组空间有余还会开启扩容，后边剖析这个insert办法        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);        mSize++;    }}

尽管这个办法只有寥寥数行，然而想要齐全了解却并非易事，即便写了很具体的正文也不容易读懂。咱们无妨来详细分析一下。第一行代码通过二分查找失去了一个index。看下二分查找的代码：

// ContainerHelpersstatic 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}

对于二分查找置信大家都是比拟相熟的，这一算法用于在一组有序数组中查找某一元素所在位置的。如果数组中存在这一元素，则将这个元素对应的地位返回。如果不存在那么此时的lo就是这个元素的最佳存储地位。上述代码中将lo取反作为了返回值。因为lo肯定是大于等于0的数，因而取反后的返回值必然小于等于0.明确了这一点，再来看put办法中的这个if...else是不是很容易了解了？

// SparseArraypublic void put(int key, E value) {     if (i >= 0) {         mValues[i] = value; // 间接更新value    } else {         i = ~i;        // ... 省略其它代码    }}

如果i>=0,意味着以后的这个key曾经存在于mKeys中了，那么此时put只须要将最新的value更新到mValues中即可。而如果i<=0就意味着mKeys中之前没有对应的key。因而就须要将key和value别离插入到mKeys和mValues中。而插入的最佳地位就是对i取反。

失去插入地位之后，如果这个地位是被标记为删除的元素，那么久能够间接将其笼罩掉了，因而有以下代码：

public void put(int key, E value) {    // ...    if (i >= 0) {        // ...    } else {            // 如果i对应的地位是被删除掉的，能够间接将其笼罩        if (i < mSize && mValues[i] == DELETED) {            mKeys[i] = key;            mValues[i] = value;            return;        }        // ...    }    }

如果上边条件不满足，那么持续往下看：

public void put(int key, E value) {    // ...    if (i >= 0) {        // ...    } else {        // mGarbage为true阐明有元素被移除了，此时mKeys曾经满了，然而mKeys外部有被标记为DELETE的元素        if (mGarbage && mSize >= mKeys.length) {            // 调用gc办法挪动mKeys和mValues中的元素，这个办法能够后边剖析            gc();                                // 因为gc办法挪动了数组，因而插入地位可能有变动，所以须要从新计算插入地位            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);        }         // ...    }    }

上边咱们曾经晓得，在remove元素的时候mGarbage会被置为true，这段代码意味着有被移除的元素，被移除的地位并不是要插入的地位，并且如果mKeys曾经满了，那么就调用gc办法来挪动元素填充被移除的地位。因为mKeys中元素地位产生了变动，因而key插入的地位也可能扭转，因而须要再次调用二分法来查找key的插入地位。

以上代码最终会确定key被插入的地位，接下来调用GrowingArrayUtils的insert办法来进行key的插入操作：

// SparseArraypublic void put(int key, E value) {    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);    if (i >= 0) {         // ...    } else {          // ...    // GrowingArrayUtils的insert办法将会将插入地位之后的所有数据向后挪动一位，而后将key和value别离插入到mKeys和mValue对应的第i个地位，如果数组空间有余还会开启扩容，后边剖析这个insert办法        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);        mSize++;    }}

GrowingArrayUtils的insert办法代码如下：

// GrowingArrayUtilspublic static <T> T[] insert(T[] array, int currentSize, int index, T element) {    assert currentSize <= array.length;    // 如果插入后数组size小于数组长度，能进行插入操作    if (currentSize + 1 <= array.length) {        // 将index之后的所有元素向后挪动一位        System.arraycopy(array, index, array, index + 1, currentSize - index);        // 将key插入到index的地位        array[index] = element;        return array;    }    // 来到这里阐明数组已满，需须要进行扩容操作。newArray即为扩容后的数组    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),            growSize(currentSize));    System.arraycopy(array, 0, newArray, 0, index);    newArray[index] = element;    System.arraycopy(array, index, newArray, index + 1, array.length - index);    return newArray;}// 返回扩容后的sizepublic static int growSize(int currentSize) {    return currentSize <= 4 ? 8 : currentSize * 2;}

insert办法的代码比拟容易了解，如果数组容量足够，那么就将index之后的元素向后挪动一位，而后将key插入index的地位。如果数组容量有余，那么则须要进行扩容，而后再进行插入操作。

四、SparseArray的gc()办法

这个办法其实很容易了解，咱们晓得Java虚拟机在内存不足时会进行GC操作，标记革除法在回收垃圾对象后为了防止内存碎片化，会将存活的对象向内存的一端挪动。而SparseArray中的这个gc办法其实就是借鉴了垃圾收集整理碎片空间的思维。

对于mGarbage这个参数上边曾经有提到过了，这个变量会在删除元素的时候被置为true。如下：

// SparseArray中所有移除元素的办法中都将mGarbage置为truepublic E removeReturnOld(int key) {    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);    if (i >= 0) {        if (mValues[i] != DELETED) {            final E old = (E) mValues[i];            mValues[i] = DELETED;            mGarbage = true;            return old;        }    }    return null;}public void delete(int key) {    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);    if (i >= 0) {        if (mValues[i] != DELETED) {            mValues[i] = DELETED;            mGarbage = true;        }    }}public void removeAt(int index) {    if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {        throw new ArrayIndexOutOfBoundsException(index);    }    if (mValues[index] != DELETED) {        mValues[index] = DELETED;        mGarbage = true;    }}

而SparseArray中所有插入和查找元素的办法中都会判断如果mGarbage为true，并且mSize >= mKeys.length时调用gc,以append办法为例，代码如下：

public void append(int key, E value) {    if (mGarbage && mSize >= mKeys.length) {        gc();    }     // ... 省略无关代码}

源码中调用gc办法的中央多达8处，都是与增加和查找元素相干的办法。例如put()、keyAt()、setValueAt()等办法中。gc的实现其实比较简单，就是将删除地位后的所有数据向前挪动一下，代码如下：

private void gc() {    // Log.e("SparseArray", "gc start with " + mSize);    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;    // Log.e("SparseArray", "gc end with " + mSize);}

五、SparseArray的get()办法

这个办法就比较简单了，因为put的时候是维持了一个有序数组，因而通过二分查找能够间接确定key在数组中的地位。

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];    }}

六、总结

可见SparseArray是一个应用起来很简略的数据结构，然而它的原理了解起来仿佛却没那么容易。这也是网上大部分文章对应SparseArray的解析都是含糊不清的起因。置信通过本篇文章的学习肯定对SparseArray的实现有了新的意识！

相干教程

Android根底系列教程：

Android根底课程U-小结_哔哩哔哩_bilibili

Android根底课程UI-布局_哔哩哔哩_bilibili

Android根底课程UI-控件_哔哩哔哩_bilibili

Android根底课程UI-动画_哔哩哔哩_bilibili

Android根底课程-activity的应用_哔哩哔哩_bilibili

Android根底课程-Fragment应用办法_哔哩哔哩_bilibili

Android根底课程-热修复/热更新技术原理_哔哩哔哩_bilibili

本文转自 https://juejin.cn/post/6972985532397649933，如有侵权，请分割删除。