Ricky.L的随笔
0%

Android集合类-SparseArray原理

发表于 更新于 分类于 Disqus：

稀疏表是什么？

key为整数的哈希表

稀疏表特点

  • Key为int类型的哈希表，避免了Integer自动装箱。
  • 底层用数组存储元素，一个数组存储key，一个数组存储value，key是有序的，通过二分查找来定位元素。
  • 插入元素会移动数组，remove的时候只设置了一个removed标记位，避免频繁移动数组元素。
  • 数据量大的时候，复制数组时间就长了，查找时间也长了。
  • 好处是不需要额外的结构体，比较节约空间，数据量较小情况下访问想效率比较高。

SparseArray相比HashMap解决了什么？

优点：

  1. 避免了基本数据类型的装箱操作
  2. 不需要额外的结构体，单个元素的存储成本更低
  3. 数据量小的情况下，随机访问的效率更高，因为不需要额外复杂操作、删除元素也是延迟的

缺点：

  1. 插入操作需要复制数组，增删效率降低
  2. 数据量巨大时，复制数组成本巨大，gc()成本也巨大
  3. 数据量巨大时，查询效率也会明显下降，因为需要二分查找，而不是直接哈希命中

参考：

SparseArray适用场景？

原则：

  1. 数据量不大（千这个数量级以内）。
  2. 空间比时间重要，例如移动端对内存使用量敏感。
  3. 需要使用Map，且key为int类型。

例如：
如果有一个ViewPager的每个页面都有一个图表，并且图表的点有上千个，而ViewPager会缓存左右两页，至少要开3个图表，用HashMap明显占用内存更多，容易引发内存溢出，而且自动装箱的消耗更多，用SparseArray肯定更快，内存占用更小。

SparseArray.put(int key, E value)原理？

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

上面这段代码是一次插入数据的操作，单看的话有些难懂，因为插入跟删除之间有一定的关系，所以要看懂这段代码，还必须搞懂删除的逻辑。在看删除之前，还是先大体梳理一下插入的几个特点：

  • 存放key的数组是有序的（二分查找的前提条件）
  • 如果冲突，新值直接覆盖原值，并且不会返回原值（HashMap会返回原值）
  • 如果当前要插入的 key 的索引上的值为DELETE，直接覆盖
  • 前几步都失败了，检查是否需要gc()并且在该索引上插入数据

参考：

GrowingArrayUtils.insert()的原理？

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
/**
 * Inserts an element into the array at the specified index, growing the array if there is no
 * more room.
 *
 * @param array The array to which to append the element. Must NOT be null.
 * @param currentSize The number of elements in the array. Must be less than or equal to
 *                    array.length.
 * @param element The element to insert.
 * @return the array to which the element was appended. This may be different than the given
 *         array.
 */
@SuppressWarnings("unchecked")
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }

    T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

如果当前数据个数并不超过数组长度，直接把待插入位置后面的元素全部后移一位，腾出空间给新元素。

如果数据总个数超过了数组容纳的长度，需要扩容，扩容大小为growSize(currentSize)求得，为原大小的两倍。

1
2
3
4
5
6
7
8
9

/**
 * Given the current size of an array, returns an ideal size to which the array should grow.
 * This is typically double the given size, but should not be relied upon to do so in the
 * future.
 */
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

然后根据新大小创建新的数组，然后：

  1. 把原数组中待插入位置前面的元素都复制到新数组的前面
  2. 新数组中指定位置插入新元素
  3. 把原数组中待插入位置后面的元素都复制到新数组中插入元素的后面

SparseArray.remove(int key)原理?

通过key二分查找到index，然后讲DELETED赋值给mValues[index]，标记这个位置会删除

为什么删除标记位DELETED？而不是直接删除元素？

直接删除元素会复制数组，如果删除比较频繁，就会降低性能，这里是为了避免频繁进行数组拷贝调整

什么时候会清理掉DELETED的元素？

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

mValues里如果没有DELETED，那么i和o应该是相等的，但是如果有DELETED，o就会小于i，然后就可以把元素全部前移到数组头部，把空位留在数组尾部，相当于碎片整理了一下，留下了尾部整块的空闲空间。

什么时候触发GC()？

以下方法会调用gc()：

put的时候如果发现数组大小不够，就清理。

size()求大小需要求得正确的大小。

SparseArray使用过程有什么坑？

indexOfValue比较的是value的指针，而并没有调用equals方法。

如果value是String就有问题。

如果是Integer，在Integer的缓存范围内也有问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Returns an index for which {@link #valueAt} would return the
 * specified value, 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;
}

参考资料