Android SparseArray源碼分析

一、概述

最近看一些關于Android性能優化方面的書，有講到了使用Android提供的SparseArray代替Java的HashMap來存儲key-value鍵值對，一定程度上能夠提升性能，但是SparseArray也有一定的局限性，比如key的類型固定為int，存儲的元素個數過大時對性能有較大的影響等。平時使用過SparseArray，但是未進行深入研究，藉此機會來學習一下。

二、使用SparseArray示例

SparseArray采用泛型（

SparseArray<E>

）來支援存儲任意引用類型的元素，它的使用是比較簡單的，因為它的key固定為int類型，是以隻需指定value的類型即可。下面為了示範，采用String作為value的類型。實際使用時指定我們需要的類型即可，最終存儲的key-value的類型分别為

<int,E>

。

示例如下，列舉了常用的幾個方法（更多方法可以檢視其api）：

// 建立SparseArray，指定存儲的值的類型為String
 SparseArray<String> sparseArray = new SparseArray<>();
   for (int i = ; i < ; i++) {
       sparseArray.put(i, "element" + i);  // put插入元素
   }

   // get擷取元素值
   System.out.println("element value:"+sparseArray.get()); 
   // 删除元素
   sparseArray.delete();  
   // 擷取key對應的索引
   int index = sparseArray.indexOfKey(); 
   // valueAt根據索引擷取元素值
   System.out.println("element value:"+sparseArray.valueAt(index));  

   // 删除一個範圍的值，從index起始，删除6個
   sparseArray.removeAtRange(index, );

三、SparseArray源碼分析

SparseArray是一種存儲key-value鍵值對的容器，前面使用時我們就發現，隻需指定value的類型即可，那是因為它内部對key的類型已經做了嚴格限定（隻允許為int類型），是以隻需指定value的類型即可，并且容器存儲的value隻允許為引用類型。

SparseArray将key和value分别使用數組存儲，使用數組位置的索引作為key-value的映射紐帶，通過二分查找key對應的索引，進而通過索引找到value的值。對元素的存儲也有一套管理機制（gc調節），處理已經處于DELETED 狀态的元素達到複用，使存儲空間達到最優利用。

下面我們通過SparseArray的使用流程，來一步一步解剖它。

1. 建立SparseArray

建立SparseArray隻需要一句話，如下：

SparseArray<String> sparseArray = new SparseArray<>();

實際上這是建立一個預設的SparseArray，它初始大小為10。檢視源碼可知，它是調用了另一個構造方法，初始化了一個大小為10的容器。

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

    /**
     * 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 == ) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = ;
    }

看到這裡，出現了好幾個全局變量：mKeys ，mValues ，mSize ，它們的定義如下：

private static final Object DELETED = new Object();
    private boolean mGarbage = false;

    private int[] mKeys;  // 存儲key的數組容器，類型為int
    private Object[] mValues; // 存儲value的數組容器，類型為Object，可存儲任意引用類型
    private int mSize; //實際存儲的元素個數

可以發現key、value是單獨存儲的，對于上面的mKeys ，mValues ，mSize 都是比較好了解的，但是DELETED 常量是什麼意思？見名知意，它确實表示一種删除的對象，當對mValues中的元進行删除時，實際上是指派為DELETED 的，表示目前元素被删除了，對DELETED 的了解可以認為目前元素是無意義的或者是已經删除的。

那麼mGarbage 又是什麼？從名字上看，似乎與垃圾回收有關系，誠然它對SparseArray存儲空間的動态管理起着重要的作用，在後面後詳細分析它。

2. SparseArray存儲元素

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) {// 插入 ， key是有序存儲的，從小到大

           int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  // 二分查找key是否存在，傳回key的索引

        if (i >= ) {  // key存在則直接覆寫value
            mValues[i] = value;
        } else { // key不存在
            i = ~i;    // i= -i-1 ; 如i=-15 , 則i = ~i後i=14

            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);  // 将key插入指定位置i
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);  // 将value插入指定位置i
            mSize++; 
        }
    }

可以發現對key進行二分查找，擷取key在mKeys中的索引，然後根據這個索引來存儲value。是以，對mKeys來說是有序的（二分查找的保證），并且根據實作來看是從小到大的。

搜尋key的索引可能不存在，此時二分查找傳回的i是實際應該插入的位置index取負數-1（-index-1，即~i），此時進行 i = ~i;操作，即可得到應該插入的位置index，當然這個位置上的value有2中可能情況：

1.value可能是DELETED，此時直接進行覆寫就可以了
2.value的值是有意義的，此時需要騰出位置來以供插入

對于第二種情況，實作是由GrowingArrayUtils的insert方法來完成的，如下：

public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
       assert currentSize <= array.length;
        // 插入索引在數組範圍内，即數組長度夠，不需重新開辟空間
       if (currentSize +  <= array.length) { 
           // 将從index起的數組元素都後移一位，騰出位置
           System.arraycopy(array, index, array, index + , currentSize - index);            
            // 插入到騰出的index位置
            array[index] = element;           
            return array;
         }

        // 數組空間不夠，重新開辟空間
       T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
               growSize(currentSize));
       System.arraycopy(array, , newArray, , index); // 拷貝0~index-1 到新數組
       newArray[index] = element; // 插入到index位置
       // 拷貝index 開始的原數組元素到新數組的index + 1起始，拷貝剩餘的元素
        System.arraycopy(array, index, newArray, index + , array.length - index); 
        return newArray;  // 最後傳回新建立的數組
   }

特别說明：

arraycopy函數是System類的一個靜态函數，用于将一個數組的内容拷貝到另一個數組。

函數原型

public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)

從指定源數組中複制一個數組，複制從指定的位置開始，到目标數組的指定位置結束。
源數組中位置在 srcPos 到 srcPos+length-1 之間的元件被分别複制到目标數組中的 destPos 到 destPos+length-1 位置。

參數：

src - 源數組。
srcPos - 源數組中的起始位置。
dest - 目标數組。
destPos - 目标資料中的起始位置。
length - 要複制的數組元素的數量。

當數組長度不大于4時，指定增長為8，否則增長原來長度的兩倍，增長規律通過如下函數控制：

public static int growSize(int currentSize) {
        return currentSize <=  ?  : currentSize * ;
}

使用ContainerHelpers的binarySearch方法進行二分查找，對于其中的二分算法如下，沒有什麼好說的：

// This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearch(int[] array, int size, int value) {
        int lo = ;
        int hi = size - ;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> ;
            final int midVal = array[mid];

            if (midVal < value) { 
                lo = mid + ;   // mid + 1 ~ hi
            } else if (midVal > value) {
                hi = mid - ;  // lo ~ mid - 1
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

2. SparseArray擷取元素

SparseArray擷取元素使用 get方法，定義如下：

/**
     * Gets the Object mapped from the specified key, or <code>null</code>
     * if no such mapping has been made.
     */
    public E get(int key) {
        return get(key, null);
    }

 /**
     * Gets the Object mapped from the specified key, or the specified Object
     * if no such mapping has been made.
     */
