深度剖析 Android SparseArray 源碼：高效鍵值存儲的實現原理

前言

在 Android 開發中，SparseArray<E> 是一個極具特色的數據結構，官方文檔建議：**當鍵為整型時，優先使用 SparseArray 替代 HashMap**，以避免自動裝箱/拆箱開銷並節省記憶體。本文將深入剖析其源碼 (基於 Android SDK 實現)，揭示其高效的核心機制：壓縮存儲 + 二分查找 + 延遲 GC。

一、 核心數據結構

SparseArray 內部維護兩個並行數組，而非 Map 的 Node/Entry 鏈表：

private int[] mKeys;      // 鍵數組，嚴格遞增有序
private Object[] mValues; // 值數組，與 mKeys 索引一一對應
private int mSize;        // 實際元素數量
private boolean mGarbage; // 標記是否存在已刪除元素(值為 DELETED)

設計優勢：

• 無裝箱開銷：鍵直接存基本類型 int，值存 Object 引用。
• 記憶體緊湊：兩個數組連續佈局，無 Entry 對象開銷，Cache 友好。
• 有序性：鍵數組始終保持升序，支援二分查找與範圍遍歷。

二、 構造與擴容機制

public SparseArray() { this(10); } // 默認容量 10

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = ContainerHelpers.EMPTY_INTS;
        mValues = ContainerHelpers.EMPTY_OBJECTS;
    } else {
        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); // 取 2 的冪 - 1 等優化值
        mKeys = new int[initialCapacity];
        mValues = new Object[initialCapacity];
    }
    mSize = 0;
}

• 提供預估容量可避免頻繁擴容拷貝。
• idealIntArraySize 會調整為接近 2 的冪的值，優化記憶體對齊。

三、 核心操作：二分查找

所有查找、插入、刪除的基石是 ContainerHelpers.binarySearch：

static int binarySearch(int[] array, int size, int value) {
    int lo = 0, hi = size - 1;
    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1; // 無符號右移，等價 (lo+hi)/2 但避免溢出
        final int midVal = array[mid];
        if (midVal < value) lo = mid + 1;
        else if (midVal > value) hi = mid - 1;
        else return mid; // 找到，返回索引
    }
    return ~lo; // 未找到，返回按位取反的插入點索引
}

• 返回值含義：≥0 表示找到索引；<0 表示未找到，~index 為「本應插入的位置」。
• 時間複雜度：O(log n)，遠優於線性查找，雖略劣於 HashMap 理想 O(1)，但常數因子極小。

四、 關鍵方法源碼解析

1. put(int key, E value) - 插入/更新

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) { // 鍵已存在，直接覆蓋值
        mValues[i] = value;
        return;
    }
    i = ~i; // 獲取插入位置

    // 1. 復用已刪除槽位 (DELETED 標記)
    if (i < mSize && mValues[i] == DELETED) {
        mKeys[i] = key;
        mValues[i] = value;
        return;
    }

    // 2. 若標記有垃圾且數組滿，先執行 gc() 整理
    if (mGarbage && mSize >= mKeys.length) {
        gc();
        i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); // 重新查找位置
    }

    // 3. 擴容檢查
    if (mSize >= mKeys.length) {
        int n = ArrayUtils.idealIntArraySize(mSize + 1);
        int[] nkeys = new int[n];
        Object[] nvalues = new Object[n];
        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
        mKeys = nkeys;
        mValues = nvalues;
    }

    // 4. 移動元素騰出插入位置 (保持有序)
    if (mSize - i != 0) {
        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++;
}

亮點：優先復用 DELETED 槽位，延遲數組移動與擴容。

2. get(int key) - 查找

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i < 0 || mValues[i] == DELETED) return valueIfKeyNotFound;
    return (E) mValues[i];
}

同樣依賴二分查找，檢查 DELETED 標記處理延遲刪除。

3. delete(int key) / remove(int key) - 刪除

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        mValues[i] = DELETED; // 標記刪除，不立即移動數組
        mGarbage = true;
    }
}

延遲刪除策略：僅標記 DELETED，設置 mGarbage=true。實際內存釋放與數組壓縮推遲到下次 gc() 或擴容時執行，避免頻繁移動大數組開銷。

4. gc() - 內存整理

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; // 幫助 GC
            }
            o++;
        }
    }
    mGarbage = false;
    mSize = o;
}

單次遍歷壓縮數組，清理 DELETED 槽位，將有效元素前移，釋放尾部引用。

5. append(int key, E value) - 尾部追加優化

public void append(int key, E value) {
    if (mSize != 0 && key <= mKeys[mSize - 1]) { // 鍵不遞增，退回 put
        put(key, value);
        return;
    }
    if (mGarbage && mSize >= mKeys.length) gc();
    // ... 直接放入 mSize 位置，無需二分查找與移動，極快
}

適用於**鍵已知遞增**場景 (如解析有序 ID 數據)，性能接近 O(1)。

五、 性能對比與適用場景

最佳實踐建議

• ✅ **鍵為 Integer/Long，數據量 < 10,000，頻繁遍歷/篩選** → 首選 SparseArray / LongSparseArray。
• ✅ **需要按鍵排序遍歷** → SparseArray 天然有序。
• ❌ **高併發寫入、超大數據量、鍵非整型** → 使用 HashMap/ConcurrentHashMap。
• ⚠️ **注意**：SparseArray **非線程安全**，多線程環境需外部同步或用 ConcurrentHashMap。

六、 總結

SparseArray 通過 「有序數組 + 二分查找 + 延遲刪除 GC」 的精妙組合，在 Android 移動端記憶體敏感環境下，為整型鍵值存儲提供了極具性價比的解決方案。理解其源碼機制，有助於我們在選型時做出更精準的決策，並在性能調優時針對性優化 (如預估容量、善用 append、適時調用 gc())。它是 Android 基礎庫中「空間換時間、順序換雜度」設計哲學的經典體現。