介紹

Android提供了SparseArray老充，這也是一種KV形式的數(shù)據(jù)結(jié)構(gòu)列粪，提供了類似于Map的功能福侈。但是實現(xiàn)方法卻和HashMap不一樣酒来。它與Map相比，可以說是各有千秋肪凛。

優(yōu)點

• 占用內(nèi)存空間小堰汉，沒有額外的Entry對象
• 沒有Auto-Boxing

缺點

• 不支持任意類型的Key辽社，只支持?jǐn)?shù)字類型（int，long）
• 數(shù)據(jù)條數(shù)特別多的時候翘鸭，效率會低于HashMap滴铅，因為它是基于二分查找去找數(shù)據(jù)的

相關(guān)參考 SparseArray vs HashMap

總的來說，SparseArray適用于數(shù)據(jù)量不是很大就乓，同時Key又是數(shù)字類型的場景汉匙。
比如，存儲某月中每天的某種數(shù)據(jù)生蚁，最多也只有31個噩翠，同時它的key也是數(shù)字（可以使用1-31，也可以使用時間戳）邦投。
再比如伤锚，你想要存儲userid與用戶數(shù)據(jù)的映射，就可以使用這個來存儲志衣。

接下來屯援，我將講解它的特性與實現(xiàn)細(xì)節(jié)。

直觀的認(rèn)知

它使用的是兩個數(shù)組來存儲數(shù)據(jù)念脯，一個數(shù)組存儲key狞洋，另一個數(shù)組來存儲value。隨著我們不斷的增加刪除數(shù)據(jù)绿店，它在內(nèi)存中是怎么樣的呢吉懊？我們需要有一個直觀的認(rèn)識，能幫助我們更好的理解和體會它惯吕。

初始化的狀態(tài)

內(nèi)部有兩個數(shù)組變量來存儲對應(yīng)的數(shù)據(jù)惕它，mKeys用來存儲key，mValues用來存儲泛型數(shù)據(jù)废登，注意淹魄，這里使用了Object[]來存儲泛型數(shù)據(jù)，而不是T[]堡距。為什么呢甲锡？這個后面在講。

初始化的狀態(tài)

插入數(shù)據(jù)

如下圖所示羽戒，插入數(shù)據(jù)缤沦，總是“緊貼”數(shù)組的左側(cè)，換句話說易稠，總是從最左邊的一個空位開始使用缸废。我一開始沒詳細(xì)探究的時候，都以為它是類似HashMap那樣稀疏的存儲。

另一個值得注意的事情是企量，key總是有序的测萎，不管經(jīng)過多少次插入，key數(shù)組中届巩，key總是從小到大排列硅瞧。

插入數(shù)據(jù)

擴容

當(dāng)一直插入數(shù)據(jù)，快滿的時候恕汇，就會自動的擴容腕唧，創(chuàng)建一個更大的數(shù)組出來，將現(xiàn)有的數(shù)據(jù)全部復(fù)制過去瘾英，再插入新的數(shù)據(jù)枣接。這是基于數(shù)組實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)共同的特性。

刪除

刪除是使用標(biāo)記刪除的方法方咆，直接將目標(biāo)位置的有效元素設(shè)置為一個DELETED標(biāo)記對象月腋。

刪除數(shù)據(jù)

查詢數(shù)據(jù)

怎么查數(shù)據(jù)呢？
比如我們查5這個數(shù)據(jù)get(5)瓣赂，那么它是在mKeys中去查找是否存在5，如果存在片拍，返回index煌集，然后用這個index在對應(yīng)的mValues取出對應(yīng)的值就好了。

實現(xiàn)

接下來我們按照自己的理解捌省，來實現(xiàn)這樣的一個數(shù)據(jù)結(jié)構(gòu)苫纤，從而學(xué)習(xí)它的一些細(xì)節(jié)和思想，加深對它的理解纲缓，有利于在生產(chǎn)中卷拘，能更有效的，正確的使用它祝高。

確定接口（API）

首先栗弟，確定一下，我們需要暴露什么樣的功能給別人使用工闺。當(dāng)然了乍赫，答案是顯而易見的，當(dāng)然是插入陆蟆，查詢雷厂，刪除等功能了。

public class SparseArray<E> {

    public SparseArray() {
    }

    public SparseArray(int initCap) {
    }

    public void put(int key, E value) {  
    }

    public E get(int key) {  
    }

    public void delete(int key) {
    }

    public int size() {
    }
  
}

