1、SparseArray內部使用雙數組，分別存儲Key和Value，Key是int[]，用于查找Value對應的Index，來定位數據在Value中的位置。 2、使用二分查找來定位Key數組中對應值的位置，所以Key數組是有序的。 3、使用數組就面臨刪除數據時數據遷移的問題，所以引入了DELETE標記。 ## 雙數組  mValue數組和mKey數組的關系是一一對應的，通過Key的值，可以定位出該Key在mKey數組中的index，進而可以操作MValue數組中對應位置的數據。 ## 二分查找 ```java 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]; } } ``` SparseArray源碼中，所有和Key有關的操作，第一步都是先通過二分查找，定位出該Key的index，再進行后續處理。 二分查找的前提條件，就是必須是針對有序并且支持下標隨機訪問的數據結構，所以它在執行插入操作的時候，必須保證 mKey 數據中的數據有序。 SparseArray的插入代碼如下： ```java 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++; } } ``` 同樣會使用二分定位查找Key的index，GrowingArrayUtils的insert方法會完成兩個任務： 1、將數據插入到指定數組對應的位置上。 2、如果發現數組空間不夠，就生成一個更大的新數組，將數組通過復制的方式，動態擴容后搬到新數組中，并返回新數組。 ## DELETE標記  對數組的刪除，如果不做數據遷移，數組中必然存在數據空洞，SparseArray引入DELETE標記，來減少刪除數據時對數據的搬運次數。 在插入時，如遇到DELETE標識，標識當前數據已經刪除掉了，直接進行替換，減少一次插入數據帶來的數據搬運。  DELETE標識是在mValue數組中存儲的，mKey中仍然存儲著它上一次對應數據的Key值。在一些必要條件下，會觸發gc()邏輯，來清理數組中的DELETE標識。在gc()方法中，用了一個布爾類型的mGarbage屬性，來記錄當前 mValue 中，是否存在 DELETE 標識，這是判定是否需要 GC 的依據。SparseArray的**所有和 size 相關的操作**以及**和數組擴容相關的操作**時需要進行gc操作。 ## 參考文檔 [https://juejin.im/post/5da1481e6fb9a04de96e8b72](https://juejin.im/post/5da1481e6fb9a04de96e8b72)