public E get(int key, E valueIfKeyNotFound) {
         // 二分查找key是否存在，傳回key的索引
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
         // 不存在key或key對應的值為DELETED，則傳回指定的預設值valueIfKeyNotFound
        if (i <  || mValues[i] == DELETED) {             return valueIfKeyNotFound;
        } else { 
            return (E) mValues[i];  // 存在key則傳回mValues中相同索引的value
        }
    }

可以發現，擷取元素是非常簡單的，兩個方法，要麼不指定預設值，不存在則傳回null；要麼指定預設值valueIfKeyNotFound，不存在則傳回之。和存儲元素類似，使用二分查找獲得索引，然後得到value。

還有類似的valueAt、keyAt等就不一一分析了，原理大緻相同。

3. SparseArray删除元素

SparseArray使用delete方法，通過key來删除一組key-value映射，該方法定義如下：

/**
    * Removes the mapping from the specified key, if there was any.
    */
public void delete(int key) {
       int i = ContainerHelpers.binarySearch(mKeys, mSize, key); // 二分查找key是否存在，傳回key的索引

       if (i >= ) {  // 存在key
           if (mValues[i] != DELETED) { // value有意義
               mValues[i] = DELETED; // 指派為DELETED
               mGarbage = true; // 垃圾回收flag置為true
           }
       }
}

delete方法實作比較簡單，主要有幾個關鍵點：

1.使用二分查找得到索引，和之前一樣
2.對要删除的value指派為DELETED，即将此處的value置為無意義的
3.置mGarbage 為true，為記憶體空間的管理做準備

4. SparseArray記憶體管理

上面多次見過gc方法，那它是幹什麼的呢？對于一個容器而言，增删是很平常的事，是以如何管理記憶體是一個關鍵點。SparseArray對記憶體管理使用gc方法來實作，定義如下：

