最近在整顿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的代码：
// SparseArray
public 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办法的代码：
// SparseArray
public 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。看下二分查找的代码：
// ContainerHelpers
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
}
对于二分查找置信大家都是比拟相熟的，这一算法用于在一组有序数组中查找某一元素所在位置的。如果数组中存在这一元素，则将这个元素对应的地位返回。如果不存在那么此时的lo就是这个元素的最佳存储地位。上述代码中将lo取反作为了返回值。因为lo肯定是大于等于0的数，因而取反后的返回值必然小于等于0.明确了这一点，再来看put办法中的这个if…else是不是很容易了解了？
// SparseArray
public 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的插入操作：
// SparseArray
public 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办法代码如下：
// GrowingArrayUtils
public 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;
}
// 返回扩容后的size
public 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置为true
public 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，如有侵权，请分割删除。
发表回复