引子
SparseArray是google官方提供的一種int到Object的map，文檔見(jiàn)：SparseArray。
大家都知道Java里已經(jīng)有了非常通用且功能強(qiáng)大的HashMap，那么Google為什么要再發(fā)明個(gè)輪子呢？這個(gè)新輪子相比有什么優(yōu)勢(shì)呢？下面我們先從整體上看下區(qū)別。
區(qū)別何在
從官方文檔描述我們知道此類的引入主要是基于節(jié)省內(nèi)存考慮，因?yàn)楫吘惯\(yùn)行時(shí)是在終端設(shè)備上。說(shuō)它更省內(nèi)存，主要是因?yàn)橄啾菻ashMap，它在實(shí)現(xiàn)上避免了int到Integer的autobox操作，還有每次put操作需要的額外Entry對(duì)象；它的key和value分別存儲(chǔ)在2個(gè)數(shù)組中，get時(shí)使用二分查找來(lái)定位某個(gè)key，不適合大數(shù)據(jù)量的場(chǎng)景比如上千，幾百的量比較合適，刪除操作也比較特殊，僅僅是個(gè)標(biāo)記操作，內(nèi)部也有自己的gc()方法用來(lái)清理壓縮內(nèi)存。接下來(lái)讓我們進(jìn)入正題。
源碼分析
和以往一樣，首先我們來(lái)看看其關(guān)鍵字段和ctor，如下：
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys; // 存放int key的數(shù)組，元素升序排列
private Object[] mValues;
private int mSize;
/**
* Creates a new SparseArray containing no mappings.
*/
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 {
// 分配至少initialCapacity這么大的數(shù)組
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
常量DELETED對(duì)象用來(lái)標(biāo)記刪除，如果某個(gè)位置的值是DELETED則表示這個(gè)位置沒(méi)對(duì)應(yīng)的元素（被刪除了）；
mGarbage在刪除操作中會(huì)被設(shè)置（置為true），表示接下來(lái)需要清理壓縮了（compacting）；
mkeys，mValues分別表示SparseArray的內(nèi)部存儲(chǔ)，即分別是key、value的存儲(chǔ)數(shù)組，mkeys在put操作中會(huì)被保證以升序的方式排列（以便二分查找能夠work）；
mSize表示有效的key-value對(duì)的數(shù)目；
兩個(gè)構(gòu)造函數(shù)比較簡(jiǎn)單明了，無(wú)參版本會(huì)調(diào)用帶參數(shù)的版本并且將初始容量設(shè)為10，我們可以看到如果initialCapacity=0的話，mkeys、mValues會(huì)分別被初始化為EmptyArray里的常量數(shù)組，實(shí)際是長(zhǎng)度為0的數(shù)組，不會(huì)產(chǎn)生內(nèi)存分配；在Android 9.0的設(shè)備上跑無(wú)參的版本，實(shí)際mValues為有11個(gè)元素的數(shù)組（這點(diǎn)細(xì)節(jié)可能跟大多數(shù)人想的不一樣，因?yàn)槠鋵?shí)newUnpaddedObjectArray實(shí)際上會(huì)分配至少initialCapacity個(gè)元素，并不一定剛好等于它）。
最后都設(shè)置了mSize為0，表明當(dāng)前還只是個(gè)剛被創(chuàng)建的空的SparseArray。
接下來(lái)看2個(gè)依據(jù)key來(lái)得到value的方法，即get方法：
/**
* Gets the Object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
public E get(int key) {
return get(key, null);
}
/**
* Gets the Object mapped from the specified key, or the specified Object
* if no such mapping has been made.
*/
@SuppressWarnings("unchecked")
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];
}
}
2個(gè)版本的實(shí)現(xiàn)都很簡(jiǎn)單明了，唯一有趣的點(diǎn)是內(nèi)部的ContainerHelpers.binarySearch(mKeys, mSize, key);這行代碼調(diào)用；
SparseArray內(nèi)部就是通過(guò)此二分查找算法來(lái)search key的，一并看下其實(shí)現(xiàn)：
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
如源碼所說(shuō)，這個(gè)版本和java.util.Arrays.java里的實(shí)現(xiàn)一樣，只是省略了參數(shù)檢查。二分查找大家都接觸過(guò)，看下實(shí)現(xiàn)是不是很眼熟，沒(méi)什么特別的，這里著重說(shuō)下最后沒(méi)找到時(shí)的返回值~lo。如方法的doc所說(shuō)，沒(méi)找到的情況下會(huì)返回一個(gè)負(fù)值，那到底返回哪個(gè)負(fù)值呢，-1行不行？其實(shí)這里的~lo就相當(dāng)于-(lo+1)（參看Arrays.binarySearch的實(shí)現(xiàn)）。為什么要這樣做，因?yàn)槲覀儾粌H想表示沒(méi)找到，還想返回更多信息，即這個(gè)key如果要插進(jìn)來(lái)應(yīng)該在的位置（外面的代碼只需要再次~即取反就可以得到這個(gè)信息）。
接下來(lái)回到剛才的get方法，明白了這里使用的二分查找這個(gè)方法就非常簡(jiǎn)單明了了。get內(nèi)部通過(guò)binarySearch的返回值來(lái)做判斷，如果是負(fù)的或i>=0但是位置i已經(jīng)被標(biāo)記為刪除了則返回valueIfKeyNotFound，否則直接返回(E) mValues[i]。
緊接著來(lái)看一組delete/remove方法：
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { // 元素存在的前提下
// 標(biāo)記刪除法！??！
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
/**
* Removes the mapping at the specified index.
*/
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
/**
* Remove a range of mappings as a batch.
*
* @param index Index to begin at
* @param size Number of mappings to remove
*/
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
delete(key)和remove(key)一樣，都是先通過(guò)二分查找來(lái)找這個(gè)key，如果不存在則do nothing，否則如果這個(gè)位置還沒(méi)被標(biāo)記為刪除則標(biāo)記之，順便設(shè)置mGarbage（之前提到過(guò)刪除之類的操作都會(huì)設(shè)置這個(gè)值，表示接下來(lái)需要執(zhí)行清理壓縮操作了）。注意這里數(shù)組的不同處理，沒(méi)有直接移動(dòng)數(shù)組元素（壓縮處理）來(lái)刪除這個(gè)key，而僅僅是標(biāo)記操作（另外留意下這些操作在執(zhí)行的時(shí)候，mKeys數(shù)組并沒(méi)有經(jīng)過(guò)任何修改）。這2個(gè)方法都是通過(guò)key來(lái)進(jìn)行操作，有時(shí)你可能想基于index來(lái)執(zhí)行某些操作，上面的removeAt(index)和removeAtRange(index, size)就是這樣的方法，處理也都是如果位置i沒(méi)標(biāo)記刪除則標(biāo)記之，并設(shè)置mGarbage的值。只是在removeAtRange中對(duì)上限做了保險(xiǎn)處理即end = Math.min(mSize, index+size)，以防數(shù)組越界。
接下來(lái)該打起來(lái)精神睜大眼睛了，讓我們一起來(lái)看看SparseArray的關(guān)鍵，姑且稱之為清理壓縮，上代碼：
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
// 數(shù)組的2個(gè)下標(biāo)，一前一后，接下來(lái)移動(dòng)數(shù)組元素需要用到
int reusedIndex = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {
if (i != reusedIndex) {
keys[reusedIndex] = keys[i];
values[reusedIndex] = val;
values[i] = null; // 往前提后，釋放此位置上的元素
}
// 如果遇到了DELETED值，那么此下標(biāo)不動(dòng)，i還是正常增加
// 所以下次循環(huán)執(zhí)行的時(shí)候，就會(huì)發(fā)生后面的有效值覆蓋掉前面DELETED的位置
// 如果遇到的是有效值，那么這2個(gè)下標(biāo)是同步移動(dòng)的
reusedIndex++;
}
}
mGarbage = false;
mSize = reusedIndex;
// Log.e("SparseArray", "gc end with " + mSize);
}
gc方法只有在mGarbage設(shè)置的時(shí)候才有可能調(diào)用，其總體思想是把靠后的有效元素（即沒(méi)被刪除的）往前（reusedIndex的位置）提，從而達(dá)到清理壓縮的目的。我們仔細(xì)分析下，首先初始化一些接下來(lái)要用到的值，這里特別留意下reusedIndex（源碼中叫o，實(shí)在不好理解，我按自己的理解重新命名了），初始化為0，指向第一個(gè)元素。接下來(lái)是遍歷mValues數(shù)組的for循環(huán)，其內(nèi)部是如果當(dāng)前元素val是DELETED則啥也不做，接著看下一個(gè)元素（注意此時(shí)reusedIndex還是保持不動(dòng)）；否則當(dāng)前是個(gè)有效的元素，執(zhí)行步驟1、2：
reusedIndex不是當(dāng)前的index則應(yīng)該把當(dāng)前元素拷貝到reusedIndex的位置（key和value都復(fù)制，即往前提），當(dāng)前位置的value清空（置null）；
reusedIndex往前+1（每遇到一個(gè)有效元素），準(zhǔn)備下次循環(huán)。
結(jié)束遍歷之后reset mGarbage（因?yàn)閯倓傋鲞^(guò)了，暫時(shí)不需要了），更新mSize為reusedIndex（因?yàn)槊坑龅揭粋€(gè)有效元素，reusedIndex就+1，所以它的值就是新的mSize）。
整個(gè)gc結(jié)束后，mValues數(shù)組里的所有DELETED元素就不存在了，故mSize也會(huì)相應(yīng)減小。
看完了上面的方法，我們來(lái)看下put相關(guān)的方法，代碼如下：
/**
* 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) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 已存在，則直接用新值替換
mValues[i] = value;
} else {
i = ~i; // 再次取反，得到要插入的位置
if (i < mSize && mValues[i] == DELETED) {
// 標(biāo)記為刪除的位置的再次復(fù)用
mKeys[i] = key;
mValues[i] = value;
return;
}
// 到了臨界點(diǎn)且需要觸發(fā)gc，則執(zhí)行一次gc方法
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 將key、value在i的位置插入，并返回新的數(shù)組
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++; // key-value對(duì)+1
}
}
// 上面用到的GrowingArrayUtils.insert實(shí)現(xiàn)，代碼如下：
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
// 大小夠用，index處的元素往后順延1個(gè)位置，給新的index騰出位置
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
// 大小不夠用，申請(qǐng)新的數(shù)組，拷貝，index處賦值
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
put實(shí)現(xiàn)關(guān)鍵的幾個(gè)點(diǎn)，也已經(jīng)寫(xiě)在上面的代碼注釋里了，可以重點(diǎn)關(guān)注下。
看完了上面put的實(shí)現(xiàn)后，最后來(lái)看看幾個(gè)非常簡(jiǎn)單的方法，
/**
* Returns the number of key-value mappings that this SparseArray
* currently stores.
*/
public int size() {
if (mGarbage) {
gc();
}
return mSize;
}
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the key from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The keys corresponding to indices in ascending order are guaranteed to
* be in ascending order, e.g., <code>keyAt(0)</code> will return the
* smallest key and <code>keyAt(size()-1)</code> will return the largest
* key.</p>
*/
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the value from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The values corresponding to indices in ascending order are guaranteed
* to be associated with keys in ascending order, e.g.,
* <code>valueAt(0)</code> will return the value associated with the
* smallest key and <code>valueAt(size()-1)</code> will return the value
* associated with the largest key.</p>
*/
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
/**
* Given an index in the range <code>0...size()-1</code>, sets a new
* value for the <code>index</code>th key-value mapping that this
* SparseArray stores.
*/
public void setValueAt(int index, E value) {
if (mGarbage) {
gc();
}
mValues[index] = value;
}
/**
* Returns the index for which {@link #keyAt} would return the
* specified key, or a negative number if the specified
* key is not mapped.
*/
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
/**
* Returns an index for which {@link #valueAt} would return the
* specified key, or a negative number if no keys map to the
* specified value.
* <p>Beware that this is a linear search, unlike lookups by key,
* and that multiple keys can map to the same value and this will
* find only one of them.
* <p>Note also that unlike most collections' {@code indexOf} methods,
* this method compares values using {@code ==} rather than {@code equals}.
*/
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++)
if (mValues[i] == value) // 唯一需要留意的是這里比較用的==，而非equals
return i;
return -1;
}
/**
* Removes all key-value mappings from this SparseArray.
*/
public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}
size()方法返回當(dāng)前有效的key-value對(duì)的數(shù)目，值得注意的是在其內(nèi)部都會(huì)有條件的執(zhí)行g(shù)c方法，因?yàn)橹暗牟僮骺赡軐?dǎo)致mGarbage被設(shè)置了，所以必須執(zhí)行下清理壓縮才能返回最新的值；
keyAt(index)和valueAt(index)提供了遍歷SparseArray的方式，如下：
for (int i = 0; i < sparseArray.size(); i++) {
System.out.println("key = " + sparseArray.keyAt(i) + ", value = " + sparseArray.valueAt(i));
}
同樣和size()方法一樣其內(nèi)部也都會(huì)有條件的執(zhí)行g(shù)c方法，注意你傳遞的index必須在[0, size()-1]之間，否則會(huì)數(shù)組越界。
setValueAt讓你像使用數(shù)組一樣設(shè)置某個(gè)位置處的值，同樣會(huì)有條件的執(zhí)行g(shù)c方法。
indexOfKey通過(guò)二分查找來(lái)search key的位置；indexOfValue在整個(gè)mValues數(shù)組中遍歷查找value，有則返回對(duì)應(yīng)的index否則返回-1。
clear()方法清空了mValues數(shù)組，重置了mSize，mGarbage，但請(qǐng)注意并沒(méi)有動(dòng)mKeys數(shù)組；
目前為止，SparseArray類的所有關(guān)鍵代碼都已經(jīng)分析完畢，希望對(duì)各位平時(shí)的開(kāi)發(fā)有所幫助，祝好。
