一.SparseArray概述
SparseArray是Android特有的API，Java中沒有此類荞膘，此類為Java容器中HashMap<Integer, E>的替代版本。相比于Java的HashMap，此類的優(yōu)點是更加節(jié)省內(nèi)存
二.SparseArray與HashMap的數(shù)據(jù)結(jié)構(gòu)對比
1.HashMap:
是數(shù)組和鏈表或者紅黑樹的結(jié)合體（至于具體什么時候是鏈表什么時候是紅黑樹以及HashMap的具體原理卿啡，這里就不再展開）昔瞧，下圖是HashMap的數(shù)據(jù)結(jié)構(gòu)：
hashmap.png
2.SparseArray:
是單純的數(shù)組組合指蚁，通過key來映射數(shù)組下標(biāo)index，再通過數(shù)組下標(biāo)在value數(shù)組里查找自晰，下圖是SparseArray的數(shù)據(jù)結(jié)構(gòu)：
sparsearray.png
下面來看看SparseArray的源碼：
數(shù)據(jù)結(jié)構(gòu)
private int[] mKeys;
private Object[] mValues;
private int mSize;
二分查找函數(shù)
// This is Arrays.binarySearch(), but doesn't do any argument validation.
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];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
put函數(shù)
/**
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
// 使用二分查找相應(yīng)的key凝化，成功返回數(shù)組的下標(biāo)，失敗返回查找的最后一個位置的index再取反缀磕，之后插入新的數(shù)據(jù)是根據(jù)次數(shù)插入
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 如果index大于0缘圈，表示查找成功，則更新相應(yīng)的value
mValues[i] = value;
} else {
i = ~i;
// 特殊的case袜蚕，直接存
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
get函數(shù)
/**
* Gets the Object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
public E get(int key) {
return get(key, null);
}
/**
* Gets the Object mapped from the specified key, or the specified Object
* if no such mapping has been made.
*/
@SuppressWarnings("unchecked")
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];
}
}
delete函數(shù)
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 標(biāo)記i的值為 DELETED
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
// 設(shè)置gc標(biāo)記為true
mGarbage = true;
}
}
}
gc函數(shù)
// 遍歷一遍數(shù)組,將非DELETED資源全部移動到數(shù)組前面
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) {
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
總結(jié)
SparseArray的實現(xiàn)主要是使用兩個數(shù)組，一個來存儲key绢涡，另一個存儲value牲剃，兩者之間是通過index值來映射；增刪查改操作主要都是使用復(fù)雜度為O（logn）的二分查找來找到對應(yīng)的index再進行相應(yīng)的操作雄可。