上面列舉了我們需要的功能叠殷，無參構(gòu)造函數(shù)改鲫，有參數(shù)構(gòu)造函數(shù)（期望能主動設(shè)置初始容量），put數(shù)據(jù)，get數(shù)據(jù)像棘，刪除數(shù)據(jù)纫塌，以及獲取當(dāng)前數(shù)據(jù)有多少。

實現(xiàn)put方法

put數(shù)據(jù)是最核心的方法讲弄，一般我們開發(fā)一個東西措左，也是先開發(fā)創(chuàng)建數(shù)據(jù)的功能，這樣才能接著開發(fā)展示數(shù)據(jù)的功能。所以我們先來實現(xiàn)put方法炼团。

按照之前的理解朦蕴，我們需要一些成員變量來存儲數(shù)據(jù)。

private int[] mKeys;
private Object[] mValues;
private int mSize = 0;

需要先找到put到什么位置
這里會有兩種情況：

• 我要put的key不存在凉逛，應(yīng)該put到什么地方？
• 我要put的key已經(jīng)存在群井，直接覆蓋

因此第一步状飞，需要先找一下，當(dāng)前key书斜，是否存在诬辈。我們使用二分查找來處理。

public void put(int key, E value) {
    int i = BinarySearch.search(mKeys, mSize, key);
    if (i >= 0) {
        // 找到了有兩種情況
        // 1.是對應(yīng)的mValues有一個有效的數(shù)據(jù)對象荐吉，直接覆蓋
        // 2.對應(yīng)的mValues里面是一個DELETED對象焙糟，同樣的，直接覆蓋
        mValues[i] = value;
    } else {

    }
}

如果在數(shù)組中找到了样屠，那么操作就很簡單穿撮，直接覆蓋就完事了。

如果沒找到呢痪欲，我們需要將數(shù)據(jù)插入到正確的位置上悦穿，這個所謂正確的位置，指的是业踢，插入之后栗柒，依然保證數(shù)組有序的情況。打個比方：1, 4, 5, 8陨亡，請問3應(yīng)該插入哪里傍衡，當(dāng)然是放到index=1的地方，結(jié)果就是1, 3, 4, 5, 8了负蠕。

那如果key不存在蛙埂，怎么知道應(yīng)該放到哪里呢？

我們來看一下這個二分查找遮糖，它幫我們解決了這個小問題绣的。

public static int search(int[] arr, int size, int target) {
    int lo = 0;
    int hi = size - 1;

    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1;
        final int value = arr[mid];

        if (value == target) {
            return mid;
        } else if (value > target) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    return ~lo;
}

按照傳統(tǒng)的思想，查找類的API，如果找不到屡江，一般都會返回-1芭概，但是這個二分查找，返回了lo的取反惩嘉。這會達(dá)到什么效果呢罢洲。

情況1：數(shù)組是空的，那么查找任何東西文黎，都找不到惹苗，那會怎么樣？根據(jù)代碼可以知道耸峭，循環(huán)都進不去桩蓉，那么直接返回了~0，也就是最大的負(fù)數(shù)劳闹。我們只需要知道它是一個負(fù)數(shù)院究。

情況2：數(shù)組不是空的，比如1, 3, 5本涕，我們找2业汰，這里簡單的單步執(zhí)行一下：

lo = 0, size = 3, hi = 2, 好，進入循環(huán)
mid = (0 + 2) / 2 = 1, value = 3
value > 2, 所以 hi = 1 - 1 = 0, 再次循環(huán)
mid = (0 + 0)  / 2 = 0, value = 1
value < 2, so, lo = 0 + 1; 退出循環(huán)
返回~1

如果你在嘗試去驗算其他情況偏友，你會發(fā)現(xiàn)蔬胯，返回值剛好是它應(yīng)該放置的位置的取反。換句話說位他，返回值再取反后，就可以得到产场，這個key應(yīng)該插入的位置鹅髓。

這應(yīng)該是二分查找的一個小技巧。非常的實用京景！

接下來窿冯，想一想，0取反是負(fù)數(shù)确徙，任何正數(shù)取反醒串，也都是負(fù)數(shù)，也就是說鄙皇，只要是負(fù)數(shù)芜赌，就代表沒找到，再將這個數(shù)取反伴逸，就得到了缠沈，應(yīng)該put的位置！

所以，代碼繼續(xù)實現(xiàn)為：

