SparseArray映射<Integer, Object>键值对。区别于对象数组,索引可以是非连续的。与使用HashMap映射Integer类型的key相比,使用SpaseArray存储效率更高,一方面它避免了自动对int型键自动装箱,另一方面它的数据结构不依赖额外的Map.Entry对象。
注意到这个容器使用数组保持映射关系,使用二分搜索寻找键。这种实现不适合存储大量数据项。与传统的HashMap比起来要慢,因为使用二分搜索查找,增加和移除操作需要在数组中插入和删除元素。存储上百条数据,性能差距不明显,不到50%.
为了提高性能,容器增加了移除key的优化:它不是立即压缩紧凑数组,而是将移除的entry标记为已删除。对于相同key, 这条数据可以被重用,或者在一次gc()操作的过程中紧凑所有移除的数据。当数组增长时或集合容量增加,或者获取数据值的时候,gc()操作就会在适当的时候执行。
使用keyAt(int), *valueAt(int)可以遍历容器中的数据。以升序索引值使用keyAt(int)*遍历key将返回升序的key, 使用升序key遍历将相应返回升序value.
SparseArray, 即稀疏数组,与HashMap不同的是,没有实现Map接口,不属于集合框架。定义了类似于集合中常用接口,比如get(int), put(int, Object), remove(int), size(), clear().
1
2
3
4
5
6
private static final Object DELETED = new Object();// 移除标记
private boolean mGarbage = false;// 执行gc()操作标记,当从数组中删除元素后置为true
private int[] mKeys;// key数组
private Object[] mValues;// value数组
private int mSize;// 数组大小
构造函数创建了初始大小为initialCapacity的key, value数组。但是capacity的计算,SparseArray与SparseArrayCompat调用了不同的实现.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
}
基本上SparseArray的所有操作都是基于二分搜索,二分搜索的前提是数组是有序的,如果value在数组中存在,返回索引位置,否则最后计算出的lo值表示插入位置(0 <= low <= size),如果查找不到,取反返回负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
如果key存在的话,移除指定key的映射关系,将对应的value标记为DELETED, mGarbage标记设置为true, 等待下一次操作触发gc()操作。
什么是gc操作?
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
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);
}
这里所谓的gc就是对数组进行整理压缩,使用两路指针i和o,将未标记为DELETED的映射都向数组的左端移动,很像垃圾收集器的标记-整理算法。
那么哪些操作会触发调用gc()呢?
- public void put(int key, E value)
- public int size()
- public int keyAt(int index)
- public E valueAt(int index)
- public void setValueAt(int index, E value)
- public int indexOfKey(int key)
- public int indexOfKey(int key)
- public int indexOfValue(E value)
- public void append(int key, E value)
所有的访问操作在mGarbage为true的时候都会调用gc操作,此外put, append操作在数组需要扩容的时候也会调用gc操作。
直接看SparseArrayCompat的put和append实现。
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
/**
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// key存在,更新value
if (i >= 0) {
mValues[i] = value;
} else {
// 取反计算插入位置
i = ~i;
// 插入位置非尾部且原来映射已经不存在了,则更新key-value
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 尝试gc一下扩容,重新计算索引
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 扩容,每次扩容都是以2的幂次大小扩容,重新映射
if (mSize >= mKeys.length) {
int n = ContainerHelpers.idealIntArraySize(mSize + 1);
int[] nkeys = new int[n];
Object[] nvalues = new Object[n];
// Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
mKeys = nkeys;
mValues = nvalues;
}
// 如果插入的位置不是尾部,需要向右移动插入位置后面的所有映射
if (mSize - i != 0) {
// Log.e("SparseArray", "move " + (mSize - i));
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
}
// 添加映射关系
mKeys[i] = key;
mValues[i] = value;
mSize++;
}
}
注意到插入映射的key保持了升序,因为每次put操作都会在已有的升序数组中计算插入的位置。
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
/**
* Puts a key/value pair into the array, optimizing for the case where
* the key is greater than all existing keys in the array.
*/
public void append(int key, E value) {
// 不是在尾部增加映射
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
}
int pos = mSize;
if (pos >= mKeys.length) {
int n = ContainerHelpers.idealIntArraySize(pos + 1);
int[] nkeys = new int[n];
Object[] nvalues = new Object[n];
// Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
mKeys = nkeys;
mValues = nvalues;
}
mKeys[pos] = key;
mValues[pos] = value;
mSize = pos + 1;
}
append操作没什么特别的,只是针对要插入映射key大于数组中已存在的最大key的情况做了优化,减少了gc操作后重新计算索引的操作。
为什么在数据量小的时候SparseArray的综合性能相对于HashMap要好?
SparseArray的主要优势是占用内存小,查询的时间复杂度是O(logn), n为数组的长度, 而HashMap的时间复杂度为O(n), n为发生hash冲突的元素个数。比起来HashMap查询性能更优。HashMap内部数据结构是一个Map.Entry数组,Map.Entry是一个单链表数据结构,维护了键值对,指向下一个元素的引用和key的hash值。每个映射均增加了内存开销。当数据量大的时候,SparseArray gc整理内存,put插入映射都是O(n)的时间复杂度,put操作还会造成数据迁移,而HashMap的时间复杂度为O(1).
如何计算capacity?
1
2
3
4
5
6
public static int idealByteArraySize(int need) {
for (int i = 4; i < 32; i++)
if (need <= (1 << i) - 12)
return (1 << i) - 12;
return need;
}
在扩容时计算新的容量大小使用的是上述方法,这个函数是为了方便内存分配,原则是给一个数组分配的内存空间最好是2的n次方大小,至于为什么要减去12, 是因为普通对象需要额外8字节空间管理对象相关信息(对象头部),数组另加4字节记录数组长度。
关于SparseArray, LongSparseArray.
两者实现原理相同,避免了整型,长整型键的自动装箱。
参考资料:
取反与补码
SparseArray growing policy
java对象的大小
EmptyArray
ArrayUtils
GrowingArrayUtils
idealByteArraySize