简介
对于在HashMap以及ArrayMap中，在存入int类型的key时，也必须有装箱的这一步操作。而SparseArray就是来解决int装箱问题的Map(虽然用法和Map几乎一样，但并没有继承至map，名字上也没有叫map)，同ArrayMap一样，SparseArray也是利用的二分法，但value数组只存value，大概减少1/3的容量，因为key是int，所以也不纯在hash冲突问题了。在此基础上SparseArray也叫做稀疏的Array，所以内部还有延迟回收的机制，用来减少插入以及删除时带来的列表整体移动的性能损耗。
另外因为key直接是int，所以key肯定是非空的，而value则是可空的。
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static final Object DELETED = new Object();
private boolean mGarbage = false;
// 储存key
private int[] mKeys;
// 储存value
private Object[] mValues;
private int mSize;
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;
}
默认初始容量是为10，分别有储存key的mKeys数组（按大小排序的），和储存value的mValues数组，这两个长度都是相等的，一一对应关系。
对应关系如图：
gc
相比传统的集合，SparseArray做了一个延迟的操作，所以有一个独特的gc方法，用于回收被前面删除的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
代码比较简单，就是判断这个位置value如果已经被delete，则后面的元素依次往前移动。
get
1
2
3
4
5
6
7
8
9
10
11
12
13
public E get(int key) {
return get(key, null);
}
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而言，因为不存在重复元素，所以如果返回的index大于0，则表示有这个key，但如果对应位置的value已经为DELETED，则表示已经被删除了。
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
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
// 末尾添加的append方法
public void append(int key, E value) {
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
}
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}
public void put(int key, E value) {
// 二分查找对应的位置或者可以插入的位置取反
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
// 如果是当前位置是被DELETED的，直接赋值
if (i < mSize && mValues[i] == DELETED) {
// 因为可能key并不相等，这个刚好是比他大的第一个位置，所以需要更改key
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果其他情况需要先回收空余位置
if (mGarbage && mSize >= mKeys.length) {
gc();
// 重新定位
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 插入操作
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
// com.android.internal.util.GrowingArrayUtils.java
public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(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;
}
相比直接插入，这里延迟了一下，若碰到可以直接插入的位置就不用gc了。插入用的工具类的方法，大致是需要扩容时小于4会扩容到8，其余情况都是2倍扩容。
remove
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
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;
}
}
}
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;
}
相比传统的删除移动操作，这里删除之后并不会去移动位置，只会把对应位置元素设置为DELETED。mGarbage表示是否有被删除的元素。
contains
1
2
3
4
5
6
7
8
9
10
11
public boolean contains(int key) {
return indexOfKey(key) >= 0;
}
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
contains方法会去调用indexOfKey方法，然后是会gc的
总结
SparseArray是一个延迟删除的Key为int的集合，在删除元素时不会移动数组，只会把value置空，在使用indexOfKey以及插入时插入位置不为空时才会去进行回收操作。所以想看元素内部是否有对应key时，快捷的方式是直接使用get，如果想触发gc则使用contains方法。