什么是SparseArray
SparseArray(稀疏数组) 是Android平台上较为推荐的一种int到object的映射结构 相比常用的HashMap 它内存占用更小而且直接使用int类型作为key, 省去了装箱操作
SparseArray原理分析
SparseArray使用一个int数组存放key,使用一个object数组存放value,保证插入的键值对在两个数组上索引的一致性来维护映射关系, 同时维护int数组有序,查找时使用二分查找法提高查找效率
SparseArray源码分析
SparseArray加上注释总共也就400+行 相对比较简单 但也有很多很精巧的设计, 下面我们就来分析SparseArray的源码
SparseArray只有4个成员变量和一个名为DELETED的静态变量
// 被删除的value会被替换为该对象
private static final Object DELETED = new Object();
// 标记数据是否被删除过(是否有垃圾存在)
private boolean mGarbage = false;
// 上面说到的 存放Key的数组
private int[] mKeys;
// 上面说到的 存放Value的Object数组
private Object[] mValues;
// Size
private int mSize;
构造方法如下,默认数组大小为10, 如果你对将要存放的键值对数量大小很明确,使用第二个构造函数指定数组初始大小可以减少数组扩展次数,获得更好的性能
public SparseArray() {
this(10); // 默认数组大小为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;
}
提供两个查询方法, 本质上都是通过2参的get方法去查询, 当key不存在时可以返回指定的值,默认为null
public E get(int key) {
return get(key, null);
}
public E get(int key, E valueIfKeyNotFound) {
// 在int数组中二分查找key对应的索引
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 索引不存在或者索引对应的value已经被删除
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
SparseArray提供了一系列的删除方法, 本质上和delete方法都是一样的, SparseArray移除对象的时候并没有真的把key从数组中移除, 只是简单的对应的value置为DELETED对象,置mGarbage为true,同时mSize不变
public E removeReturnOld(int key); // 通过key移除并返回之前的对象, 如果之前没有则返回null
public void remove(int key); // 只移除但不返回移除的value
public void removeAt(int index); //移除索引所在的value
public void removeAtRange(int index, int size); // 移除从index开始的size个对象,如果到达数组末端,则停止
public void delete(int key) {
// 查找key对应的索引
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 如果找到且value没有被删除, 将value置为DELETED, 同时标记mGarbage(value数组已脏)
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
put方法会先查找是否已经存在key,如果存在直接覆盖,如果不存在但是数组容量够,则直接插入, 如果容量不够但是存在垃圾, 会先触发垃圾回收,再执行查找索引和插入逻辑
public void put(int key, E value) {
// 二分查找, 如果没找到, 返回的值是新key对应的索引的取反值(<0)
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { // 找到key在int数组中的索引, 替换value为新的value
mValues[i] = value;
} else {
// 没有找到改key的索引, 将该key插入int数组, 插入位置是二分查找到的位置
i = ~i;
// 该位置value被标记删除, 可直接放入
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果存在垃圾同时容量不够了, 先回收垃圾所占用的空间
if (mGarbage && mSize >= mKeys.length) {
gc(); // 不是jvm的gc
// Search again because indices may have changed.
// 重新查找key的索引, 垃圾回收后索引位置可能会变化
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 插入键值对, 如果数组容量不够, 会申请一块更大的内存, 然后把原值拷贝进去
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
SparseArray的gc和delete方法是其中比较亮点的地方, delete方法并没有真正的删除key, 也没有改变mSize, 只是把mGarbage置为true, 对应的value置为DELETED,把真正移除的逻辑交由gc来处理, 这样做的好处是避免了删除一个key就引发一次数组调整,多次删除只需一次gc, 提高了操作效率
private void gc() {
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
// 遍历value数组, 清除被标记为DELETED的value
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;
}
SparseArray图解
源码可能比较枯燥, 下面用图来详细描述一下代码中SparseArray产生的变化
SparseArray sparseArray = new SparseArray(3); // 总大小为3, 便于观察
sparseArray.put(5, "Hello World");
sparseArray.put(9, "Hello Java");
sparseArray.put(1, "Hello SparseArray");
sparseArray.delete(5);
sparseArray.put(3, "Hello gc");
sparseArray.put(10086, "Hello 10086");
SparseArray.png
网友评论