public void put(int key, E value) {
    int i = BinarySearch.search(mKeys, mSize, key);
    if (i >= 0) {
        // 找到了有兩種情況
        // 1.是對應(yīng)的mValues有一個有效的數(shù)據(jù)對象洲愤，直接覆蓋
        // 2.對應(yīng)的mValues里面是一個DELETED對象颓芭，同樣的，直接覆蓋
        mValues[i] = value;
    } else {
        i = ~i;
        mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtil.insert(mValues, mSize, i, value);
        mSize++;
    }
}

實現(xiàn)get方法

接下來柬赐，我們實現(xiàn)get方法亡问。
get方法實現(xiàn)就比較簡單了，只需要通過二分查找找到對應(yīng)的index肛宋，再從value數(shù)組中取出對象即可州藕。

public E get(int key) {
    // 首先查找這個key存不存在
    int i = BinarySearch.search(mKeys, mSize, key);

    if (i < 0) {
        return null;
    } else {
        return (E)mValues[i];
    }
}

實現(xiàn)delete方法

delete方法，就是刪除某個key悼吱，對應(yīng)的細(xì)節(jié)是慎框，找到這個key是否存在，如果存在的話后添，將value數(shù)組中對應(yīng)位置的數(shù)據(jù)設(shè)置為一個常量DELETED笨枯。這樣做的好處就是比較快捷，而不需要真正的去刪除元素遇西。當(dāng)然由于這個DELETED對象存在value數(shù)組中馅精，對put和get以及size方法都會帶來一些影響。

下面的代碼粱檀，定義一個靜態(tài)的final變量DELETED用來作為標(biāo)記已經(jīng)刪除的變量洲敢。
另一個成員變量標(biāo)記，當(dāng)前value數(shù)組中是否有刪除元素這個狀態(tài)信息茄蚯。

private static final Object DELETED = new Object();

/**
 * 標(biāo)記是否有DELETED元素標(biāo)記
 * */
private boolean mHasDELETED = false;

public void delete(int key) {
    // 刪除的時候為標(biāo)記刪除压彭，先要找到是否有這個key，如果沒有渗常，就沒必要刪除了壮不；
    // 找到了key看一下對應(yīng)的value是否已經(jīng)是DELETED，如果是的話皱碘，也沒必要再刪除了
    int i = BinarySearch.search(mKeys, mSize, key);
    if (i >= 0 && mValues[i] != DELETED) {
        mValues[i] = DELETED;
        mHasDELETED = true;
    }
}

實現(xiàn)size方法

size方法返回在這個容器中询一，數(shù)據(jù)對象有多少個。由于DELETED對象的存在癌椿，key數(shù)組和value數(shù)組健蕊，以及成員變量mSize都沒法靠譜得直接得到有效數(shù)據(jù)的count。

因此這里需要一個內(nèi)部的工具方法gc()踢俄，它的作用就是缩功，如果有DELETED對象存在，那么就重新整理一下數(shù)組褪贵，將DELETED對象都移除掂之，數(shù)組中只保留有效數(shù)據(jù)即可抗俄。

先來看gc的實現(xiàn)

private void gc() {

    int placeHere = 0;

    for (int i = 0; i < mSize; i++) {
        Object obj = mValues[i];
        if (obj != DELETED) {

            if (i != placeHere) {
                mKeys[placeHere] = mKeys[i];
                mValues[placeHere] = obj;
                mValues[i] = null;
            }
            placeHere++;
        }

    }

    mHasDELETED = false;
    mSize = placeHere;
}

它的內(nèi)部邏輯很簡單，就是從頭到尾遍歷value數(shù)組世舰，把每一個不是DELETED的對象都重新放置一遍动雹，覆蓋掉前面的DELETED對象。

然后跟压，我們再看一下size的實現(xiàn)

public int size() {
    if (mHasDELETED) {
        gc();
    }
    return mSize;
}

完善get方法

假設(shè)有這樣的一個場景胰蝠，put(1, a), put(2, b), delete(2), get(2)。按照現(xiàn)在的get實現(xiàn)震蒋，就會返回DELETED對象出去茸塞，所以，由于DELETED的存在查剖，我們需要完善一下get方法的邏輯钾虐。

public E get(int key) {
    // 首先查找這個key存不存在
    int i = BinarySearch.search(mKeys, mSize, key);

    // 這里有兩種情況
    // 如果key小于0，說明在mKeys中笋庄，沒有目標(biāo)key效扫，沒找到
    // 如果key大于0，還要看一下直砂，對應(yīng)的mValues中菌仁，是否那個元素是DELETED，因為刪除的時候是標(biāo)記刪除的
    // 以上兩種情況都是沒有找到
    if (i < 0 || mValues[i] == DELETED) {
        return null;
    } else {
        return (E)mValues[i];
    }
}

