前言

SparseArray是安卓特有的一種數(shù)據(jù)結(jié)構(gòu)，跟HashMap相似，都是存儲(chǔ)<Key,Value>的實(shí)體。但是SparseArray的Key只能是Int類型的。在存儲(chǔ)的時(shí)候Key按照順序進(jìn)行了排序，當(dāng)查詢的時(shí)候采用了二分查找法來(lái)定位位置。這種方式相對(duì)來(lái)說(shuō)更加迅速

變量

private boolean mGarbage = false;//是否可以進(jìn)行回收，也就是進(jìn)行key，value的整理

private int[] mKeys;//存儲(chǔ)的key值

private Object[] mValues;//存儲(chǔ)的value值

private int mSize; //數(shù)組的大小

可以看到，對(duì)于key和value的存儲(chǔ)，是分別存儲(chǔ)在兩個(gè)不同的數(shù)組中的。而且key的類型是int，而不是封裝后的Integer。

這里面有個(gè) mGarbage 變量，它標(biāo)志著我們當(dāng)前的數(shù)據(jù)是否可以進(jìn)行數(shù)據(jù)的整理工作。比如說(shuō)，當(dāng)我們移除某個(gè)key以后，會(huì)將這個(gè)標(biāo)志位設(shè)置為true，在需要的時(shí)候（比如說(shuō)我們要進(jìn)行數(shù)據(jù)的存儲(chǔ)），會(huì)根據(jù)這個(gè)標(biāo)志位進(jìn)行一次數(shù)組的整理工作。

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

public SparseArray() {
    //默認(rèn)數(shù)組的大小是10
    this(10);
}

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

從構(gòu)造函數(shù)可以看出來(lái)，SparseArray的數(shù)組 默認(rèn)大小是10 ，如果我們?cè)趯?shí)際的使用過(guò)程中能夠確定要保存的數(shù)據(jù)量的大小，最好直接初始化，這樣就不會(huì)出現(xiàn)擴(kuò)容的問(wèn)題。

源碼分析

添加元素

