SparseArray家族 SparseArray基於鍵值對存儲數據，key為int，value為object，簡單使用如下： //聲明 SparseArray<String> sparseArray= new SparseArray<>(); //增加元素，append方式 sparseArray ...
SparseArray家族
SparseArray基於鍵值對存儲數據，key為int，value為object，簡單使用如下：
//聲明
SparseArray<String> sparseArray= new SparseArray<>();
//增加元素，append方式
sparseArray.append(0, "myValue");
//增加元素，put方式
sparseArray.put(1, "myValue");
//刪除元素，二者等同
sparseArray.remove(1);
sparseArray.delete(1);
//修改元素，put或者append相同的key值即可
sparseArray.put(1,"newValue");
sparseArray.append(1,"newValue");
//查找，遍歷方式1
for(int i=0;i<sparseArray.size();i++){
Log.d(TAG,sparseArray.valueAt(i));
}
//查找，遍歷方式2
for(int i=0;i<sparseArray.size();i++){
int key = sparseArray.keyAt(i);
Log.d(TAG,sparseArray.get(key));
}
LongSparseArray 和SparseArray 相比，唯一的不同就是key值為long，所以LongSparseArray可以存儲的數據元素就比SparseArray多，int的範圍是-2^31 到 231-1，而long是-263 到 2^63-1。
SparseBooleanArray，SparseIntArray，SparseLongArray，這三個數據結構的key值的類型也是int，value值的類型也固定，SparseBooleanArray的value固定為boolean類型，SparseIntArray的value固定為int類型，SparseLongArray的value固定為long類型。
總結一下這四種數據結構的key，value類型：
SparseArray <int, Object>
LongSparseArray <long, Object>
SparseBooleanArray <int, boolean>
SparseIntArray <int, int>
SparseLongArray <int, long>
上述四種數據結構的key類型都是int，而不是Integer，相較於使用HashMap的話，省去了裝箱拆箱過程，查詢、存儲等操作效率更高，而且int的存儲開銷也遠小於Integer。
SparseArray實現原理
SparseArray內部的重要屬性：
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
}
DELETED
static final 的一個靜態Object實例，當一個鍵值對被remove後，會在對應key的value下放置該對象，標記該元素已經被刪除，只是標記刪除，沒有真正的刪除。
mGarbage
當值為true，標誌數據結構中有元素被刪除，可以觸發gc對無效數據進行回收，真正刪除。
mKeys
用於存放Key的數組，通過int[] 進行存儲，與HashMap相比減少了裝箱拆箱的操作，同時一個int只占4位元組；一個重要特點，mKeys的元素是升序排列的，也是基於此，我們才能使用二分查找。
mValues
用於存放與Key對應的Value，通過數組的position 進行映射；如果存放的是int型等，可以用SparseIntArray ，存放的Values也是int數組，性能更高。
mSize
mSize的大小等於數組中mValues的值等於非DELETED的元素個數。
remove方法源碼：
public void delete(int key) {
//查找對應key在數組中的下標，如果存在，返回下標，不存在，返回下標的取反；
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//key存在於mKeys數組中，將元素刪除，用DELETED替換原value，起標記作用；
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
/**
* @hide
* Removes the mapping from the specified key, if there was any, returning the old value.
*/
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage = true;
return old;
}
}
return null;
}
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
二分查找：
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation.
//第一個參數array為keys的數組，第二個為數組中元素個數（與keys的length不一定相等），第三個value為目標的key
static int binarySearch(int[] array, int size, int value) {
//lo為二分查找的左邊界
int lo = 0;
//hi為二分查找的右邊界
int hi = size - 1;
//還沒找到，繼續查找
while (lo <= hi) {
//左邊界+右邊界處以2，獲取到mid 的index
final int mid = (lo + hi) >>> 1;
//獲取中間元素
final int midVal = array[mid];
// 目標key在右部分 。。。。感覺這部分太簡單了
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
//相等，找到了，返回key對應在array的下標；
return mid; // value found
}
}
//沒有找到該元素，對lo取反！！！！！很重要
return ~lo; // value not present
}
該方法是通過二分查找返回了當前key的對應於mKeys數組的下標，如果沒有找到，就返回一個特殊的負數。二分法返回的數值如果非負數，我們則對其所對應的value進行替換成DELETED，用於標記該key已經被刪除，但是key仍然存在於mKeys數組，因此刪除是一個偽刪除同時，我們將garbage賦值true，代表數組中可能存在垃圾。
put方法源碼：
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//原來已經有key，可能是remove後，value存放著DELETED，也可能是存放舊值，那麼就替換
if (i >= 0) {
mValues[i] = value;
} else {
//沒有找到，對i取反，得到i= lo（ContainerHelpers.binarySearch）
i = ~i;
//如果i小於數組長度，且mValues==DELETED(i對應的Key被延遲刪除了)
if (i < mSize && mValues[i] == DELETED) {
//直接取代，實現真實刪除原鍵值對
mKeys[i] = key;
mValues[i] = value;
return;
}
//數組中可能存在延遲刪除元素且當前數組長度滿，無法添加
if (mGarbage && mSize >= mKeys.length) {
//真實刪除，將所有延遲刪除的元素從數組中清除；
gc();
//清除後重新確定當前key在數組中的目標位置；
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//不存在垃圾或者當前數組仍然可以繼續添加元素，不需要擴容，則將i之後的元素全部後移，數組中仍然存在被DELETED的垃圾key；
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
//新元素添加成功，潛在可用元素數量+1
mSize++;
}
}
put方法也調用了ContainerHelpers.binarySearch方法先進行查找，查找到大於0，則在數組中找到了對應的key，此時，直接將value進行替換即可；如果沒有找到，返回的是~lo，將i取反後，此時i就是我們需要插入的位置。
此刻，我們找到了i，就是目標位置，如果沒有設置延遲刪除（DELETED），那麼由於數組的特點，我們需要將i序號之後的數組後移，這樣就會產生一個較大的性能損耗；，但是如果我們設置了延遲刪除且mValue[i]上當前的元素恰巧為DELETED,那麼此時我們可以用當前的key替換原來mKeys的key，且用當前value替換DELETED；這樣就成功避免了一次數組的遷移操作。
但是事情不可能永遠湊巧，如果，i上的元素並非恰好被刪除呢？那麼此時我們會判斷mGarbage，如果為true那麼我們執行一次gc，將無效數據移除，再進行一次二分查找，然後將i之後的數據全部後移，將當前key插入；如果mGarbage為false，那麼證明其中的數據全部存在，因此不需要gc，直接進行元素插入並將數組後移。
Get方法源碼：
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];
}
}
與HashMap做比較
1、key類型都是int，而不是Integer，相較於使用HashMap的話，省去了裝箱拆箱過程，查詢、存儲等操作效率更高，而且int的存儲開銷也遠小於Integer
2、使用二分查找法判斷元素的位置，所以，在獲取數據的時候非常快，時間複雜度為O(lgN)，比HashMap快的多，因為HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素。
3、使用場景
雖說SparseArray性能比較好，但是由於其添加、查找、刪除數據都需要先進行一次二分查找，所以在數據量大的情況下性能並不明顯，將降低至少50%。滿足下麵兩個條件我們可以使用SparseArray代替HashMap：
a：數據量不大，最好在千級以內，如果在數據量比較大時，它的性能將退化至少50%。
b：key必須為int類型，這中情況下的HashMap可以用SparseArray代替。
