1、SparseArray是android sdk 提供集合類，主要用來替換key 為int類型，value為Object類型的Hashmap

2、SparseArray和HashMap相比優(yōu)缺點：
優(yōu)點：
1、SparseArray存在一個int[]keys, 因此避免自動裝箱
2、SparseArray擴容時只需要數(shù)組拷貝工作（system.arraycopy), 不需要重建哈希表（rehash十分消耗性能）
缺點:
3、SparseArray以時間換空間，由于使用二分查找，時間比hashmap要慢。mkeys數(shù)組的元素總是連續(xù)的（即使中間會存在DELETED元素，但是這些DELETED元素，在后續(xù)的gc()方法中被清除掉），不像hashmap數(shù)組的元素，由于內在的hash沖突無法徹底解決而導致數(shù)組空間利用很浪費。
4、不適合大容量的數(shù)據(jù)存儲。存儲大量數(shù)據(jù)時，他的性能很差，千條數(shù)據(jù)以內可以使用SparseArray
5、按照key進行自然排序
二、全局變量
//用于標記當前是否有待垃圾回收（GC）的元素
private boolean mGarbage = false

key 數(shù)組和value數(shù)組的默認打下是10

 //設置數(shù)組的默認初始容量為10public SparseArray() {this(10);}/*** Creates a new SparseArray containing no mappings that will not* require any additional memory allocation to store the specified* number of mappings.  If you supply an initial capacity of 0, the* sparse array will be initialized with a light-weight representation* not requiring any additional array allocations.*/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;}

添加元素、
主要看put(int key,E value)方法，當中用到了ContainerHelpers類提供binarySearch,用于查找目標key在mKeys中的當前索引或者目標索引
binarySearch方法的返回值分為兩種情況：
1.如果mKeys中存在對應的key,則直接返回對應的索引值
2.如果mKeys中不存在對應的key

2.1  假設mKeys中存在"值比key大且大小與key最接近的值的索引為parseIndex"，則此方法的返回值為~parsentIndex
2.2 如果mKeys中不存在比key還要大的值的話，則返回值~mKeys.length

通過這種方式來存放數(shù)據(jù)，可以使得mKeys的內部值一直是按照遞增的方式來排序的。

//將索引 index 處的元素賦值為 value//SparseArray 的元素值都是存到 mValues 中的，因此如果知道目標位置（index），則可以直接向數(shù)組 mValues 賦值public void setValueAt(int index, E value) {//如果需要則先進行垃圾回收if (mGarbage) {gc();}mValues[index] = value;}/*** Adds a mapping from the specified key to the specified value,* replacing the previous mapping from the specified key if there* was one.*/public void put(int key, E value) {//用二分查找法查找指定 key 在 mKeys 中的索引值int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//找得到則直接賦值if (i >= 0) {mValues[i] = value;} else {//binarySearch 方法的返回值分為兩種情況：//1、如果存在對應的 key，則直接返回對應的索引值//2、如果不存在對應的 key//  2.1、假設 mKeys 中存在"值比 key 大且大小與 key 最接近的值的索引"為 presentIndex，則此方法的返回值為 ~presentIndex//  2.2、如果 mKeys 中不存在比 key 還要大的值的話，則返回值為 ~mKeys.length//可以看到，即使在 mKeys 中不存在目標 key，但其返回值也指向了應該讓 key 存入的位置//通過將計算出的索引值進行 ~ 運算，則返回值一定是 0 或者負數(shù)，從而與“找得到目標key的情況（返回值大于0）”的情況區(qū)分開//且通過這種方式來存放數(shù)據(jù)，可以使得 mKeys 的內部值一直是按照值遞增的方式來排序的i = ~i;//如果目標位置還未賦值，則直接存入數(shù)據(jù)即可，對應的情況是 2.1if (i < mSize && mValues[i] == DELETED) {mKeys[i] = key;mValues[i] = value;return;}//以下操作對應兩種情況：//1、對應 2.1 的一種特殊情況，即目標位置已用于存放其他值了//   此時就需要將從索引 i 開始的所有數(shù)據(jù)向后移動一位，并將 key 存到 mKeys[i]//2、對應的情況是 2.2if (mGarbage && mSize >= mKeys.length) {gc();//GC 后再次進行查找，因為值可能已經(jīng)發(fā)生變化了i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);}//通過復制或者擴容數(shù)組，將數(shù)據(jù)存放到數(shù)組中mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);mSize++;}}//和 put 方法類似//但在存入數(shù)據(jù)前先對數(shù)據(jù)大小進行了判斷，有利于減少對 mKeys 進行二分查找的次數(shù)//所以在“存入的 key 比現(xiàn)有的 mKeys 值都大”的情況下會比 put 方法性能高public void append(int key, E value) {if (mSize != 0 && key <= mKeys[mSize - 1]) {put(key, value);return;}if (mGarbage && mSize >= mKeys.length) {gc();}mKeys = GrowingArrayUtils.append(mKeys, mSize, key);mValues = GrowingArrayUtils.append(mValues, mSize, value);mSize++;}

上文說：布爾變量mGarbage用于標記當前是否有待垃圾回收(GC)的元素，當該值為true時，即意味著當前狀態(tài)需要垃圾回收，回收操作不是立馬進行的，而是在后續(xù)操作中完成。

以下幾個方法在移除元素時，只是切斷mValues中的引用，而mKeys沒進行回收，這個操作gc()進行處理。

 //如果存在 key 對應的元素值，則將其移除public void delete(int key) {//用二分查找法查找指定 key 在 mKeys 中的索引值int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {if (mValues[i] != DELETED) {mValues[i] = DELETED;//標記當前需要進行垃圾回收mGarbage = true;}}}public void remove(int key) {delete(key);}//和 delete 方法基本相同，差別在于會返回 key 對應的元素值public E removeReturnOld(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {if (mValues[i] != DELETED) {final E old = (E) mValues[i];mValues[i] = DELETED;mGarbage = true;return old;}}return null;}//刪除指定索引對應的元素值public void removeAt(int index) {if (mValues[index] != DELETED) {mValues[index] = DELETED;//標記當前需要進行垃圾回收mGarbage = true;}}//刪除從起始索引值 index 開始之后的 size 個元素值public void removeAtRange(int index, int size) {//避免發(fā)生數(shù)組越界的情況final int end = Math.min(mSize, index + size);for (int i = index; i < end; i++) {removeAt(i);}}//移除所有元素值public void clear() {int n = mSize;Object[] values = mValues;for (int i = 0; i < n; i++) {values[i] = null;}mSize = 0;mGarbage = false;}

垃圾回收、
因為SparseArray中可能會出現(xiàn)只移除value和value兩者之一的情況，導致數(shù)組存在無效引用，因此gc()方法就用于移除無效引用，并將有效的元素值位置合在一起

//垃圾回收//因為 SparseArray 中可能出現(xiàn)只移除 value 和 value 兩者之一的情況//所以此方法就用于移除無用的引用private void gc() {int n = mSize;//o 值用于表示 GC 后的元素個數(shù)int o = 0;int[] keys = mKeys;Object[] values = mValues;for (int i = 0; i < n; i++) {Object val = values[i];//元素值非默認值 DELETED ，說明該位置可能需要移動數(shù)據(jù)if (val != DELETED) {//以下代碼片段用于將索引 i 處的值賦值到索引 o 處//所以如果 i == o ，則不需要執(zhí)行代碼了if (i != o) {keys[o] = keys[i];values[o] = val;values[i] = null;}o++;}}mGarbage = false;mSize = o;}