Android机制源码分析（二）：Android Util系列之SparseArray

碎碎念

临近毕业，在成为一名全职android开发工程师之前，重新回顾那些重要的基础知识，这是第二篇

稀疏数组

为了了解SparseArray和ArrayList的区别，需要了解一些前置知识：

稀疏数组（Sparse Array）是指数组中大部分元素为默认值（通常为0或者null）的数组。与稠密数组（Dense Array）相比，稀疏数组只存储非默认值的元素及其位置信息，从而减少了存储空间的占用。

在许多应用场景中，数组的元素往往具有一定的规律性，而且默认值占据了大部分的数组空间。例如，图像处理中的像素矩阵、稀疏矩阵的表示等都可以使用稀疏数组来减少存储开销。

稀疏数组通常采用一种压缩的方式进行存储，以便有效地表示数组中的非默认值元素。常用的稀疏数组存储格式包括：

哈希表（Hash Table）：使用哈希表来存储非默认值元素的索引和值。通过哈希函数可以将索引映射到哈希表的位置，从而快速地进行查找和插入操作。
链表（Linked List）：使用链表来存储非默认值元素及其位置信息。每个节点包含元素值、索引和指向下一个节点的指针，通过遍历链表可以获取稀疏数组中的非默认值元素。

这些存储格式根据具体的应用场景和操作需求选择不同的方式，以便在稀疏数组的表示和操作中提高效率。

通过使用稀疏数组，可以在处理大规模数组时减少内存占用，提高存储和计算效率。但需要注意的是，稀疏数组在某些情况下可能会增加一些操作的复杂度，例如插入、删除元素等操作可能需要重新调整稀疏数组的结构。因此，在选择使用稀疏数组时需要综合考虑数据规模、访问模式和操作需求等因素。

源码分析

直接上源码分析，为了便于理解，我将部分注释简单翻译成了中文，比较粗糙，还请见谅

SparseArray 包含以下重要成员变量和方法：

成员变量：

private int[] mKeys: 保存键的数组。
private Object[] mValues: 保存值的数组。
private int mSize: SparseArray 中实际映射的数量。
private boolean mGarbage: 标记是否有删除的条目。

方法：

public SparseArray(): 构造函数，创建一个空的 SparseArray，默认初始容量为 10。
public SparseArray(int initialCapacity): 构造函数，创建一个空的 SparseArray，指定初始容量。
public boolean contains(int key): 判断 SparseArray 是否包含指定的键。
public E get(int key): 根据键获取对应的值。
public E get(int key, E valueIfKeyNotFound): 根据键获取对应的值，如果不存在则返回指定的默认值。
public void delete(int key): 删除指定键的映射关系。
public void remove(int key): 删除指定键的映射关系。
public void removeAt(int index): 根据索引删除映射关系。
public void put(int key, E value): 添加或替换指定键的映射关系。
public int size(): 返回 SparseArray 中映射的数量。
public int keyAt(int index): 返回指定索引处的键。
public E valueAt(int index): 返回指定索引处的值。
public void setValueAt(int index, E value): 设置指定索引处的值。
public int indexOfKey(int key): 返回指定键的索引。
public SparseArray<E> clone(): 克隆 SparseArray。

SparseArray 使用数组来存储键值对，通过二分查找来查找键的位置。在删除键值对时，会将对应位置的值标记为 DELETED，并在后续需要扩容、获取大小或值时进行垃圾回收操作。

package android.util;

import android.compat.annotation.UnsupportedAppUsage;
import com.android.internal.util.ArrayUtils;
import com.android.internal.util.GrowingArrayUtils;
import libcore.util.EmptyArray;

import java.util.Objects;

/**
 * <code>SparseArray</code> 将整数映射到对象上，与普通的对象数组不同的是，它的索引可以包含空洞。
 * <code>SparseArray</code> 旨在比
 * <a href="/reference/java/util/HashMap"><code>HashMap</code></a> 更节省内存，
 * 因为它避免了键的自动装箱，并且其数据结构不依赖于每个映射的额外条目对象。
 *
 * <p>请注意，该容器将映射保留在数组数据结构中，使用二分搜索来查找键。该实现不适用于
 * 可能包含大量项的数据结构。它通常比
 * <code>HashMap</code> 慢，因为查找需要二分搜索，添加和删除需要在数组中插入和删除条目。
 * 对于容纳数百个项的容器，性能差异小于 50%。</p>
 *
 * <p>为了提高性能，该容器在删除键时包含了一种优化方法：它不会立即压缩其数组，
 * 而是将已删除的条目标记为已删除。然后可以重新使用该条目用于相同的键，或在稍后的单个垃圾回收中压缩它。
 * 必须在数组需要增长时或检索映射大小或条目值时执行此垃圾回收。</p>
 *
 * <p>可以使用 {@link #keyAt(int)} 和 {@link #valueAt(int)} 遍历此容器中的项。
 * 使用升序的索引值使用 <code>keyAt</code> 和 <code>valueAt</code> 方法，
 * 或者使用降序的索引值使用 <code>keyAt</code> 和 <code>valueAt</code> 方法，
 * 或者使用 <code>size()</code> 和 <code>get(int)</code> 方法以任意顺序遍历。</p>
 *
 * @param <E> 所保存对象的类型
 */
