SparseArray、ArrayMap 實現原理學習

SparseArray源碼來自：android 25/java/util/SparseArray ArrayMap源碼來自：25.3.1/support compat 25.3.1/android/android.support.v4.util.ArrayMap 一、SparseArray實現源碼學 ...

SparseArray源碼來自：android-25/java/util/SparseArray
ArrayMap源碼來自：25.3.1/support-compat-25.3.1/android/android.support.v4.util.ArrayMap

一、SparseArray實現源碼學習

SparseArray採用時間換取空間的方式來提高手機App的運行效率，這也是其與HashMap的區別；HashMap通過空間換取時間，查找迅速；HashMap中當table數組中內容達到總容量0.75時，則擴展為當前容量的兩倍，關於HashMap可查看HashMap實現原理學習)

SparseArray的key為int，value為Object。
在Android中，數據長度小於千時，用於替換HashMap
相比與HashMap，其採用時間換空間的方式，使用更少的記憶體來提高手機APP的運行效率(HashMap中當table數組中內容達到總容量0.75時，則擴展為當前容量的兩倍，關於HashMap可查看HashMap實現原理學習)

這裡寫圖片描述

下邊對其源碼進行簡單學習。

1、構造方法

// 構造方法
public SparseArray() {
    this(10);
}

// 構造方法
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        // key value各自為一個數組，預設長度為10
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

ps：
SparseArray構造方法中，創建了兩個數組mKeys、mValues分別存放int與Object，其預設長度為10

2、 put(int key, E value)

public void put(int key, E value) {
        // 二分查找,key在mKeys列表中對應的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 如果找到，則直接賦值
        if (i >= 0) {
            mValues[i] = value;
        } 
        // 找不到
        else {
            // binarySearch方法中，找不到時，i取了其非，這裡再次取非，則非非則正
            i = ~i;
            // 如果該位置的數據正好被刪除,則賦值
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            // 如果有數據被刪除了，則gc
            if (mGarbage && mSize >= mKeys.length) {
                gc();
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 插入數據，增長mKeys與mValues列表
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
}

ps：

因為key為int,不存在hash衝突
mKeys為有序列表，通過二分查找，找到要插入的key對應的index (這裡相對於查找hash表應該算是費時間吧，但節省了記憶體，所以是時間換取了空間)
通過二分查找到的index，將Value插入到mValues數組的對應位置

3、get(int key)

// 通過key查找對應的value
public E get(int key) {
        return get(key, null);
}
// 通過key查找對應的value
public E get(int key, E valueIfKeyNotFound) {
        // mKeys數組中採用二分查找，找到key對應的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 沒有找到，則返回空
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
        // 找到則返回對應的value
            return (E) mValues[i];
        }
}

ps：
每次調用get，則需經過一次mKeys數組的二分查找，因此mKeys數組越大則二分查找的時間就越長，因此SparseArray在大量數據，千以上時，會效率較低

3、ContainerHelpers.binarySearch(mKeys, mSize, key)二分查找

// array為有序數組
// size數組中內容長度
// value要查找的值
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];
            // 如果中間元素小於要查找元素，則midIndex賦值給 lo 
            if (midVal < value) {
                lo = mid + 1;
            }
            // 如果中間元素大於要查找元素，則midIndex賦值給 hi  
            else if (midVal > value) {
                hi = mid - 1;
            }
            // 找到則返回 
            else {
                return mid;  // value found
            }
        }
        // 找不到,則lo 取非
        return ~lo;  // value not present
}

二、android.support.v4.util.ArrayMap

ArrayMap和SparseArray有點類似；其中含有兩個數組，一個是mHashes（key的hash值數組，為一個有序數組），另一個數組存儲的是key和value，其中key和value是成對出現的，key存儲在數組的偶數位上，value存儲在數組的奇數位上。

這裡寫圖片描述

1、構造方法

public SimpleArrayMap() {
     // key的hash值數組，為一個有序數組
     mHashes = ContainerHelpers.EMPTY_INTS;
     // key 與 value數組
     mArray = ContainerHelpers.EMPTY_OBJECTS;
     mSize = 0;
}

ps：
構造方法中初始化了兩個數組mHashes、mArray，其中mHashes為key的Hash值對應的數組

2、put(K key, V value)

public V put(K key, V value) {
        // key 對應的hash值
        final int hash;
        // hash對應的mHashes列表的index
        int index;
        // key為空，hash為0
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        }
        //  
        else {
            // 計算key的hashcode
            hash = key.hashCode();
            // 查找key對應mHashes中的index,大於0則找到了，否則為未找到
            // 這裡涉及到hash衝突,如果hash衝突，則在index的相鄰位置插入數據
            index = indexOf(key, hash);
        }
        // 找到key對應mHashes中的index
        if (index >= 0) {
            // 取出基數位置原有的Value
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            // 將新數據放到基數index位置
            mArray[index] = value;
            return old;
        }
        // indexOf中取了反，這裡反反則正
        index = ~index;
        // 如果滿了就擴容  
        if (mSize >= mHashes.length) {
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            // 擴容
            allocArrays(n);
            // 把原來的數據拷貝到擴容後的數組中  
            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }
            freeArrays(ohashes, oarray, mSize);
        }
        // 根據上面的二分法查找，如果index小於mSize，說明新的數據是插入到數組之間index位置，插入之前需要把後面的移位  
        if (index < mSize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }
        // 保存數據
        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
}

// 根據key 與key的hash，查找key對應的index
int indexOf(Object key, int hash) {
        final int N = mSize;
        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }
        // 二分查找mHashes有序數組，查找hash對應的index
        int index = ContainerHelpers.binarySearch(mHashes, N, hash);
        // 沒有找到
        if (index < 0) {
            return index;
        }
        // 偶數位為對應的key，則找到了
        if (key.equals(mArray[index<<1])) {
            return index;
        }
        // index之後查找
        // 這裡涉及到hash衝突,如果hash衝突，則在index的相鄰位置插入數據
        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }
        // index之前查找
        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) return i;
        }
        // 沒有找到
        return ~end;
}

SparseArray、ArrayMap 實現原理學習

一、SparseArray實現源碼學習

1、構造方法

2、 put(int key, E value)

3、get(int key)

3、ContainerHelpers.binarySearch(mKeys, mSize, key)二分查找

二、android.support.v4.util.ArrayMap

1、構造方法

2、put(K key, V value)

========== THE END ==========