## 簡介 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; } } } ~~~