充滿矛盾的類——SparseArray
雖然類名叫“稀疏陣列”,但它其實非常“緊實”。這一篇將會通過分析SparseArray
的原始碼來展現這個類的矛盾之處。
(ps: 下文中的 粗斜體字 表示引導原始碼閱讀的內心戲)
還記得分析RecyclerView快取機制
中提到的SparseArray
嗎?當時只知道它是一個存放鍵值對的容器。RecyclerView
的回收池使用它按ViewType
分類存放被回收的ViewHolder
。
HashMap
也存放鍵值對,為啥RecyclerView
不用HashMap
?
帶著這個疑問,點開SparseArray.java
,一探究竟:
/** * SparseArrays map integers to Objects.Unlike a normal array of Objects, * there can be gaps in the indices.It is intended to be more memory efficient * than using a HashMap to map Integers to Objects, both because it avoids * auto-boxing keys and its data structure doesn‘t rely on an extra entry object * for each mapping. * SparseArrays建立int值和Object之間的關係 * 不同於一般的陣列物件,SparseArray陣列物件間不會存在空隙 * 相對於HashMap<Integer,Object>更加節省記憶體,因為避免了鍵自動裝箱以及建立Entry實體 * * <p>Note that this container keeps its mappings in an array data structure, * using a binary search to find keys.The implementation is not intended to be appropriate for * data structures * that may contain large numbers of items.It is generally slower than a traditional * HashMap, since lookups require a binary search and adds and removes require inserting * and deleting entries in the array.For containers holding up to hundreds of items, * the performance difference is not significant, less than 50%.</p> * SparseArrays將鍵值對儲存在陣列中並通過二分查詢鍵值。所以在資料量很大的時候速度較慢。 */ public class SparseArray<E> implements Cloneable { ... }
讀完這段註釋好像已經回答了剛才的問題:因為SparseArray
相較於HashMap
有更好的空間效能。而且RecyclerView
回收池中每種viewType
預設最多存放5個ViewHolder
。少量資料也正好可以忽略SparseArray
在效能上的劣勢。
取值
好奇SparseArray
是如何做到用時間換空間的?容器類必然會提供存和取的操作,就以取操作為切入點,一探究竟:
public class SparseArray<E> implements Cloneable { //儲存鍵的陣列 private int[] mKeys; //儲存值的陣列 private Object[] mValues; /** * Gets the Object mapped from the specified key, or <code>null</code> * if no such mapping has been made. * 根據給定的key取對應value,如果沒有取到則返回null */ 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. * 根據給定的key取對應value */ @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]; } } } class ContainerHelpers { // 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 } }
看到這裡可以做一個階段性總結:
-
SparseArray
用兩個長度相同的陣列分別儲存鍵和值,鍵是int
型別的,值是Object
型別的。而且一對鍵值在各自陣列中的索引相同。 - 取值演算法如下:按鍵取值時,會二分查詢鍵陣列。若找到,則用相同的索引去值陣列取出值。
- 不由得產生一個疑問: 鍵陣列可以使用二分法查詢,難道它是有序的嗎?看下存值邏輯是否能找到更多線索。
存值
public class SparseArray<E> implements Cloneable { /** * 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); //1.若找到鍵索引(表示該鍵已存在),則用新值覆蓋舊值 if (i >= 0) { mValues[i] = value; } //若未找到儲存索引,則儲存新值 else { //將負值索引恢復成正值(二分查詢失敗時會取反) i = ~i; //2.若目標插入位置是待刪除位,則複用待刪除位 if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } //當鍵陣列滿了且存在待刪除位時,壓縮陣列 if (mGarbage && mSize >= mKeys.length) { gc(); // Search again because indices may have changed. //壓縮陣列產生了陣列挪動,索引會改變,所以重新查詢一遍以獲新目標插入位置 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //3.插入到新的位置 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); //有效鍵值對+1 mSize++; } } }
存值時通過二分查詢確定存入位置,如果每次存入的鍵都是新的,那每次查詢必然失敗,但查詢失敗返回的索引值(取反後)正是遵守了原有序列的順序產生的應該被插入新鍵的位置。所以,剛才的疑問解決了:鍵陣列是有序的,且是遞增的。
在獲得目標插入位置後,分為三種情況:
1. 新值覆蓋舊值
在鍵陣列中二分查詢給定鍵值,如果返回的索引大於0,則表示找到相同的鍵。直接將新值賦值給值陣列的對應位置,覆蓋掉舊值。
2. 複用待刪除位
如果二分查詢失敗,表示給定鍵是一個新的鍵。如果新鍵對應的索引位是一個待刪除位,則將新值存入該位置,以複用該待刪除位。
待刪除位是啥?,看一下刪除操作SparseArray.delete()
:
public class SparseArray<E> implements Cloneable { ... //用於標記某一位置的鍵值對已經被刪除(假刪) private static final Object DELETED = new Object(); /** * 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) { //將值陣列中對應位置標記為待刪除 if (mValues[i] != DELETED) { mValues[i] = DELETED; //打開回收開關 mGarbage = true; } } } }
刪除鍵值對時並沒有真正的刪除,而是標記為刪除(此處並沒有將mSize--),但標記的後果是陣列會變得“稀疏”,即有效鍵值對不是一個挨著一個,他們會被待刪除鍵值對分割。
想想也對,陣列的刪除操作是費時的,因為需要整體挪動陣列覆蓋待刪除位。想必在未來的某個時刻應該會執行一次真正的刪除。
所以存值的第二種情況是:當待刪除位還沒來得及真正刪除時被複用了。
3. 插入新位置
當給定鍵是一個新的鍵且其對應的索引位已經被其他鍵值所佔用了,即發生了衝突(HashMap
的解決方案是“拉鍊法”,相同鍵的值被組織在一個連結串列結構中),SparseArray
通過挪動陣列來解決衝突:
public final class GrowingArrayUtils { /** * Primitive int version of {@link #insert(Object[], int, int, Object)}. * 陣列插入操作 * @param array陣列 * @param currentSize 當前有效元素個數 * @param index 待插入位置 * @param element 帶插入元素 * @return */ public static int[] insert(int[] array, int currentSize, int index, int element) { assert currentSize <= array.length; //1.如果array陣列可以容納下一個新元素,則將給定元素插入到指定位置 //並將原本該位置以後的元素整體往後平移一個位置 if (currentSize + 1 <= array.length) { System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } //2.如果array容納不下,則將陣列擴容 //構造比老陣列更大的新陣列 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; } //擴容演算法 public static int growSize(int currentSize) { return currentSize <= 4 ? 8 : currentSize * 2; } }
其實除了發生衝突,還有另一種情況(註釋中第2點):原本的鍵陣列滿了。這種情況下只能通過陣列擴容才能存取新的值。
緊緻
剛才跳過了一個步驟(它是“緊緻”的關鍵),即將新的鍵值插入到陣列之前,還有一個回收操作SparseArray.gc()
,點進去看看:
public class SparseArray<E> implements Cloneable { //壓縮鍵陣列和值陣列,將待刪除索引位覆蓋(將陣列中的空隙填滿) private void gc() { // Log.e("SparseArray", "gc start with " + mSize); 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會偏大) mSize = o; } }
一圖勝千言:
-
假設當前
SparseArray
中有4個鍵值對,此時mSize=4
,如下所示:
0 | 1 | 2 | 3 | |
---|---|---|---|---|
mKeys | 55 | 57 | 58 | 60 |
mValues | A | B | D | F |
-
刪除第二個後,此時
mSize=4
:
0 | 1 | 2 | 3 | ||
---|---|---|---|---|---|
mKeys | 55 | 57 | 58 | 60 | 65 |
mValues | A | DELETE | D | F | G |
-
執行
SparseArray.gc()
後,此時mSize=3
:
0 | 1 | 2 | 3 | |
---|---|---|---|---|
mKeys | 55 | 58 | 60 | 60 |
mValues | A | D | F | null |
雖然經過SparseArray.gc()
後,陣列末尾會出現兩個相同的鍵,但這不會影響下一次二分查詢,因為二分查詢的終點是mSize-1
。
“緊緻”是相對於“稀疏”來說的,當從SparseArray
刪除鍵值對,SparseArray
中儲存鍵值對的兩個陣列就變得“稀疏”,“緊緻”就是覆蓋掉待刪除鍵值對,讓有效鍵值對重新挨個排在一起,這樣二叉查詢效率更高。
SparseArray.gc()
中運用了兩個索引,分別是i
和o
。如果把遍歷值陣列比作跑步,那這兩個索引就是兩個選手,它們同時從起點出發。不同的是,每當遇到待刪除坑位,o
就會停下來,而i
總是一往直前,所以i
一直領先於o
,當i
找到有效鍵值對時,會將其覆蓋到o
的位置,然後o
才向前進一步。通過這樣的演算法,就實現了將陣列後面的內容往前挪覆蓋掉待刪位。
所以,明明很緊緻,卻偏偏要取一個稀疏的名字,這是一個充滿矛盾的類。
總結
-
SparseArray
用於存放鍵值對,鍵是int
,值是Object
。它比HashMap
更節省空間,但速度更慢。 -
SparseArray
用兩個長度相等的陣列分別儲存鍵和值,同一個鍵值對所在兩個陣列中的索引相等。 -
SparseArray
中存放鍵的陣列是遞增序列 -
SparseArray
刪除元素時並不會真正刪除,而是標記為待刪除元素,在合適的時候會將後面的元素往前挪覆蓋掉待刪除元素。待刪除元素在沒有被覆蓋前有可能被複用。