SparseArray原理分析
SparseArray 和其他的Android容器類一樣，都是為了更加有效地利用記憶體，說直白點，就是為了節省記憶體。 SparseArray 和 ArrayMap 一樣，都是為了更高效的儲存int值到非原始型別的對映，用了同樣的資料結構，但是為了提高效率， SparseArray 也做了自己的優化。接下來就分析一下 SparseArray 的儲存，新增和刪除元素。
繼承結構
上圖表明，```SparseArray```並沒有像```ArrayMap```一樣實現```Map```介面，僅僅實現了```Cloneable```介面。 ## **儲存結構**
儲存結構和```ArraySet```以及```ArrayMap```一脈相承，都使用int陣列儲存key值，使用Object陣列儲存物件。不同點在於```mKeys```陣列中儲存的是新增元素的key值本身，沒有進行hash值得計算。
put
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
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++;
}
}
複製程式碼
put 方法首先使用二分查詢在 mKeys 中查詢 key ，如果找到，則直接更新對應下標的 value 。如果未找到， binarySearch 方法返回待插入的下標的取反，故 i = ~i 。如果待插入的位置的元素已經被標記為 DELETED ，則直接更新並返回。如果需要執行 gc 函式，且需要擴大陣列的容量（ mSize >= mKeys.lengt ），則先執行 gc 函式。由於執行 gc 函式之後元素會發生移動，故重新計算待插入位置，最後執行元素的插入。插入函式分為插入 key 和插入 value 。 GrowingArrayUtils.insert 的原始碼如下：
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
複製程式碼
函式的邏輯很簡單，首先斷言了 currentSize <= array.length ；如果 array 在不需要擴大容量的情況下可以新增一個元素，則先將待插入位置 index 開始的元素整體後移一位，然後插入元素，否則先擴容，然後將元素拷貝到新的陣列中。
刪除
為什麼刪除的時候我沒有使用一個具體的函式呢，是因為 SparseArray 的刪除有兩種：根據key刪除物件，刪除指定位置的物件。
根據key刪除物件
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
複製程式碼
ContainerHelpers.binarySearch 函式在 ArraySet 和 ArrayMap 的元素查詢中都出現過，作用是使用二分查詢，在 mKeys 中找到 key 的位置，如果 key 存在，則返回 key 在 mKeys 中的下標，否則返回試圖將 key 插入到 mKeys 中的位置的取反。找到待刪除元素的下標後， SparseArray 並沒有像 ArraySet 和 ArrayMap 一樣去刪除元素，只是將待刪除元素標記為 DELETED ，然後將 mGarbage 設定為 true 。 DELETED 實際上就是一個物件，具體申明為： Object DELETED = new Object() ， SparseArray 有 gc 的過程，後面會分析這個 gc 的過程。
刪除執行位置的物件
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
複製程式碼
刪除指定位置元素的邏輯比較簡單，判斷待刪除位置的元素是否已經被標記為 DELETED ，如果沒有被標記，則標記指定位置的元素，並將 mGarbage 設定為 true 。
元素在被刪除之後，都會將標誌 mGarbage 設定為 true ，這是執行 gc 的必要條件。
gc
說到gc，給我的第一感覺應該是什麼高深的c/c++原始碼，其實不是，貼上 gc 的原始碼
private void gc() {
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;
}
複製程式碼
好吧，開始被自己給嚇著了， gc 函式沒有那麼複雜。 gc 函式實際上就是將 mValues 陣列中還未標記為 DELETED 的元素以及對應下標的 mKeys 陣列中的元素移動到陣列的前面，保證陣列在0到 mSize 之間的元素都是未被標記為 DELETED ，經過 gc 之後，資料的位置可能會發生移動。
在元素被刪除後，標誌 mGarbage 設定為 true ，表示可以執行 gc 函數了。那麼 gc 函式會在什麼位置執行呢？ 分析 SparseArray 原始碼可以發現，如果 mGarbage 設定為 true ，在以下函式呼叫中 gc 函式會執行：
put , append , size , keyAt , valueAt , setValueAt , indexOfKey , indexOfValue , indexOfValueByValue
將以上函式總結一下可以歸納為三類：
- 向SparseArray新增元素
- 修改SparseArray的mValues陣列
- 獲取SparseArray的屬性
通過執行 gc 將未被標記為 DELETED 的元素前移，在進行元素查詢時可以減少需要查詢的元素的數量，減少查詢的時間，在新增元素的時候也可以更加快速的找到待插入點。
總結
SparseArray 主要是為了優化 int 值到 Object 對映的儲存，提高記憶體的使用效率。相較於 HashMap ，在儲存上的優化如下：
- 使用int和Object型別的陣列分別儲存key和value，相較於
HashMap使用Node，SparseArray在儲存單個key-value時更節省記憶體 -
SparseArray使用int陣列儲存int型別的key，避免了int到Integer的自動裝箱機制
雖然在儲存int到Object對映時的記憶體使用效率更高，由於使用陣列儲存陣列，在新增或者刪除元素時需要進行二分查詢，元素較多（超過1000）時效率較低，谷歌給出的建議是資料量不要超過1000，這種情況下，相較於 HashMap ,效率降低不會超過50%。