SparseArray源码分析与性能优化

SparseArray是Android提供的数据结构,在某些场景下可以替代HashMap实现更好的性能。SparseArray在Android Java Framework源码中有大量使用。

SparseArray系列主要有:

  • SparseBooleanArray
  • SparseIntArray
  • SparseLongArray
  • SparseArray
  • LongSparseArray

SparseBooleanArray,SparseIntArray,SparseLongArray

这三者的代码几乎相同,都是int型的key,区别在于value分别是boolean、int、long型。

关键源码

以SparseIntArray为例分析,关键代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public class SparseIntArray {
private int[] mKeys;
private int[] mValues;
private int mSize;

public void put(int key, int value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;

mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}

public int get(int key, int valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

if (i < 0) {
return valueIfKeyNotFound;
} else {
return mValues[i];
}
}

public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

if (i >= 0) {
removeAt(i);
}
}

public void removeAt(int index) {
System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
mSize--;
}

public int size() {
return mSize;
}
}

class 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
}
}

final class GrowingArrayUtils {
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;

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

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

分析

SparseIntArray中有两个数组mKeys和mValues,分别保存对应的key和value,mSize用于保存数量。

二分法

Key在数组中按顺序插入,put、get、delete,都调用ContainerHelpers.binarySearch,使用二分法查找Key所在的Index。

  • 如果找到了Key,则返回index,index的值大于等于0。
  • 如果没找到,则返回lo按位取反后的结果,返回值是小于0的。对于put方法,此时的lo刚好是Key应该插入的位置。

get方法

  • 找到了Key则直接返回对应Value,没找到则返回valueIfKeyNotFound

put方法

  • 找到了Key则直接覆盖对应的value,没找到则将binarySearch返回的值取反得到lo的原始值,再调用GrowingArrayUtils.insert,将后面的数据往后移动一位,给新数据腾出位置,并在lo的位置插入新的数据。如果容量不够,则会重新分配内存扩大容量。

delete方法

  • 找到了Key,则直接调用System.arraycopy将后面的数据往前移动一位。

SparseArray,LongSparseArray与性能优化

前面三种API保存的都是boolean、int、long基本类型,而SparseArray和LongSparseArray都支持泛型,返回任意类型的数据,并且在SparseIntArray的基础上做了性能优化

关键源码

SparseArray的Key是int型,而LongSparseArray的Key是long型。这里以SparseArray为例分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;

private int[] mKeys;
private Object[] mValues;
private int mSize;

@SuppressWarnings("unchecked")
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];
}
}

public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

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

mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}

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 int size() {
if (mGarbage) {
gc();
}

return mSize;
}

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

分析

还是mKeymValues数组保存Key和Value,还是实用二分法查找Key的位置。但是多了一个优化逻辑。

在SparseArray中:

  • Value数组中保存的可能是有效数据,也可能是固定的DELETED对象,下面简称为无效数据

  • mSize并不是有效数据的数量,而是有效数据+无效数据的总数量。

  • mGarbage标志位,表示Value数组中是否包含了无效数据(准确来说是Value数组中0 ~ mSize-1的区间)。

delete方法

  • 在SparseIntArray中,删除元素操作会立即删除元素,将后面的数据往前挪,并改变mSize
  • 在SparseArray中,删除数据并不会立即删除,而是将数据标记为已删除。具体的做法是将Value设置为固定的DELETED对象,同时还会设置标志位mGarbage(这个标记删除的思路,有点像文件系统中删除文件的操作)。

get方法

  • 如果二分法找到了Key,同时对应的Value为有效数据,则返回Value。

put方法

  • 如果二分法找到了Key,无论Value是否为有效数据,都直接覆盖掉。
  • 如果没找到Key,则获取插入位置。如果碰巧这个位置保存的是无效数据,则直接覆盖Key和Value为新数据即可。
  • 如果已经获取插入位置,该位置已经被有效数据占据,Value数组中包含了无效数据(mGarbage==true),且已经存不下新数据了(mSize >= mKeys.length),则调用gc方法,将无效数据从数组中清理掉,然后重新搜索应该插入的位置。
  • 最后,和SparseIntArray的逻辑一样,移动后面的数据,给新数据腾出位置并插入。

size方法

  • SparseArray中的mSize保存的是有效数据+无效数据总数量,而不是有效数据的数量,因此在调用size方法时,也会触发gc,清理无效数据,并得到真实的Size。

gc方法

gc方法的实现比较简单,使用双指针的思路:

  • 指针i在数组中遍历一遍,指针o每次遇到有效数据就自增,并将Key和Value从位置i复制到位置o
  • 为了防止内存泄露,还有一句values[i] = null,将原始位置的重复引用清除掉。
  • 移动完成后,清除mGarbage标志,并修改mSize的值,因为此时已经没有无效数据了,mSize的值就等于有效数据的数量。

进一步优化点

在put方法触发gc的分支中,需要经过四步操作:

  • 二分搜索
  • gc
  • 重新二分搜索
  • 给新数据腾出空间并插入

实际上可以对这个分支进行优化,将后面的三步合并,只需要遍历一遍就可以同时实现gc和插入操作。

SparseArray性能分析

这里主要是对比HashMap和SparseArray / LongSparseArray,在处理int/long --> Object这种映射时的性能。

SparseArray的优势

  • 避免了HashMap中对于一些基本类型的装箱拆箱操作,对CPU和内存性能都会有提高。
  • 保存Value只需要数组,存储单个元素的成本更低。而HashMap比较复杂,需要用到Node,Node中包含了额外变量。
  • 对于Key的数量可以提前明确的情况,SparseArray可以设置刚好合适的容量,节省内存。而HashMap很难保证Key的哈希值刚好均匀分布,因此通常需要让容量比Key的数量更多,才能保持较好的时间性能。
  • SparseArray数据遍历速度比HashMap快,因为是直接数组操作,而HashMap是数组+链表,逻辑比较复杂。
  • HashMap在容量不足、Key发生哈希冲突的情况下,需要遍历链表逐个对比Key,就没有SparseArray的二分法速度快了。

SparseArray的缺点

  • 如果Key较多并且不能提前确定或变动频繁,SparseArray的数组就会很庞大,而插入、删除时又很容易触发移动、扩容操作,性能就会非常差。
  • HashMap在Key发生哈希冲突很少的情况下,计算hashCode比SparseArray的二分法性能更好。

使用SparseArray的建议

在SparseArray的JavaDoc中已经说明了,SparseArray并不是设计用来保存大量数据的,更适合数据较少的情况,能节省内存。

SparseArray首次插入某个Key时,如果按照Key从小到大插入,性能会很好,每次都会在数组尾部插入新数据。但是反过来性能就会很差,因为需要频繁移动已有数据。因此如果Key的取值很不稳定,忽大忽小,使用SparseArray效果可能就比较差了。

如果Key是提前明确的,建议使用SparseArray。初始化时可以指定SparseArray的容量,还可以提前按照Key从小到大的顺序,调用SparseArray.append方法预先存放到SparseArray中,之后使用时就不会触发移动、扩容操作了。

举例:

  • RecyclerView中按照ViewType缓存ViewHolder,使用了SparseArray。一般来说ViewType不会很多。

  • 用后台返回的id作为Key,保存较多Object。因为id的取值范围很大,其值的大小也不确定,因此SparseArray的性能不佳。

  • 使用RecyclerView的position为Key,给每个Item缓存数据(例如从本地或者网络加载数据)。这种场景适合SparseArray,一般来说,首次插入某个Key时,刚好是接近从小到大的顺序获取到数据的。