2020-03-01-Android的SparseArray原理

上一次介紹了HashMap的原理，HashMap采用一維數(shù)組+單鏈表+二叉樹的數(shù)據(jù)結(jié)構(gòu)疮方。今天看下android對map類型的優(yōu)化拄显，SparseArray的原理。在沒有hash沖突的情況下HashMap那種桶排序的算法查找速度應(yīng)該是最快的案站，缺點(diǎn)是在數(shù)據(jù)量較少時，內(nèi)存的利用率不高棘街，而SparseArray在數(shù)據(jù)沖突的時候可能會進(jìn)行垃圾回收蟆盐，提高了內(nèi)存利用率。

SparseArray原理.jpg

成員變量和構(gòu)造函數(shù)

首先看下成員變量遭殉，可以看到有兩個一維數(shù)組石挂，mKeys和mValues。SparseArray限定了key的類型是int基本類型险污。

    @UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int)
    private int[] mKeys;
    @UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E)
    private Object[] mValues;
    @UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
    private int mSize;

接下來看構(gòu)造函數(shù)痹愚，默認(rèn)情況下初始容量是0，初始沒有數(shù)據(jù)的情況下是不需要額外分配內(nèi)存的蛔糯。

    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;
    }

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

看看put方法插入一個數(shù)據(jù)的過程拯腮，這里重要的是二分查找，獲取key的索引位置蚁飒。

    public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//1

        if (i >= 0) {
            mValues[i] = value;//2
        } else {
            i = ~i;//3

            if (i < mSize && mValues[i] == DELETED) {//4
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                gc();//5

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);//6
            }
            //7
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

1.通過二分查找方法找到該key值所在的索引位置动壤；
2.如果該key值已經(jīng)存在，直接替換該位置的value淮逻；
3.如果該key不存在琼懊，對二分查找返回的位置i取反，這里取反的原因待會看看binarySearch方法爬早；
4.如果應(yīng)該插入的索引位置value=DELETED狀態(tài)哼丈，直接插入該位置，覆蓋原來的key和value筛严；
5.如果該索引位置已經(jīng)有元素醉旦，且當(dāng)前數(shù)組已滿，執(zhí)行g(shù)c方法回收DELETED的位置脑漫；
6.重新通過二分查找方法找到key應(yīng)該存放的位置髓抑，并取反；
7.通過GrowingArrayUtils.insert方法插入元素优幸。

二分查找

接下來看看二分查找方法：

    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;//1
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present//2
    }

1.每次對索引做除2運(yùn)算吨拍，所以每次查找的位置是n/2，n/4网杆，n/8羹饰，最后是n/(2^k)伊滋，k是n的對數(shù)，查找時間復(fù)雜度是O(log n)队秩。
2.如果找不到該元素笑旺，返回當(dāng)前查找位置的反碼。
注意計(jì)算機(jī)保存的是二進(jìn)制的補(bǔ)碼馍资，所以這里取反并不是直接對原碼取反筒主，而是補(bǔ)碼。比如lo=4鸟蟹，原碼和補(bǔ)碼都是0100乌妙，取反后變成1011，如果要輸出建钥，就需要將補(bǔ)碼轉(zhuǎn)換成原碼藤韵，先減1，變成1010熊经，然后對非符號位取反泽艘，變成1101，得到的結(jié)果是-5镐依。

垃圾回收

接下來看看gc方法：

    private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        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) {//1
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }
        //2
        mGarbage = false;
        mSize = o;

        // Log.e("SparseArray", "gc end with " + mSize);
    }

1.遍歷數(shù)組匹涮，如果元素不是DELETED狀態(tài)，就將元素移動到values[o]位置馋吗，將原來values[i]位置設(shè)置為null焕盟。
2.最后將垃圾回收標(biāo)志設(shè)置為false，數(shù)組容量更新為有效元素個數(shù)宏粤。

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

看完了查找和垃圾回收脚翘，最后看一下數(shù)據(jù)插入的過程：

    public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
        assert currentSize <= array.length;

        if (currentSize + 1 <= array.length) {//1
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        @SuppressWarnings("unchecked")
        T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
                growSize(currentSize));//2
        System.arraycopy(array, 0, newArray, 0, index);//3
        newArray[index] = element;//4
        System.arraycopy(array, index, newArray, index + 1, array.length - index);//5
        return newArray;//6
    }

1.如果當(dāng)前數(shù)組有空位，即容量大于實(shí)際元素個數(shù)绍哎，將index及以后的數(shù)據(jù)后移一位来农，在原來的index位置插入新數(shù)據(jù)；
2.如果當(dāng)前數(shù)組沒有空余容量崇堰，先對數(shù)組進(jìn)行擴(kuò)容沃于；
3.將原來數(shù)組index之前的元素復(fù)制到新數(shù)組中；
4.將新數(shù)據(jù)插入index位置海诲；
5.將原來數(shù)組index以及之后的數(shù)據(jù)復(fù)制到新數(shù)組中繁莹；
6.返回新數(shù)組。

數(shù)據(jù)獲取過程

數(shù)據(jù)獲取就是一個簡單的二分查找過程特幔，上面已經(jīng)分析過咨演，這里就不介紹了。

    public E get(int key) {
        return get(key, null);
    }
    public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }

參考：

https://juejin.im/entry/57c3e8c48ac24700634bd3cf
https://blog.csdn.net/weixin_34008933/article/details/91397619