概述
HashMap的查找和插入時間復雜度為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倍侦讨； - 二分查找的時間復雜度O(log n)驶冒，大數(shù)據(jù)量的情況下，效率沒有HashMap高
SparseArray原理
SparseArray源代碼很簡單韵卤，只有幾百行骗污。
private static final Object DELETED = new Object();//要刪除的value先設為這個，特定情況下再回收
private boolean mGarbage = false;//標記是否有需要回收的
private int[] mKeys;
private Object[] mValues;
private int mSize;
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;
// 如果該位置的數(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查找對應的value
public E get(int key) {
return get(key, null);
}
// 通過key查找對應的value
public E get(int key, E valueIfKeyNotFound) {
// mKeys數(shù)組中采用二分查找汗洒，找到key對應的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 沒有找到，則返回空
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
// 找到則返回對應的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
}
