本文出自:【張旭童的簡(jiǎn)書(shū)】 (http://www.reibang.com/users/8e91ff99b072/latest_articles)
想來(lái)gayhub和我gaygayup:【mcxtzhang的Github主頁(yè)】https://github.com/mcxtzhang

1 概述

在前文中，我們已經(jīng)聊過(guò)了HashMap和LinkedHashMap ArrayMap.所以如果沒(méi)看過(guò)憾朴，可以先閱讀
面試必備：HashMap源碼解析（JDK8） ,
面試必備：LinkedHashMap源碼解析（JDK8 狸捕，
面試必備：ArrayMap源碼解析
今天依舊是看看android sdk的源碼。

本文將從幾個(gè)常用方法下手众雷，來(lái)閱讀SparseArray的源碼灸拍。
按照從構(gòu)造方法->常用API（增、刪砾省、改鸡岗、查）的順序來(lái)閱讀源碼，并會(huì)講解閱讀方法中涉及的一些變量的意義编兄。了解SparseArray的特點(diǎn)轩性、適用場(chǎng)景。

如果本文中有不正確的結(jié)論狠鸳、說(shuō)法揣苏，請(qǐng)大家提出和我討論，共同進(jìn)步件舵，謝謝卸察。

2 概要

概括的說(shuō)，SparseArray<E>是用于在Android平臺(tái)上替代HashMap的數(shù)據(jù)結(jié)構(gòu),更具體的說(shuō)芦圾，
是用于替代key為int類型蛾派，value為Object類型的HashMap。
和ArrayMap類似个少，它的實(shí)現(xiàn)相比于HashMap更加節(jié)省空間，而且由于key指定為int類型眯杏，也可以節(jié)省int-Integer的裝箱拆箱操作帶來(lái)的性能消耗夜焦。

它僅僅實(shí)現(xiàn)了implements Cloneable接口，所以使用時(shí)不能用Map作為聲明類型來(lái)使用岂贩。

它也是線程不安全的茫经，允許value為null巷波。

從原理上說(shuō)，
它的內(nèi)部實(shí)現(xiàn)也是基于兩個(gè)數(shù)組卸伞。
一個(gè)int[]數(shù)組mKeys抹镊，用于保存每個(gè)item的key，key本身就是int類型荤傲，所以可以理解hashCode值就是key的值.
一個(gè)Object[]數(shù)組mValues垮耳，保存value。容量和key數(shù)組的一樣遂黍。

類似ArrayMap,
它擴(kuò)容的更合適终佛，擴(kuò)容時(shí)只需要數(shù)組拷貝工作，不需要重建哈希表雾家。

同樣它不適合大容量的數(shù)據(jù)存儲(chǔ)铃彰。存儲(chǔ)大量數(shù)據(jù)時(shí)，它的性能將退化至少50%芯咧。

比傳統(tǒng)的HashMap時(shí)間效率低牙捉。
因?yàn)槠鋾?huì)對(duì)key從小到大排序，使用二分法查詢key對(duì)應(yīng)在數(shù)組中的下標(biāo)敬飒。
在添加鹃共、刪除、查找數(shù)據(jù)的時(shí)候都是先使用二分查找法得到相應(yīng)的index驶拱，然后通過(guò)index來(lái)進(jìn)行添加霜浴、查找、刪除等操作蓝纲。

所以其是按照key的大小排序存儲(chǔ)的阴孟。

另外，SparseArray為了提升性能税迷，在刪除操作時(shí)做了一些優(yōu)化：
當(dāng)刪除一個(gè)元素時(shí)永丝，并不是立即從value數(shù)組中刪除它，并壓縮數(shù)組箭养，
而是將其在value數(shù)組中標(biāo)記為已刪除慕嚷。這樣當(dāng)存儲(chǔ)相同的key的value時(shí)，可以重用這個(gè)空間毕泌。
如果該空間沒(méi)有被重用喝检，隨后將在合適的時(shí)機(jī)里執(zhí)行g(shù)c（垃圾收集）操作，將數(shù)組壓縮撼泛，以免浪費(fèi)空間挠说。

適用場(chǎng)景：

• 數(shù)據(jù)量不大（千以內(nèi)）
• 空間比時(shí)間重要
• 需要使用Map，且key為int類型愿题。

示例代碼：

        SparseArray<String> stringSparseArray = new SparseArray<>();
        stringSparseArray.put(1,"a");
        stringSparseArray.put(5,"e");
        stringSparseArray.put(4,"d");
        stringSparseArray.put(10,"h");
        stringSparseArray.put(2,null);

        Log.d(TAG, "onCreate() called with: stringSparseArray = [" + stringSparseArray + "]");

輸出：

//可以看出是按照key排序的
onCreate() called with: stringSparseArray = [{1=a, 2=null, 4=d, 5=e, 10=h}]