private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        int n = mSize;
        int o = ;
        int[] keys = mKeys;
        Object[] values = mValues;

        for (int i = ; i < n; i++) {  // 循環周遊，将數組後面有意義的值，移動到前面為DELETED的位置
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {  // 将i處的key-value映射前移到o處
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o; // 調整後的數組的元素的真實個數

        // Log.e("SparseArray", "gc end with " + mSize);
    }

這個方法比較關鍵，對我們掌握SparseArray原理至關重要。通常有兩個條件同時滿足時，才觸發gc操作（某些方法隻需要mGarbage為true，如size()方法）：

mGarbage
mSize >= mKeys.length

mGarbage 标志着是否有元素存在垃圾狀态，即被置為DELETED

mSize >= mKeys.length 表示此時存儲的元素個數已滿，看看是否需要調整

對于gc的原理是這樣的：當滿足gc條件後，執行gc，周遊所有mValues的元素，發現DELETED狀态，則記錄下來（o），在後面的周遊發現不為DELETED時，則将目前的元素key-value映射移動到之前記錄的o處，這樣使mValues數組的前面x項都被填充有意義的值，後面的空間都騰出來，使數組能夠充分利用空間，而不是再開辟新空間來容納元素。

舉個栗子：

gc前的mValues假設是這樣子的,目前mSize=7 ：

element1, element2,element3,DELETED,element5,DELETED,element7

注:DELETED元素一般是删除了元素造成的，會使mGarbage=true

gc後的mValues變成了如下，目前mSize=5：

element1, element2,element3,element5,element7，null，null

gc後使得mValues的空間得以較好的利用，而不必從新開辟空間造成浪費。

5. SparseArray 使用index擷取key與value

在了解上面的内容的基礎上，看懂下面代碼也比較容易了：

/**
     * 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>
     *
     * <p>For indices outside of the range <code>0...size()-1</code>,
     * the behavior is undefined.</p>
     */
     public int keyAt(int index) { // 未做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>
     *
     * <p>For indices outside of the range <code>0...size()-1</code>,
     * the behavior is undefined.</p>
     */
    public E valueAt(int index) {
        if (mGarbage) {
            gc();
        }

        return (E) mValues[index];
    }

從上面的注釋可以得到：

在得到key或value時，可能會觸發gc操作
keyAt(0)獲得最小的key，keyAt(size()-1)可獲得最大的key
valueAt(0)傳回的是最小key對應的value，valueAt(size()-1)傳回的是最大key對應的位置
index的範圍在0…size()-1其他值是不被支援的

6. SparseArray 删除指定索引、指定範圍以及清空

删除指定索引處

/**
     * Removes the mapping at the specified index.
     *
     * <p>For indices outside of the range <code>0...size()-1</code>,
     * the behavior is undefined.</p>
     */
    public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;  // 直接指派為DELETED
            mGarbage = true;
        }
    }

删除範圍，利用removeAt來完成

/**
     * Remove a range of mappings as a batch.
     *
     * @param index Index to begin at
     * @param size Number of mappings to remove
     *
     * <p>For indices outside of the range <code>0...size()-1</code>,
     * the behavior is undefined.</p>
     */
    public void removeAtRange(int index, int size) {
        final int end = Math.min(mSize, index + size);
        for (int i = index; i < end; i++) {
            removeAt(i);
        }
    }

清空容器

/**
     * Removes all key-value mappings from this SparseArray.
     */
    public void clear() {
        int n = mSize;
        Object[] values = mValues;

        for (int i = ; i < n; i++) {
            values[i] = null;  // 清空時會将元素的值指派為null
        }

        mSize = ;
        mGarbage = false;
    }

注意：

removeAt、removeAtRange删除元素會導緻mGarbage 被置為true，但不會使mSize變化
clear操作會将所有元素的值指派為null，并且置mSize為0

四、總結

1.對于SparseArray而言，對其key-value映射方式（index，二分查找），插入元素的處理（直接覆寫還是需要拓展空間）、以及記憶體管理（gc）的了解是較為關鍵的。
2.對于SparseArray 而言，适用于存在數量不多的資料（通常推薦是1000以内），這樣才能達到性能較優。畢竟當數量大了以後，每當有删除操作，接下來的操作(比如keyAt)都可能導緻gc，會比較消耗記憶體，影響性能。
3.由于key被限定為int類型，是以在選擇時需要考慮存入的元素的key的類型，這需要結合具體的情況綜合考慮與運用。
4.SparseArray 為Android提供的容器，用來替代HashMap等Java類容器，是以使用範圍有一定的平台局限性。
5.為了達到Android前後版本的相容性，可以考慮使用v4包的SparseArrayCompat來代替SparseArray。

Android SparseArray源碼分析

一、概述

二、使用SparseArray示例

三、SparseArray源碼分析

1. 建立SparseArray

2. SparseArray存儲元素

2. SparseArray擷取元素

3. SparseArray删除元素

4. SparseArray記憶體管理

5. SparseArray 使用index擷取key與value

6. SparseArray 删除指定索引、指定範圍以及清空

四、總結

繼續閱讀

Android MVP架構MVCMVP

mvp初探

Android常用工具類簡介目錄

android常用工具類轉載自：http://www.trinea.cn/android/android-common-utils/Android常用工具類

Android常用工具類ToastUtilsSizeUtilsLogUtilsRetrofitManagerAnimUtil

BMP檔案結構及圖像每行位元組計算方法

磁盤結構及在Linux中的命名

Android Studio 0.8.0解決 Failure [INSTALL_FAILED_OLDER_SDK] 問題

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

Kotlin的ListView與RecyclerView的簡單應用

關于公司的那些坑：Android Studio篇

android SQLite事務和kotlin協程

無法正常編譯錯誤Compilation failed to complete

關于Gradle配置的小結

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Android APK檔案反編譯Android APK檔案反編譯