## 简介 SparseArray，Android推荐我们使用它用来替代**HashMap** ,这样更加节省内存空间的使用。 SparseArray内部由两个数组组成，一个是int\[\]类型的mKeys，用来存放所有的键；另一个是Object\[\]类型的mValues，用来存放所有的值。  最常见的是拿SparseArray跟HashMap来做对比，由于SparseArray内部组成是两个数组，所以占用内存比HashMap要小。我们都知道，增删改查等操作都首先需要找到相应的键值对，而SparseArray**内部是通过二分查找来寻址**的，效率很明显要低于HashMap的常数级别的时间复杂度。提到二分查找，这里还需要提一下的是二分查找的前提是数组已经是排好序的，没错，SparseArray中就是**按照key进行升序排列的**。 综合起来来说，SparseArray所占空间优于HashMap，而效率低于HashMap，是典型的时间换空间，适合较小容量的存储 ## 核心成员变量 ~~~ //保存key的数组 private int[] mKeys; //保存value的数组 private Object[] mValues //大小 private int mSize; ~~~ ## 构造函数 ~~~ public SparseArray() { this(10); } public SparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } mSize = 0; } ~~~ 构造函数做就是根据initialCapacity初始化mValues和mKeys ## put ~~~ public void put(int key, E value) { //使用二分查找在key的位置 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; } //mGarbage大概意思是是否存在被删除的元素(垃圾) //mSize >= mKeys.length 表示满了 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++; } } ///其实是把被删除的元素删除，其他元素向上挤,争取腾出位置 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; } ~~~ ## get ~~~ 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]; } ~~~ get的亮点不多，就是一个二分查找找到index，然后返回value ## remove ~~~ public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } } ~~~