3 構(gòu)造函數(shù)

    //用于標(biāo)記value數(shù)組损俭，作為已經(jīng)刪除的標(biāo)記
    private static final Object DELETED = new Object();
    //是否需要GC 
    private boolean mGarbage = false;
    
    //存儲(chǔ)key 的數(shù)組
    private int[] mKeys;
    //存儲(chǔ)value 的數(shù)組
    private Object[] mValues;
    //集合大小
    private int mSize;
    
    //默認(rèn)構(gòu)造函數(shù)蛙奖，初始化容量為10
    public SparseArray() {
        this(10);
    }
    //指定初始容量
    public SparseArray(int initialCapacity) {
        //初始容量為0的話，就賦值兩個(gè)輕量級(jí)的引用
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
        //初始化對(duì)應(yīng)長(zhǎng)度的數(shù)組
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        //集合大小為0
        mSize = 0;
    }

構(gòu)造函數(shù) 無(wú)亮點(diǎn)杆兵，路過(guò)雁仲。
關(guān)注一下幾個(gè)變量：

• 底層數(shù)據(jù)結(jié)構(gòu)為int[]和Object[]類型數(shù)組。
• mGarbage: 是否需要GC
• DELETED: 用于標(biāo)記value數(shù)組琐脏，作為已經(jīng)刪除的標(biāo)記

4 增 攒砖、改

4.1 單個(gè)增、改：

    public void put(int key, E value) {
        //利用二分查找骆膝，找到 待插入key 的 下標(biāo)index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果返回的index是正數(shù)祭衩，說(shuō)明之前這個(gè)key存在，直接覆蓋value即可
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //若返回的index是負(fù)數(shù)阅签，說(shuō)明 key不存在.
            
            //先對(duì)返回的i取反掐暮，得到應(yīng)該插入的位置i
            i = ~i;
            //如果i沒(méi)有越界，且對(duì)應(yīng)位置是已刪除的標(biāo)記政钟，則復(fù)用這個(gè)空間
            if (i < mSize && mValues[i] == DELETED) {
            //賦值后路克，返回
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            
            //如果需要GC，且需要擴(kuò)容
            if (mGarbage && mSize >= mKeys.length) {
                //先觸發(fā)GC
                gc();
                //gc后养交，下標(biāo)i可能發(fā)生變化精算，所以再次用二分查找找到應(yīng)該插入的位置i
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //插入key（可能需要擴(kuò)容）
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            //插入value（可能需要擴(kuò)容）
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            //集合大小遞增
            mSize++;
        }
    }
    //二分查找 基礎(chǔ)知識(shí)不再詳解
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            //關(guān)注一下高效位運(yùn)算
            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
            }
        }
        //若沒(méi)找到，則lo是value應(yīng)該插入的位置碎连，是一個(gè)正數(shù)灰羽。對(duì)這個(gè)正數(shù)去反，返回負(fù)數(shù)回去
        return ~lo;  // value not present
    }
    
    //垃圾回收函數(shù),壓縮數(shù)組
    private void gc() {
        //保存GC前的集合大小
        int n = mSize;
        //既是下標(biāo)index鱼辙，又是GC后的集合大小
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        //遍歷values集合廉嚼，以下算法 意義為 從values數(shù)組中，刪除所有值為DELETED的元素
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            //如果當(dāng)前value 沒(méi)有被標(biāo)記為已刪除
            if (val != DELETED) {
                //壓縮keys倒戏、values數(shù)組
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    //并將當(dāng)前元素置空怠噪，防止內(nèi)存泄漏
                    values[i] = null;
                }
                //遞增o
                o++;
            }
        }
        //修改 標(biāo)識(shí)，不需要GC
        mGarbage = false;
        //更新集合大小
        mSize = o;
    }

GrowingArrayUtils.insert:

    //
    public static int[] insert(int[] array, int currentSize, int index, int element) {
        //斷言 確認(rèn) 當(dāng)前集合長(zhǎng)度 小于等于 array數(shù)組長(zhǎng)度
        assert currentSize <= array.length;
        //如果不需要擴(kuò)容
        if (currentSize + 1 <= array.length) {
            //將array數(shù)組內(nèi)元素杜跷，從index開(kāi)始 后移一位
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            //在index處賦值
            array[index] = element;
            //返回
            return array;
        }
        //需要擴(kuò)容
        //構(gòu)建新的數(shù)組
        int[] newArray = new int[growSize(currentSize)];
        //將原數(shù)組中index之前的數(shù)據(jù)復(fù)制到新數(shù)組中
        System.arraycopy(array, 0, newArray, 0, index);
        //在index處賦值
        newArray[index] = element;
        //將原數(shù)組中index及其之后的數(shù)據(jù)賦值到新數(shù)組中
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        //返回
        return newArray;
    }
    //根據(jù)現(xiàn)在的size 返回合適的擴(kuò)容后的容量
    public static int growSize(int currentSize) {
        //如果當(dāng)前size 小于等于4傍念，則返回8， 否則返回當(dāng)前size的兩倍
        return currentSize <= 4 ? 8 : currentSize * 2;
    }

