SparseArray源码分析

Posted on Edited on

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