SparseIntArray、SparseArray、ArrayMap 和 HashMap 的原理分析
前言
Android開發(fā)一般都使用java集合里面的HashMap HashSet等集合API， 但是由于其特殊的需求做數(shù)據(jù)處理的時(shí)候，Android為自身定義了一套自有的API來實(shí)現(xiàn)本身的功能和需求，在android.util 里面有這幾個(gè)類： SparseArray(系列)、ArrayMap、 ArraySet等。
SparseArray的源碼分析
SparseArray（稀疏數(shù)組）是Android框架提供的工具類，用于建立整數(shù)和對(duì)象之間的映射關(guān)系，效果相當(dāng)于HashMap<Integer, Object>。SparseArray內(nèi)部采用了兩個(gè)數(shù)組分別存儲(chǔ)key-value, 尋找key的時(shí)候做二分查找。
1：SparseArray的定義的一些屬性
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
1：DELETE: 所有被刪除的數(shù)據(jù)都會(huì)優(yōu)先指向這個(gè)對(duì)象
2：mGarbage: 是否進(jìn)行空間回收，true ：立即執(zhí)行移除的操作
3：mKeys: 存儲(chǔ)Key的數(shù)組
4：mValues: 存儲(chǔ)value的數(shù)組
5：當(dāng)前元素的數(shù)量（不包含已經(jīng)被標(biāo)記刪除的元素）
2：構(gòu)造方法
public 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;
}
1: SparseArray存在兩個(gè)構(gòu)造方法, 帶參數(shù)的構(gòu)造方法可以指定SparseArray的初始容量，如果使用默認(rèn)的構(gòu)造函數(shù)，那么初始容量為10。
2：當(dāng)初始容量為0的時(shí)候，mkey和mValue都被初始化了EmptyArray常量，避免重復(fù)創(chuàng)建
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
3: 當(dāng)初始容量不為0的時(shí)候，初始化 mValues 數(shù)組時(shí)使用了 ArrayUtils 的 newUnpaddedObjectArray 方法， 這是個(gè)native方法，此方法返回的就是一個(gè)比約定的容量大小大一些的容量。即： 實(shí)際返回的數(shù)組大小有可能比 minLength大，也就是說，如果 minLength 是15，那么實(shí)際返回的數(shù)組大小可能是 16。
3：SparseArray的增：
put 方法用于放入一個(gè)整數(shù)到對(duì)象的映射：
1: binarySearch 二分查找來確定key的位置， 有效長度為mSize
2: 通過二分查找在 mKeys 數(shù)組的 mSize 長度中， 查看 key 是否已經(jīng)存在，如果存在，則直接更新 mValues 數(shù)組中對(duì)應(yīng)位置的值
3：key 不存在，那么將二分查找的返回值取反，得到 key 要插入的位置，檢查該位置的 value 是否標(biāo)記為已刪除，如果是，直接在該位置更新 key 和 value。
4：如果有必要，進(jìn)行一次「垃圾回收」，并更新即將插入的位置（垃圾回收過程數(shù)組元素發(fā)生了移動(dòng)，所以插入位置可能會(huì)變動(dòng)）
5：在 mKeys 和 mValues 數(shù)組中的對(duì)應(yīng)位置分別插入 key 和 value，size 加 1。
為什么將二分查找的返回值按位取反就能得到新元素的位置呢？
如果數(shù)組元素為 [-1,0,1,3,6], 如果數(shù)組元素為 [-1,0,1,3,6]，在使用二分查找法查找元素 5 時(shí)，lo 最后的值是4，也就是元素 5 應(yīng)該在數(shù)組中下標(biāo)為 4 的位置。在經(jīng)過按位取反后，binarySearch 的返回值就是個(gè)負(fù)數(shù)。而在 put 方法中，通過 i = ~i 可以得到這個(gè)位置下標(biāo)，然后執(zhí)行更新或插入即可。
備注： 因?yàn)镵ey[] 和 value[] 初始值為null，所以在進(jìn)行put()操作的時(shí)候， 會(huì)優(yōu)先進(jìn)行一次二分查找進(jìn)行一下定位，那么key[]在進(jìn)行若干次put操作后就是一個(gè)有序的數(shù)組。
4： SparseArray的刪：remove and delete（都是public的類型）
delete方法首先使用二分查找對(duì)應(yīng)的key，取得到了對(duì)應(yīng)的位置，并未立即搬除數(shù)據(jù)，而是把mValues對(duì)應(yīng)位置的元素指向delete， 并將mGarbage設(shè)置為true， 意味著有必要進(jìn)行垃圾回收了，當(dāng)下次垃圾回收的時(shí)候 再統(tǒng)一進(jìn)行元素的搬移操作。
5：SparseArray的查：
直接通過二分查找去查找key是否在mkey數(shù)組中， 如果有則返回mValues數(shù)組中的相同位置的值， 如果沒有或者mValues中對(duì)應(yīng)位置的元素被標(biāo)記為已刪除，就返回默認(rèn)值（沒有默認(rèn)值就返回為null）
SparseArray/ArrayMap 代替HashMap的優(yōu)點(diǎn)
1：SparseArray 相比 HashMap<Integer,Object> 主要做了兩點(diǎn)優(yōu)化：
一是避免了自動(dòng)裝箱過程，
二是去掉了額外的 Entry 包裝對(duì)象
2：SpareArray 內(nèi)部采用了兩個(gè)數(shù)組來分別存儲(chǔ) key 和 value，尋找 key 時(shí)使用了二分查找。不過，也是由于這個(gè)原因，查找效率無法和 HashMap 相比，適用于少量數(shù)據(jù)的情況。
3：ArrayMap系列跟HashMap的映射
SparseArray => HashMap<int, Object>
LongSparseArray => HashMap<long, Object>
SparseBooleanArray => HashMap<int, boolean>
SparseIntArray => HashMap<int, int>
SparseLongArray => HashMap<int, long>
ArrayMap => HashMap
ArraySet => HashSet