public class SparseArray<E> implements Cloneable {
    /**
     * 默认初始容量。
     */
    public static final int DEFAULT_INITIAL_CAPACITY = 10;

    /**
     * 表示已删除条目的标记对象。
     */
    private static final Object DELETED = new Object();

    /**
     * 用于存储键的数组。
     */
    private int[] mKeys;

    /**
     * 用于存储值的数组。
     */
    private Object[] mValues;

    /**
     * 有效映射的数量。
     */
    private int mSize;

    /**
     * 标记是否已删除条目以便在下次垃圾回收时进行压缩。
     */
    private boolean mGarbage;

    /**
     * 创建一个新的 <code>SparseArray</code> 对象，默认初始容量为 {@link #DEFAULT_INITIAL_CAPACITY}。
     */
    public SparseArray() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * 创建一个新的 <code>SparseArray</code> 对象，指定初始容量。
     *
     * @param initialCapacity 初始容量
     */
    public SparseArray(int initialCapacity) {
        mGarbage = false;
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

    /**
     * 复制一个 <code>SparseArray</code> 对象。
     *
     * @return 该对象的副本
     */
    @Override
    public SparseArray<E> clone() {
        SparseArray<E> clone = null;
        try {
            clone = (SparseArray<E>) super.clone();
            clone.mKeys = mKeys.clone();
            clone.mValues = mValues.clone();
        } catch (CloneNotSupportedException e) {
            // 不应该发生，因为我们是可克隆的
        }
        return clone;
    }

    /**
     * 获取有效映射的数量。
     *
     * @return 映射的数量
     */
    public int size() {
        if (mGarbage) {
            gc();
        }
        return mSize;
    }

    /**
     * 检查该容器是否为空。
     *
     * @return 如果为空，则为 <code>true</code>，否则为 <code>false</code>
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 获取指定键的值。
     *
     * @param key 要获取值的键
     * @return 与指定键关联的值；如果键不存在，则返回 <code>null</code>
     */
    @UnsupportedAppUsage
    public E get(int key) {
        return get(key, null);
    }

    /**
     * 获取指定键的值，如果键不存在，则返回提供的默认值。
     *
     * @param key          要获取值的键
     * @param defaultValue 如果键不存在，则返回的默认值
     * @return 与指定键关联的值；如果键不存在，则返回提供的默认值
     */
    @UnsupportedAppUsage
    public E get(int key, E defaultValue) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i < 0 || mValues[i] == DELETED) {
            return defaultValue;
        } else {
            return (E) mValues[i];
        }
    }

    // 其他方法...
}

另外对于几个重点方法，在这里着重介绍一下:

gc()

这段代码是 SparseArray 类中的 gc 方法的实现。让我们逐行解释它的作用：

private void gc() {
    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;
  
    // 遍历 SparseArray 中的元素
    for (int i = 0; i < n; i++) {
        Object val = values[i];
    
        // 如果当前元素不是占位符 DELETED
        if (val != DELETED) {
            // 如果当前索引 i 不等于 o，说明有需要回收的元素
            if (i != o) {
                // 将键值对移动到更靠前的位置
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }
        
            // 更新有效元素的数量
            o++;
        }
    }
  
    // 清除标记，表示 SparseArray 不再处于垃圾状态
    mGarbage = false;
    // 更新有效元素的数量
    mSize = o;
}

这个 gc 方法用于在 SparseArray 中进行垃圾回收。在 SparseArray 中，元素的删除并不会立即释放内存，而是将被删除元素的值设为占位符 DELETED，并记录 SparseArray 的状态为 “垃圾状态”。当需要使用或遍历 SparseArray 时，通过调用 gc 方法来进行垃圾回收。

在 gc 方法中，通过遍历 SparseArray 的元素，将有效元素向前移动，去除已被删除的元素和占位符。然后，更新有效元素的数量，并将 SparseArray 的状态设置为非垃圾状态。

通过这种方式，SparseArray 可以减少内存占用，并提高性能。垃圾回收过程中，SparseArray 不会立即释放内存，而是等到下一次访问或遍历时才进行回收，从而避免了频繁的内存分配和释放操作。

