一、基本概念

SparseArray的用法和key為int類型，value為Object類型的HashMap相同，和HashMap相比铐伴，先簡要介紹一下它的兩點優(yōu)勢撮奏。

內(nèi)存占用

在 Java&Android 基礎(chǔ)知識梳理(8) - 容器類 我們已經(jīng)學(xué)習(xí)過HashMap的內(nèi)部實現(xiàn)，它內(nèi)部是采用數(shù)組的形式保存每個Entry当宴，并采用鏈地址法來解決Hash沖突的問題畜吊。但是采用數(shù)組會遇到擴容的問題，默認情況下當(dāng)數(shù)組內(nèi)的元素達到loadFactor的時候户矢，會將其擴大為目前大小的兩倍定拟，那么就有可能造成空間的浪費。

SparseArray雖然也是采用數(shù)組的方式來保存Key/Value

private int[] mKeys;
private Object[] mValues;

但是與HashMap使用普通數(shù)組不同逗嫡，它對存放Value的mValues數(shù)組進行了優(yōu)化，其創(chuàng)建方式為：

    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            //默認情況下株依，創(chuàng)建的 initialCapacity 大小為 10驱证。
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

其中ArrayUtils.newUnpaddedObjectArray(initialCapacity)用于創(chuàng)建優(yōu)化后的數(shù)組，該方法實際上是一個Native方法恋腕，它解決了當(dāng)數(shù)組中的元素沒有填滿時造成的空間浪費抹锄。

在 SparseArray 淺析 一文中介紹了SparseArray對于數(shù)組的優(yōu)化方式，假設(shè)有一個9 x 7的數(shù)組荠藤，在一般情況下它的存儲模型可以表示如下：

數(shù)組存儲的一般模型

可以看到這種模型下的數(shù)組當(dāng)中存在大量無用的0值伙单，內(nèi)存利用率很低。而優(yōu)化后的方案用兩個部分來表示數(shù)組：

• 第一部分：存放的是數(shù)組的行數(shù)哈肖、列數(shù)吻育、當(dāng)前數(shù)組中有效元素的個數(shù)
• 第二部分：存放的是所有有效元素的行、列數(shù)淤井、元素的值

數(shù)組存儲的優(yōu)化模型

避免自動裝箱

對于HashMap來說漩绵，當(dāng)我們采用put(1, Object)這樣的形式來放入一個元素時贱案，會進行自動裝箱，即創(chuàng)建一個Integer對象放入到Entry當(dāng)中止吐。

SparseArray則不會存在這一問題宝踪，因為我們聲明的就是int[]類型的mKeys數(shù)組。

二碍扔、源碼解析

2.1 存放過程

    
    public void put(int key, E value) {
        //通過二分查找法進行查找插入元素所在位置肴沫。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果大于0，那么直接插入蕴忆。
        if (i >= 0) { 
            mValues[i] = value;
        } else {
            //找到插入的位置颤芬。
            i = ~i;
            //如果插入的位置之前已經(jīng)分配，但是該位置上的元素已經(jīng)被標(biāo)記為刪除，那么直接替換站蝠。
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //首先回收掉之前標(biāo)記為刪除位置的元素汰具。
            if (mGarbage && mSize >= mKeys.length) {
                gc();

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //重新分配數(shù)組，并插入新的 Key菱魔，Value留荔。
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

2.2 讀取過程

    public E get(int key, E valueIfKeyNotFound) {
        //通過二分查找，在 Key 數(shù)組中得到對應(yīng) Value 的下標(biāo)澜倦。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //取出下標(biāo)對應(yīng)的元素聚蝶。
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }

2.3 刪除過程

    public void delete(int key) {
        //二分查找所在位置。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //將該位置的元素置為 DELETED藻治，它是內(nèi)部預(yù)先定義好的一個對象碘勉。
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

可以看到，在刪除元素的時候桩卵，它是用一個空的Object來標(biāo)記該位置股冗。在合適的時候（例如上面的put方法）紧索，才通過下面的gc()方法對mKeys和mValues數(shù)組 重新排列。

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

2.4 二分查找

    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            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
            }
        }
        //如果沒有找到，那么返回的是低位指針的取反坐標(biāo)伏社。
        return ~lo;  // value not present
    }

這里用的是~或粮，由于lo>=0溺拱，所以當(dāng)無法查找到對應(yīng)元素的時候画畅，返回值~lo一定<0。（~lo=-(lo+1)）

這也是我們在2.1中看到寥粹，為什么在i>=0時就可以直接替換的原因孙技，因為只要i>=0，就說明之前已經(jīng)存在一個Key相同的元素了排作。

而在返回值小于0時牵啦，對它再一次取~，就剛好可以得到 要插入的位置妄痪。

三哈雏、SparseArray 的效率問題

了解了SparseArray的原理之后，我們可以分析出有以下幾方面有可能會影響SparseArray插入的效率：

• 插入的效率衫生。插入的效率其實主要跟Key值插入的先后順序有關(guān)裳瘪，假如Key值是按 遞減順序 插入的，那么每次我們都是在mValues的[0]位置插入元素罪针，這就要求把原來Values和mKeys數(shù)組中[0, xxx]位置元素復(fù)制到[1, xxx+1]的位置彭羹，而如果是 遞增插入 的則不會存在該問題，直接擴大數(shù)組數(shù)組的范圍之后再插入即可泪酱。
• 查找的效率派殷。這點很明顯还最，因為采用了二分查找，如果查找的Key值位于折半處毡惜，那么將會更快地找到對應(yīng)的元素拓轻。

也就是說SparseArray在插入和查找上，相對于HashMap并不存在明顯的優(yōu)勢经伙，甚至在某些情況下扶叉，效率還要更差一些。

Google之所以推薦我們使用SparseArray來替換HashMap帕膜，是因為在移動端我們的數(shù)據(jù)集往往都是比較小的枣氧，而在這種情況下，這兩者效率的差別幾乎可以忽略垮刹。但是在內(nèi)存利用率上达吞，由于采用了優(yōu)化的數(shù)組結(jié)構(gòu)，并且避免了自動裝箱危纫，SparseArray明顯更高，因此更推薦我們使用SparseArray乌庶。

四种蝶、SparseArray 的衍生

SparseArray還有幾個衍生的類，它們的基本思想都是一樣的瞒大，即：

• 用兩個數(shù)組分別存儲key和value螃征，通過下標(biāo)管理映射關(guān)系。
• 采用二分查找法查找現(xiàn)在mKeys數(shù)組中對應(yīng)找到所在元素的下標(biāo)透敌，再去mValues數(shù)組中取出元素盯滚。

我們在平時使用的時候，可以根據(jù)實際的應(yīng)用場景選取相應(yīng)的集合類型酗电。

Key 類型不同

假如key為long型：

• LongSparseArray：key為long魄藕，value為Object

Value 類型不同

假如key為int，而value為下面三種基本數(shù)據(jù)類型之一撵术，那么可以采用以下三種集合來避免value的自動裝箱來進一步優(yōu)化背率。

• SparseLongArray：key為int，value為long
• SparseBooleanArray：key為int嫩与，value為boolean
• SparseIntArray：key為int寝姿，value為int

Key 和 Value 類型都不同

假如key和value都不為基本數(shù)據(jù)類型，那么可以采用：

• ArrayMap：key為Object划滋，value為Object

更多文章饵筑，歡迎訪問我的 Android 知識梳理系列：

• Android 知識梳理目錄：http://www.reibang.com/p/fd82d18994ce
• Android 面試文檔分享：http://www.reibang.com/p/8456fe6b27c4