• 二分查找葛闷，若未找到返回下標(biāo)時(shí)憋槐，與JDK里的實(shí)現(xiàn)不同，JDK是返回return -(low + 1); // key not found.,而這里是對(duì) 低位去反 返回孵运。
  這樣在函數(shù)調(diào)用處秦陋，根據(jù)返回值的正負(fù)，可以判斷是否找到index治笨。對(duì)負(fù)index取反驳概，即可得到應(yīng)該插入的位置。

• 擴(kuò)容時(shí)旷赖，當(dāng)前容量小于等于4顺又，則擴(kuò)容后容量為8.否則為當(dāng)前容量的兩倍。和ArrayList,ArrayMap不同(擴(kuò)容一半)等孵，和Vector相同(擴(kuò)容一倍)稚照。

• 擴(kuò)容操作依然是用數(shù)組的復(fù)制、覆蓋完成俯萌。類似ArrayList.

5 刪

5.1 按照key刪除

    //按照key刪除
    public void remove(int key) {
        delete(key);
    }
    
    public void delete(int key) {
        //二分查找得到要?jiǎng)h除的key所在index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果>=0,表示存在
        if (i >= 0) {
            //修改values數(shù)組對(duì)應(yīng)位置為已刪除的標(biāo)志DELETED
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED; 
                //并修改 mGarbage ,表示稍后需要GC
                mGarbage = true;
            }
        }
    }

5.2 按照index刪除

    public void removeAt(int index) {
        //根據(jù)index直接索引到對(duì)應(yīng)位置 執(zhí)行刪除操作
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

5.3 批量刪除

    public void removeAtRange(int index, int size) {
    //越界修正
        final int end = Math.min(mSize, index + size);
        //for循環(huán) 執(zhí)行單個(gè)刪除操作
        for (int i = index; i < end; i++) {
            removeAt(i);
        }
    }

6 查

6.1 按照key查詢

    //按照key查詢果录，如果key不存在，返回null
    public E get(int key) {
        return get(key, null);
    }

    //按照key查詢咐熙，如果key不存在弱恒，返回valueIfKeyNotFound
    public E get(int key, E valueIfKeyNotFound) {
        //二分查找到 key 所在的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //不存在
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {//存在
            return (E) mValues[i];
        }
    }

6.2 按照下標(biāo)查詢

    public int keyAt(int index) {
    //按照下標(biāo)查詢時(shí)，需要考慮是否先GC
        if (mGarbage) {
            gc();
        }

        return mKeys[index];
    }
    
    public E valueAt(int index) {
     //按照下標(biāo)查詢時(shí)棋恼，需要考慮是否先GC
        if (mGarbage) {
            gc();
        }

        return (E) mValues[index];
    }

6.3查詢下標(biāo)：

    public int indexOfKey(int key) {
     //查詢下標(biāo)時(shí)返弹，也需要考慮是否先GC
        if (mGarbage) {
            gc();
        }
        //二分查找返回 對(duì)應(yīng)的下標(biāo) ,可能是負(fù)數(shù)
        return ContainerHelpers.binarySearch(mKeys, mSize, key);
    }
    public int indexOfValue(E value) {
     //查詢下標(biāo)時(shí)，也需要考慮是否先GC
        if (mGarbage) {
            gc();
        }
        //不像key一樣使用的二分查找爪飘。是直接線性遍歷去比較义起，而且不像其他集合類使用equals比較，這里直接使用的 ==
        //如果有多個(gè)key 對(duì)應(yīng)同一個(gè)value师崎，則這里只會(huì)返回一個(gè)更靠前的index
        for (int i = 0; i < mSize; i++)
            if (mValues[i] == value)
                return i;

        return -1;
    }

• 按照value查詢下標(biāo)時(shí)痕惋，不像key一樣使用的二分查找。是直接線性遍歷去比較仲义，而且不像其他集合類使用equals比較秤朗，這里直接使用的 ==
• 如果有多個(gè)key 對(duì)應(yīng)同一個(gè)value，則這里只會(huì)返回一個(gè)更靠前的index

總結(jié)

SparseArray的源碼相對(duì)來(lái)說(shuō)比較簡(jiǎn)單昼汗，經(jīng)過(guò)之前幾個(gè)集合的源碼洗禮肴熏，很輕松就可以掌握大體流程和關(guān)鍵思想：時(shí)間換空間。

Android sdk中顷窒，還提供了三個(gè)類似思想的集合：

• SparseBooleanArray,value為boolean
• SparseIntArray,value為int
• SparseLongArray,value為long

他們和SparseArray唯一的區(qū)別在于value的類型蛙吏，SparseArray的value可以是任意類型。而它們是三個(gè)常使用的拆箱后的基本類型鞋吉。