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)