一,基本概念
SparseArray 的用法和 key 为 int 类型,value 为 Object 类型的 HashMap 相同,和 HashMap 相比,先简要介绍一下它的两点优势.
内存占用
在 Java&Android 基础知识梳理 (8) - 容器类 我们已经学习过 HashMap 的内部实现,它内部是采用数组的形式保存每个 Entry,并采用链地址法来解决 Hash 冲突的问题.但是采用数组会遇到扩容的问题,默认情况下当数组内的元素达到 loadFactor 的时候,会将其扩大为目前大小的两倍,那么就有可能造成空间的浪费.
SparseArray 虽然也是采用数组的方式来保存 Key/Value
private int[] mKeys;
private Object[] mValues;
但是与 HashMap 使用普通数组不同,它对存放 Value 的 mValues 数组进行了优化,其创建方式为:
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
//默认情况下,创建的 initialCapacity 大小为 10.
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
其中
ArrayUtils.newUnpaddedObjectArray(initialCapacity)
用于创建优化后的数组,该方法实际上是一个 Native 方法,它解决了当数组中的元素没有填满时造成的空间浪费.
在 SparseArray 浅析 一文中介绍了 SparseArray 对于数组的优化方式,假设有一个 9 x 7 的数组,在一般情况下它的存储模型可以表示如下:
可以看到这种模型下的数组当中存在大量无用的 0 值,内存利用率很低.而优化后的方案用两个部分来表示数组:
第一部分:存放的是数组的行数,列数,当前数组中有效元素的个数
第二部分:存放的是所有有效元素的行,列数,元素的值
mKeys 则是用普通数组实现的,通过查找 Key 值所在的位置,再根据 mValues 数组的属性找到对应元素的行,列值,从而得到对应的元素值.
避免自动装箱
对于 HashMap 来说,当我们采用 put(1, Object) 这样的形式来放入一个元素时,会进行自动装箱,即创建一个 Integer 对象放入到 Entry 当中.
SparseArray 则不会存在这一问题,因为我们声明的就是 int[] 类型的 mKeys 数组.
二,源码解析
2.1 存放过程
public void put(int key, E value) {
//通过二分查找法进行查找插入元素所在位置.
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果大于0,那么直接插入.
if (i >= 0) {
mValues[i] = value;
} else {
//找到插入的位置.
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);
}
//重新分配数组,并插入新的 Key,Value.
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
2.2 读取过程
public E get(int key, E valueIfKeyNotFound) {
//通过二分查找,在 Key 数组中得到对应 Value 的下标.
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//取出下标对应的元素.
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
2.3 删除过程
public void delete(int key) {
//二分查找所在位置.
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//将该位置的元素置为 DELETED,它是内部预先定义好的一个对象.
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
可以看到,在删除元素的时候,它是用一个空的 Object 来标记该位置.在合适的时候(例如上面的 put 方法),才通过下面的 gc() 方法对 mKeys 和 mValues 数组 重新排列.
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;
}
2.4 二分查找
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>=0,所以当无法查找到对应元素的时候,返回值~ lo 一定 <0.(~lo=-(lo+1))
这也是我们在
2.1
中看到,为什么在 i>=0 时就可以直接替换的原因,因为只要 i>=0,就说明之前已经存在一个 Key 相同的元素了.
而在返回值小于 0 时,对它再一次取~,就刚好可以得到 要插入的位置.
三,SparseArray 的效率问题
了解了 SparseArray 的原理之后,我们可以分析出有以下几方面有可能会影响 SparseArray 插入的效率:
插入的效率.插入的效率其实主要跟 Key 值插入的先后顺序有关,假如 Key 值是按 递减顺序 插入的,那么每次我们都是在 mValues 的 [0] 位置插入元素,这就要求把原来 Values 和 mKeys 数组中 [0, xxx] 位置元素复制到 [1, xxx+1] 的位置,而如果是 递增插入 的则不会存在该问题,直接扩大数组数组的范围之后再插入即可.
查找的效率.这点很明显,因为采用了二分查找,如果查找的 Key 值位于折半处,那么将会更快地找到对应的元素.
也就是说 SparseArray 在插入和查找上,相对于 HashMap 并不存在明显的优势,甚至在某些情况下,效率还要更差一些.
Google 之所以推荐我们使用 SparseArray 来替换 HashMap,是因为在移动端我们的数据集往往都是比较小的,而在这种情况下,这两者效率的差别几乎可以忽略.但是在内存利用率上,由于采用了优化的数组结构,并且避免了自动装箱,SparseArray 明显更高,因此更推荐我们使用 SparseArray.
四,SparseArray 的衍生
SparseArray 还有几个衍生的类,它们的基本思想都是一样的,即:
用两个数组分别存储 key 和 value,通过下标管理映射关系.
采用二分查找法查找现在 mKeys 数组中对应找到所在元素的下标,再去 mValues 数组中取出元素.
我们在平时使用的时候,可以根据实际的应用场景选取相应的集合类型.
Key 类型不同
假如 key 为 long 型:
LongSparseArray:key 为 long,value 为 Object
Value 类型不同
假如 key 为 int,而 value 为下面三种基本数据类型之一,那么可以采用以下三种集合来避免 value 的自动装箱来进一步优化.
SparseLongArray:key 为 int,value 为 long
SparseBooleanArray:key 为 int,value 为 boolean
SparseIntArray:key 为 int,value 为 int
Key 和 Value 类型都不同
假如 key 和 value 都不为基本数据类型,那么可以采用:
ArrayMap:key 为 Object,value 为 Object
来源: https://juejin.im/post/5a687ccff265da3e377c31e5