既然和HashMap相似，那么肯定是有數(shù)據(jù)的增刪改的

    public void put(int key, E value) {
        //通過(guò)ContainerHelpers進(jìn)行二分查找。如果存在則返回key的位置
        // 如果不存在則返回key在數(shù)組中可以存儲(chǔ)的位置i的負(fù)值。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果key已經(jīng)存在，則直接賦值
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //binarySearch 方法的返回值分為兩種情況：
            //1、如果存在對(duì)應(yīng)的 key，則直接返回對(duì)應(yīng)的索引值
            //2、如果不存在對(duì)應(yīng)的 key
            //  2.1、假設(shè) mKeys 中存在"值比 key 大且大小與 key 最接近的值的索引"為 presentIndex，則此方法的返回值為 ~presentIndex
            //  2.2、如果 mKeys 中不存在比 key 還要大的值的話，則返回值為 ~mKeys.length
            //可以看到，即使在 mKeys 中不存在目標(biāo) key，但其返回值也指向了應(yīng)該讓 key 存入的位置
            //通過(guò)將計(jì)算出的索引值進(jìn)行 ~ 運(yùn)算，則返回值一定是 0 或者負(fù)數(shù)，從而與“找得到目標(biāo)key的情況（返回值大于0）”的情況區(qū)分開
            //且通過(guò)這種方式來(lái)存放數(shù)據(jù)，可以使得 mKeys 的內(nèi)部值一直是按照值遞增的方式來(lái)排序的
            i = ~i;
            //如果搜索到的i位置可以使用，并且沒(méi)有數(shù)據(jù)，則將對(duì)應(yīng)的key，value存入到i位置
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //如果可以進(jìn)行數(shù)組的整理，并且當(dāng)前的數(shù)組大小能夠進(jìn)行存儲(chǔ)，則進(jìn)行數(shù)據(jù)的整理，然后再進(jìn)行位置的查找
            if (mGarbage && mSize >= mKeys.length) {
                gc();
                // Search again because indices may have changed.
                //GC 后再次進(jìn)行查找，因?yàn)橹悼赡芤呀?jīng)發(fā)生變化了
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //通過(guò)復(fù)制或者擴(kuò)容數(shù)組，將數(shù)據(jù)存放到數(shù)組中
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

這里有個(gè)輔助類 ContainerHelpers ，它的 binarySearch 方法會(huì)根據(jù)實(shí)際情況返回key所對(duì)應(yīng)的位置值

• 如果mKeys數(shù)組中存在key，那么直接返回key所對(duì)應(yīng)的索引值

• 如果mKeys中不存在key

  • key比mKeys中的所有的數(shù)據(jù)都大，則返回~mKeys.length

  • key處于mKeys中的某個(gè)中間位置，則返回那個(gè)值比 key 大且大小與 key 最接近的值的索引。

可以看到，哪怕key在數(shù)組中不存在， binarySearch ，也會(huì)將key保存的最佳位置給返回回來(lái)。

當(dāng)key的位置確定以后，會(huì)根據(jù)情況進(jìn)行數(shù)組的重新編排，重新編排的話，當(dāng)前的key和value在數(shù)組中的位置就會(huì)發(fā)生變化，所以會(huì)調(diào)用 binarySearch 重新獲取適合的插入位置。

最后調(diào)用 GrowingArrayUtils.insert 方法進(jìn)行數(shù)據(jù)的插入。

這個(gè)方法會(huì)判斷當(dāng)前的數(shù)組大小是否能夠繼續(xù)插入key，如果不可以的話，會(huì)進(jìn)行擴(kuò)容。如果可以，會(huì)將i位置以后的數(shù)據(jù)往后移動(dòng)一位，然后將i位置插入我們的key值。

移除元素

移除元素的函數(shù)有多個(gè)，我們一個(gè)個(gè)來(lái)看。

    public void remove(int key) {
        delete(key);
    }
    public void delete(int key) {
        //通過(guò)二分查找，獲取key所在位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            //將所在位置的value設(shè)置為DELETED,然后標(biāo)記需要進(jìn)行整理。
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
    public E removeReturnOld(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            //如果key所在的index的值不為DELETED，則返回?cái)?shù)據(jù)，并標(biāo)記對(duì)應(yīng)index的值為DELETED，
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
    //刪除指定索引對(duì)應(yīng)的元素值
    public void removeAt(int index) {
        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

可以看到，不管哪種remove方法。實(shí)際的移除操作，只是把key所在的位置的value值設(shè)置為了 DELETED ，然后設(shè)置了 mGrabage 標(biāo)志位。并沒(méi)有進(jìn)行key數(shù)組和value數(shù)組的移動(dòng)操作。

查找元素

    public E get(int key) {
        return get(key, null);
    }

    //獲取指定key的值，如果獲取不到，則返回指定對(duì)象。
    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        //獲取key對(duì)應(yīng)的index位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果不存在，或者i位置的數(shù)據(jù)已經(jīng)回收了，則直接返回
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }
    public E valueAt(int index) {
        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (mGarbage) {
            gc();
        }
        return (E) mValues[index];
    }
    //根據(jù)value值，獲取其對(duì)應(yīng)的index信息
    public int indexOfValue(E value) {
        if (mGarbage) {
            gc();
        }
        for (int i = 0; i < mSize; i++) {
            if (mValues[i] == value) {
                return i;
            }
        }
        return -1;
    }

查找方法有的返回的是key所對(duì)應(yīng)的的信息，有的是獲取index信息。這里面進(jìn)行了區(qū)分操作。因?yàn)槿绻皇歉鶕?jù)key值獲取value值的話，不需要進(jìn)行數(shù)組的整理工作。而一旦涉及到了index的查找工作，那么就需要根據(jù) mGrabage 先進(jìn)行一次整理工作，然后才能進(jìn)行index的相關(guān)處理。

垃圾回收

SparseArray的垃圾回收并不是我們平時(shí)所理解的JVM的垃圾回收，只是因?yàn)楫?dāng)我們進(jìn)行移除value的情況下，并沒(méi)有進(jìn)行數(shù)據(jù)的移除，只是設(shè)置了 mGrabage ，而且將對(duì)應(yīng)位置的value設(shè)置為了 DELETED 來(lái)表示當(dāng)前位置是可以回收的。所以當(dāng)我們需要適應(yīng)索引時(shí)，就會(huì)出現(xiàn)索引無(wú)效的問(wèn)題。所以需要通過(guò)垃圾回收來(lái)進(jìn)行數(shù)組的整理，將數(shù)組整理為連續(xù)的數(shù)據(jù)。

    //用于移除無(wú)用的引用，通過(guò)移動(dòng)，將現(xiàn)在所有的key和value連續(xù)保存到數(shù)組中，而不會(huì)使某個(gè)位置的value為空
    //而且會(huì)將mSize賦值為實(shí)際使用的大小
    private void gc() {
        int n = mSize;
        //o 值用于表示 GC 后的元素個(gè)數(shù)
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            //如果value不是DELETED，證明當(dāng)前的位置數(shù)據(jù)是可用的
            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
                o++;
            }
        }
        mGarbage = false;
        mSize = o;
    }

優(yōu)劣

優(yōu)勢(shì)

• 使用int類型作為key，避免了裝箱拆箱操作
• 延遲了垃圾回收時(shí)機(jī)，只在需要的時(shí)候才進(jìn)行一次回收
• 和Map每個(gè)存儲(chǔ)節(jié)點(diǎn)都是一個(gè)類對(duì)象不同，SparseArray不需要用于包裝的結(jié)構(gòu)體，單個(gè)元素存儲(chǔ)成本更低廉
• 在小數(shù)據(jù)量下，二分查找效率更高一些。

劣勢(shì)

• 插入新元素會(huì)導(dǎo)致大量的數(shù)組移動(dòng)
• 數(shù)據(jù)量較大時(shí)，二分查找效率會(huì)變低

本文由 開了肯 發(fā)布！

同步公眾號(hào)[開了肯]