Google 是这么介绍SparseArray的:

/**
 * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
 * there can be gaps in the indices.  It is intended to be more memory efficient
 * than using a HashMap to map Integers to Objects, both because it avoids
 * auto-boxing keys and its data structure doesn't rely on an extra entry object
 * for each mapping.
 *
 * <p>Note that this container keeps its mappings in an array data structure,
 * using a binary search to find keys.  The implementation is not intended to be appropriate for
 * data structures
 * that may contain large numbers of items.  It is generally slower than a traditional
 * HashMap, since lookups require a binary search and adds and removes require inserting
 * and deleting entries in the array.  For containers holding up to hundreds of items,
 * the performance difference is not significant, less than 50%.</p>
 *
 * <p>To help with performance, the container includes an optimization when removing
 * keys: instead of compacting its array immediately, it leaves the removed entry marked
 * as deleted.  The entry can then be re-used for the same key, or compacted later in
 * a single garbage collection step of all removed entries.  This garbage collection will
 * need to be performed at any time the array needs to be grown or the the map size or
 * entry values are retrieved.</p>
 *
 * <p>It is possible to iterate over the items in this container using
 * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
 * <code>keyAt(int)</code> with ascending values of the index will return the
 * keys in ascending order, or the values corresponding to the keys in ascending
 * order in the case of <code>valueAt(int)</code>.</p>
 */

Google 推荐我们使用SparseArray 来代替 HashMap<Integer, Objects>, 原因是SparseArray能更高效的使用内存.

但是如果包含很多 items 的时候效率就比传统的 HashMap 要低了, 来分析分析 SparseArray 的源码吧~

SparseArray 默认申请10个长度的内存, 当然我们也可以自己来设置默认的容器大小.

/**
 * Creates a new SparseArray containing no mappings.
 */
public SparseArray() {
    this(10);
}

/**
 * Creates a new SparseArray containing no mappings that will not
 * require any additional memory allocation to store the specified
 * number of mappings.  If you supply an initial capacity of 0, the
 * sparse array will be initialized with a light-weight representation
 * not requiring any additional array allocations.
 */
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;
}

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
/**
* 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);

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

put 函数中出现了几个成员变量,简单介绍一下

  • DELETEDObject 的一个final对象, 它主要用来覆盖被删除的 item
  • mGarbage 一个 boolean 型的成员变量, 用来标记 items 是否发生删除,存在垃圾
  • mKeys 一个 int 型的数组, 用来存放 key
  • mValues 一个 Object 的数组, 用来存放 Value
  • mSize 一个 int 的数据类型, 用来存放 items 的个数

上述成员是 SparseArray 的所有成员.

接着看 put 函数, 第 7 行 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);, 首先通过二分法来查找 keymKeys 的下标(取反).

需要注意的是, mSizeitems 的个数,并不是 mKeys 的长度, 所以在插入第一个数据的时候, mSize = 0, 所以查找到的 i 是 -1, 而不是 -11 (之所以认为是-11是因为我当时认为 size = 10).

这里贴上 binarySearch 函数

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
}

继续看 put 函数, 如果i 大于 0,说明查到了key值,那么直接覆盖 value, 第14行到18行也好理解,如果这个地方是之前被删除的内容,那么直接保存 keyvalue.

第 20 行, 可以这么理解, 如果存在垃圾,并且初始化时的容器已经填满,那么整理一下,接着插入.

再看看 delete 的函数

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 所对应的 value 覆盖为 DELETED. mSize 什么的都没有进行 -1;

说个题外话, Google 肯定没有函数圈复杂度的要求,这段代码可以这样优化,至少能少了一圈复杂度,

1
2
3
4
5
6
    if (i < 0 || mValues[i] == DELETED) {
return;
}

mValues[i] = DELETED;
mGarbage = true;

一个数组 {1,2,3,4,5,6}, 在执行删除 3 之后,{1,2,3,4,5,6} -> {1,2,DELETED,4,5,6}

注意 delete 完之后, 在最后将 mGarbage 置为了 true.

接着我们看下其他 get 类的函数

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
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the key from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The keys corresponding to indices in ascending order are guaranteed to
* be in ascending order, e.g., <code>keyAt(0)</code> will return the
* smallest key and <code>keyAt(size()-1)</code> will return the largest
* key.</p>
*/

public int keyAt(int index) {
if (mGarbage) {
gc();
}

return mKeys[index];
}

/**
* Given an index in the range <code>0...size()-1</code>, returns
* the value from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The values corresponding to indices in ascending order are guaranteed
* to be associated with keys in ascending order, e.g.,
* <code>valueAt(0)</code> will return the value associated with the
* smallest key and <code>valueAt(size()-1)</code> will return the value
* associated with the largest key.</p>
*/

@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}

return (E) mValues[index];
}

/**
* Given an index in the range <code>0...size()-1</code>, sets a new
* value for the <code>index</code>th key-value mapping that this
* SparseArray stores.
*/

public void setValueAt(int index, E value) {
if (mGarbage) {
gc();
}

mValues[index] = value;
}

/**
* Returns the index for which {@link #keyAt} would return the
* specified key, or a negative number if the specified
* key is not mapped.
*/

public int indexOfKey(int key) {
if (mGarbage) {
gc();
}

return ContainerHelpers.binarySearch(mKeys, mSize, key);
}

/**
* Returns an index for which {@link #valueAt} would return the
* specified key, or a negative number if no keys map to the
* specified value.
* <p>Beware that this is a linear search, unlike lookups by key,
* and that multiple keys can map to the same value and this will
* find only one of them.
* <p>Note also that unlike most collections' {@code indexOf} methods,
* this method compares values using {@code ==} rather than {@code equals}.
*/

public int indexOfValue(E value) {
if (mGarbage) {
gc();
}

for (int i = 0; i < mSize; i++)
if (mValues[i] == value)
return i;

return -1;
}

观察源码, 其中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);
}

这个可以这样理解, 上述数组在执行删除 3 之后,{1,2,3,4,5,6} -> {1,2,DELETED,4,5,6}, 我们还可以继续删除 1,5

{1,2,3,4,5,6} -> {1,2,DELETED,4,5,6} -> {DELETED,2,DELETED,4,DELETED,6}

现在我们知道,在删除完之后,mSize 并没有减少,但我们在取size得时候如何保证取到的size是准确的呢, 这个就得 gc 出马保证了.

{DELETED,2,DELETED,4,DELETED,6} 在调用gc 之后 就变成了 {2,4,6,null,null,null}

o 值只有在val != DELETED的时候才会增加, 所以o 值就是最后items的个数.

所以分析到这里, SparseArray 的工作原理应该是清楚了