put()

这段代码是 SparseArray 类中的 put 方法的实现。让我们逐行解释它的作用：

/**
 * 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 已存在于 SparseArray 中，则替换对应的值
    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        // 如果 key 不存在于 SparseArray 中，并且存在被删除的位置可用，则直接插入到被删除的位置
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        // 如果 SparseArray 处于垃圾状态并且数组已满，则进行垃圾回收
        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++;
    }
}

这个 put 方法用于向 SparseArray 中添加键值对，如果指定的键已存在，则替换对应的值。如果键不存在，则根据以下情况处理：

如果存在被删除的位置可用（即 mValues[i] == DELETED），则直接将键值对插入该位置，并更新对应的值。
如果 SparseArray 处于垃圾状态并且数组已满，则通过调用 gc 方法进行垃圾回收，以释放被删除的元素的内存。然后重新搜索合适的插入位置。
最后，使用 GrowingArrayUtils.insert 方法在合适的位置插入新的键值对，并更新 SparseArray 的大小。

通过这个方法，我们可以向 SparseArray 中添加键值对，并根据需要替换现有的键值对。SparseArray 是一种优化的数据结构，适用于存储大量索引不连续的键值对，可以减少内存占用并提高性能。

SparseArray 的 put 方法和 HashMap 的 put 方法有以下区别：

存储方式：SparseArray 内部使用两个数组，一个用于存储键，一个用于存储值；而 HashMap 使用哈希表数据结构来存储键值对。
键的类型：SparseArray 的键类型是整数，而 HashMap 的键可以是任意对象。
内存占用：由于 SparseArray 的键是整数类型，它在内存占用方面更加高效。相比之下，HashMap 在存储大量数据时可能会占用更多内存，因为它需要存储键对象的引用和哈希码。
性能：由于 SparseArray 内部使用数组，查找和插入的性能通常比 HashMap 更高效。对于较小的数据集，SparseArray 可能比 HashMap 更快。但是，对于较大的数据集，HashMap 的哈希表实现通常能够提供更好的性能。
迭代顺序：SparseArray 中的元素按照键的大小顺序存储，而 HashMap 中的元素没有特定的顺序。

对比

普通的对象数组在存储键值对时，需要使用连续的索引来表示每个键值对的位置。例如，如果要存储键值对 (0, “A”) 和 (2, “B”)，普通的对象数组需要使用一个大小为3的数组，其中索引0和2分别存储值 “A” 和 “B”，而索引1则为空。这种连续的索引方式可能会浪费一些内存，尤其是在存储稀疏数据时。

而 SparseArray 则允许索引之间存在间隔，它的内部实现使用两个数组，一个用于存储键，一个用于存储值。这样，SparseArray 可以根据键的值来确定存储位置，而不需要使用连续的索引。因此，SparseArray 在存储稀疏数据时能够更加节省内存空间。

另外，由于 SparseArray 的键是整数类型，它避免了键的自动装箱操作，这也有助于节省内存。在普通的对象数组或 HashMap 中，当使用对象作为键时，需要将对象进行装箱操作，将其转换为包装类型，从而增加了内存消耗。

综上所述，SparseArray 通过允许索引间隔和避免键的自动装箱，以及使用紧凑的数据结构，达到了节省内存的目的，相比于 HashMap 在某些场景下可以提供更好的内存效率。

小结

总体来说SparseArray具有以下特点

内存效率高：SparseArray 的内部实现采用了稀疏数组的方式，它只存储非零值的元素，对于值为零的元素不占用内存空间。相比于普通的数组或 ArrayList，在存储稀疏数据时可以节省大量的内存空间。
快速查找：SparseArray 内部使用了二分查找算法，因此可以在较快的时间复杂度内进行查找操作。对于较大的数据集，它的查找效率通常比 HashMap 或 TreeMap 高。
不支持基本数据类型：SparseArray 只能存储对象类型的数据，不支持基本数据类型（如 int、boolean 等）。如果需要存储基本数据类型，可以使用对应的包装类作为值。
自动排序：SparseArray 内部会对键进行自动排序，以保证键的有序性。这在一些需要有序存储数据的场景中非常有用。
动态增删效率低：相比于普通的数组或 ArrayList，在动态插入或删除元素时，SparseArray 的效率较低。因为它需要进行数组的扩容或缩容操作，并且需要进行数据的移动。
总体而言，SparseArray 适用于存储键值对数量相对较小且键为整数的情况，而 HashMap 适用于存储键值对数量较大且键类型可以是任意对象的情况。在选择使用哪个类时，需要根据具体的需求和数据特征进行评估。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。