概述

HashMap的查找和插入時間復(fù)雜度為O(1)的代價是犧牲大量的內(nèi)存來實現(xiàn)的，而SparseArray和ArrayMap性能略遜于HashMap，但更節(jié)省內(nèi)存，用時間換取空間。ArrayMap和SparseArray采用的都是兩個數(shù)組，HashMap采用的是數(shù)據(jù)+鏈表+紅黑樹。數(shù)據(jù)長度小于千時，建議取代HashMap。

• SparseArray（<Integer,Value>），SparseBooleanArray（<Integer,Bool>），SparseIntArray，SparseLongArray（<Integer,Long>），LongSparseArray（<Long,Value>）
• ArrayMap、ArraySet
• SparseArray使用兩個數(shù)組，一個保存key，一個保存value。
• ArrayMap兩個數(shù)組, mHashes是一個記錄所有key的hashcode值組成的數(shù)組，是從小到大的排序方式；
  mArray是一個記錄著key-value鍵值對所組成的數(shù)組，是mHashes大小的2倍；
• 二分查找的時間復(fù)雜度O(log n)，大數(shù)據(jù)量的情況下，效率沒有HashMap高

SparseArray原理

SparseArray源代碼很簡單，只有幾百行。

private static final Object DELETED = new Object();//要刪除的value先設(shè)為這個，特定情況下再回收
private boolean mGarbage = false;//標(biāo)記是否有需要回收的
private int[] mKeys;
private Object[] mValues;
private int mSize;

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

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


// array為有序數(shù)組
// size數(shù)組中內(nèi)容長度
// value要查找的值
static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        // 循環(huán)查找
        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
}

參考

深度解讀ArrayMap優(yōu)勢與缺陷
SparseArray、ArrayMap 實現(xiàn)原理學(xué)習(xí)