Android之SparseArray 源碼解析

前言

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

變量

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

private int[] mKeys;//存儲的key值

private Object[] mValues;//存儲的value值

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

可以看到崩侠，對于key和value的存儲，是分別存儲在兩個不同的數(shù)組中的屁柏。而且key的類型是int啦膜，而不是封裝后的Integer。

這里面有個 mGarbage 變量淌喻，它標(biāo)志著我們當(dāng)前的數(shù)據(jù)是否可以進(jìn)行數(shù)據(jù)的整理工作僧家。比如說，當(dāng)我們移除某個key以后裸删，會將這個標(biāo)志位設(shè)置為true八拱，在需要的時候（比如說我們要進(jìn)行數(shù)據(jù)的存儲），會根據(jù)這個標(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ù)可以看出來肌稻，SparseArray的數(shù)組 默認(rèn)大小是10 清蚀，如果我們在實際的使用過程中能夠確定要保存的數(shù)據(jù)量的大小，最好直接初始化爹谭，這樣就不會出現(xiàn)擴容的問題枷邪。

源碼分析

添加元素

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

    public void put(int key, E value) {
        //通過ContainerHelpers進(jìn)行二分查找诺凡。如果存在則返回key的位置
        // 如果不存在則返回key在數(shù)組中可以存儲的位置i的負(fù)值东揣。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果key已經(jīng)存在，則直接賦值
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //binarySearch 方法的返回值分為兩種情況：
            //1腹泌、如果存在對應(yīng)的 key嘶卧，則直接返回對應(yīng)的索引值
            //2、如果不存在對應(yīng)的 key
            //  2.1凉袱、假設(shè) mKeys 中存在"值比 key 大且大小與 key 最接近的值的索引"為 presentIndex芥吟，則此方法的返回值為 ~presentIndex
            //  2.2、如果 mKeys 中不存在比 key 還要大的值的話专甩，則返回值為 ~mKeys.length
            //可以看到钟鸵，即使在 mKeys 中不存在目標(biāo) key，但其返回值也指向了應(yīng)該讓 key 存入的位置
            //通過將計算出的索引值進(jìn)行 ~ 運算配深，則返回值一定是 0 或者負(fù)數(shù)携添，從而與“找得到目標(biāo)key的情況（返回值大于0）”的情況區(qū)分開
            //且通過這種方式來存放數(shù)據(jù)，可以使得 mKeys 的內(nèi)部值一直是按照值遞增的方式來排序的
            i = ~i;
            //如果搜索到的i位置可以使用篓叶，并且沒有數(shù)據(jù)烈掠，則將對應(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)行存儲左敌，則進(jìn)行數(shù)據(jù)的整理，然后再進(jìn)行位置的查找
            if (mGarbage && mSize >= mKeys.length) {
                gc();
                // Search again because indices may have changed.
                //GC 后再次進(jìn)行查找俐镐，因為值可能已經(jīng)發(fā)生變化了
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //通過復(fù)制或者擴容數(shù)組矫限，將數(shù)據(jù)存放到數(shù)組中
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

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

如果mKeys數(shù)組中存在key佩抹，那么直接返回key所對應(yīng)的索引值
如果mKeys中不存在key
- key比mKeys中的所有的數(shù)據(jù)都大叼风，則返回~mKeys.length
- key處于mKeys中的某個中間位置，則返回那個值比 key 大且大小與 key 最接近的值的索引棍苹。

可以看到无宿，哪怕key在數(shù)組中不存在， binarySearch 枢里，也會將key保存的最佳位置給返回回來孽鸡。

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

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

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

移除元素

移除元素的函數(shù)有多個，我們一個個來看尉尾。

    public void remove(int key) {
        delete(key);
    }
    public void delete(int key) {
        //通過二分查找爆阶，獲取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沙咏，則返回數(shù)據(jù)辨图，并標(biāo)記對應(yīng)index的值為DELETED，
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
    //刪除指定索引對應(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方法故河。實際的移除操作，只是把key所在的位置的value值設(shè)置為了 DELETED 吆豹，然后設(shè)置了 mGrabage 標(biāo)志位鱼的。并沒有進(jìn)行key數(shù)組和value數(shù)組的移動操作。

查找元素

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

    //獲取指定key的值痘煤，如果獲取不到凑阶，則返回指定對象。
    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        //獲取key對應(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值，獲取其對應(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所對應(yīng)的的信息蘸拔，有的是獲取index信息师郑。這里面進(jìn)行了區(qū)分操作。因為如果只是根據(jù)key值獲取value值的話调窍，不需要進(jìn)行數(shù)組的整理工作宝冕。而一旦涉及到了index的查找工作，那么就需要根據(jù) mGrabage 先進(jìn)行一次整理工作陨晶，然后才能進(jìn)行index的相關(guān)處理猬仁。

垃圾回收

SparseArray的垃圾回收并不是我們平時所理解的JVM的垃圾回收帝璧，只是因為當(dāng)我們進(jìn)行移除value的情況下，并沒有進(jìn)行數(shù)據(jù)的移除湿刽，只是設(shè)置了 mGrabage 的烁，而且將對應(yīng)位置的value設(shè)置為了 DELETED 來表示當(dāng)前位置是可以回收的。所以當(dāng)我們需要適應(yīng)索引時诈闺，就會出現(xiàn)索引無效的問題渴庆。所以需要通過垃圾回收來進(jìn)行數(shù)組的整理，將數(shù)組整理為連續(xù)的數(shù)據(jù)雅镊。

    //用于移除無用的引用襟雷，通過移動，將現(xiàn)在所有的key和value連續(xù)保存到數(shù)組中仁烹，而不會使某個位置的value為空
    //而且會將mSize賦值為實際使用的大小
    private void gc() {
        int n = mSize;
        //o 值用于表示 GC 后的元素個數(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)勢

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

劣勢

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

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

同步公眾號[開了肯]