完善put方法

補充的代碼上面我都寫了注釋静暂，講解了這兩坨額外的代碼是用來處理什么情況的济丘。

public void put(int key, E value) {
    int i = BinarySearch.search(mKeys, mSize, key);
    if (i >= 0) {

        // 找到了有兩種情況
        // 1.是對應(yīng)的mValues有一個有效的數(shù)據(jù)對象，直接覆蓋
        // 2.對應(yīng)的mValues里面是一個DELETED對象洽蛀，同樣的摹迷，直接覆蓋

        mValues[i] = value;
    } else {
        i = ~i;

        // 這一段代碼是處理這一的場景的
        // 1 2 3 5, delete 5, put 4
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        // 另一種情況
        // 如果有刪除的元素，并且數(shù)組裝滿了郊供，這個時候需要先GC泪掀，再重新搜一下key的位置
        if (mHasDELETED && mSize >= mKeys.length) {
            gc();
            i = ~BinarySearch.search(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtil.insert(mValues, mSize, i, value);
        mSize++;
    }
}

最后，GrowingArrayUtil.insert是做了什么颂碘？

其實說起來很簡單，用一個過程來概括一下一般情況椅挣。

[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
insert(index=2, value=99)
1.復(fù)制index=2以前的元素 [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
2.復(fù)制index=2以后的元素头岔，往后挪一位 [1, 2, 3, 3, 4, 5, 0, 0, 0, 0]
3.將index=2的位置，放入99 [1, 2, 99, 3, 4, 5, 0, 0, 0, 0]

當(dāng)然鼠证，這里要處理峡竣，如果剛好數(shù)據(jù)滿了，插入新數(shù)據(jù)量九，就需要創(chuàng)建一個新的适掰，更大的數(shù)組來復(fù)制以前的數(shù)據(jù)了颂碧。

/**
 * @param rawArr 原始數(shù)組
 * @param size 有效數(shù)據(jù)的長度，與數(shù)組長度不一樣类浪，如果數(shù)組長度大于有效數(shù)據(jù)的長度载城，那么往里面插入數(shù)據(jù)是OK的
 *             如果有效數(shù)據(jù)的長度等于數(shù)組的長度，那么要插入數(shù)據(jù)费就，就要創(chuàng)建更大的數(shù)組
 * @param insertIndex 插入index
 * @param insertValue 插入到index的數(shù)值
 * */
public static int[] insert(int[] rawArr, int size, int insertIndex, int insertValue) {
    if (size < rawArr.length) {
        System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex);
        rawArr[insertIndex] = insertValue;
        return rawArr;
    }

    int[] newArr = new int[rawArr.length * 2];
    System.arraycopy(rawArr, 0, newArr, 0, insertIndex);
    newArr[insertIndex] = insertValue;
    System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex);
    return newArr;
}

public static <T> Object[] insert(Object[] rawArr, int size, int insertIndex, T insertValue) {
    if (size < rawArr.length) {
        System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex);
        rawArr[insertIndex] = insertValue;
        return rawArr;
    }

    Object[] newArr = new Object[rawArr.length * 2];
    System.arraycopy(rawArr, 0, newArr, 0, insertIndex);
    newArr[insertIndex] = insertValue;
    System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex);
    return newArr;
}

好了诉瓦，關(guān)于SparseArray的講解就到這里結(jié)束了。完整的源碼可以查看我寫的力细，也可以查看官方的睬澡。

之前提到的一些疑問點

• 為什么用Object[]，而不是T[]
  我的理解是眠蚂，如果使用泛型數(shù)組T[]煞聪，你就必須構(gòu)造出一個泛型數(shù)組，那么構(gòu)造泛型數(shù)組逝慧，你需要能創(chuàng)建泛型對象昔脯，也就是說，必須調(diào)用T的構(gòu)造函數(shù)才能創(chuàng)建泛型對象馋艺，但是由于是泛型栅干，構(gòu)造函數(shù)是不確定的，只能通過反射的形式來調(diào)用捐祠，這樣顯然就效率和穩(wěn)定性上有一些問題碱鳞。因此大多數(shù)泛型的實現(xiàn)，都是通過Object對象來存儲泛型數(shù)據(jù)踱蛀。

如果你覺得這篇內(nèi)容對你有幫助的話窿给，不妨打賞一下，哪怕是小小的一份支持與鼓勵率拒，也會給我?guī)砭薮蟮膭恿Ρ琅荩x謝:)

你的鼓勵是我創(chuàng)作的動力！