SparseArray 原始碼解析
使用 Android Studio 作為 IDE 的開發者可能會遇到一個現象,就是在程式碼中如果聲明瞭Map<Integer, Object>
型別的變數的話,Android Studio 會提示:Use new SparseArray<Object>(...) instead for better performance ...
,意思就是用 SparseArray<Object> 效能更優,可以考慮來替換 HashMap
這裡就來介紹下 SparseArray 的內部原理,看看它與 HashMap 有什麼差別,關於 HashMap 的原始碼解析可以看這裡:Java集合框架原始碼解析之HashMap
一、基本概念
先看下 SparseArray 的使用方式
SparseArray<String> sparseArray = new SparseArray<>(); sparseArray.put(100, "leavesC"); sparseArray.remove(100); sparseArray.get(100); sparseArray.removeAt(29);
SparseArray<E> 相當於 Map<Integer,E> ,key 值固定為 int 型別,在初始化時只需要宣告 Value 的資料型別即可,其內部用兩個陣列分別來儲存 Key 列表和 Value 列表:int[] mKeys ; Object[] mValues
mKeys
和mValues
通過如下方式對應起來:假設要向SparseArray
存入key
為10
,value
為200
的鍵值對,則先將10
存到mKeys
中,假設10
在mKeys
中對應的索引值是index
,則將value
存入mValues[index]
中
最首要的一點就是 SparseArray 避免了 Map 每次存取值時的裝箱拆箱 操作,其 Key 值型別都是基本資料型別 int,這有利於提升效能
二、全域性變數
布林變數mGarbage
也是 SparseArray 的一個優化點之一,用於標記當前是否有待垃圾回收(GC)的元素
,當該值被置為 true 時,即意味著當前狀態需要進行垃圾回收,但回收操作並不馬上進行,而是在後續操作中再完成
//陣列元素在沒有外部指定值時的預設元素值 private static final Object DELETED = new Object(); //用於標記當前是否有待垃圾回收(GC)的元素 private boolean mGarbage = false; private int[] mKeys; private Object[] mValues; //當前集合元素大小 //該值並不一定是時時處於正確狀態,因為有可能出現只刪除 key 和 value 兩者之一的情況 //所以在呼叫 size() 方法前都需要進行 GC private int mSize;
三、建構函式
key 陣列和 value 陣列的預設大小都是 10,如果在初始化時已知資料量的預估大小,則可以直接指定初始容量,這樣可以避免後續的擴容操作
//設定陣列的預設初始容量為10 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; }
四、新增元素
新增元素的方法有如下幾個,主要看put(int key, E value)
方法,當中用到了ContainerHelpers
類提供的二分查詢方法:binarySearch
,用於查詢目標 key 在 mKeys 中的當前索引或者是目標索引
binarySearch 方法的返回值分為兩種情況:
- 如果 mKeys 中存在對應的 key,則直接返回對應的索引值
-
如果 mKeys 中不存在對應的 key
- 假設 mKeys 中存在"值比 key 大且大小與 key 最接近的值的索引"為 presentIndex,則此方法的返回值為 ~presentIndex
- 如果 mKeys 中不存在比 key 還要大的值的話,則返回值為 ~mKeys.length
可以看到,即使在 mKeys 中不存在目標 key,但其返回值也指向了應該讓 key 存入的位置。通過將計算出的索引值進行 ~ 運算,則返回值一定是 0 或者負數,從而與“找得到目標key的情況(返回值大於0)”的情況區分開
且通過這種方式來存放資料,可以使得 mKeys 的內部值一直是按照值遞增的方式來排序的
//將索引 index 處的元素賦值為 value //SparseArray 的元素值都是存到 mValues 中的,因此如果知道目標位置(index),則可以直接向陣列 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 或者負數,從而與“找得到目標key的情況(返回值大於0)”的情況區分開 //且通過這種方式來存放資料,可以使得 mKeys 的內部值一直是按照值遞增的方式來排序的 i = ~i; //如果目標位置還未賦值,則直接存入資料即可,對應的情況是 2.1 if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } //以下操作對應兩種情況: //1、對應 2.1 的一種特殊情況,即目標位置已用於存放其他值了 //此時就需要將從索引 i 開始的所有資料向後移動一位,並將 key 存到 mKeys[i] //2、對應的情況是 2.2 if (mGarbage && mSize >= mKeys.length) { gc(); //GC 後再次進行查詢,因為值可能已經發生變化了 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //通過複製或者擴容陣列,將資料存放到陣列中 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } } //和 put 方法類似 //但在存入資料前先對資料大小進行了判斷,有利於減少對 mKeys 進行二分查詢的次數 //所以在“存入的 key 比現有的 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 時,即意味著當前狀態需要進行垃圾回收,但回收操作並不馬上進行,而是在後續操作中再完成
以下幾個方法在移除元素時,都是隻切斷了 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) { //避免發生陣列越界的情況 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; }
六、查詢元素
查詢元素的方法較多,但邏輯都是挺簡單的
//根據 key 查詢相應的元素值,查詢不到則返回預設值 @SuppressWarnings("unchecked") public E get(int key, E valueIfKeyNotFound) { //用二分查詢法查詢指定 key 在 mKeys 中的索引值 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //如果找不到該 key 或者該 key 尚未賦值,則返回預設值 if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } } //根據 key 查詢相應的元素值,查詢不到則返回 null public E get(int key) { return get(key, null); } //因為 mValues 中的元素值並非一定是連貫的,有可能摻雜著 DELETED //所以在遍歷前需要先進行 GC,這樣通過陣列取出的值才是正確的 @SuppressWarnings("unchecked") public E valueAt(int index) { if (mGarbage) { gc(); } return (E) mValues[index]; } //根據索引值 index 查詢對應的 key public int keyAt(int index) { if (mGarbage) { gc(); } return mKeys[index]; } //根據 key 對應的索引值 public int indexOfKey(int key) { if (mGarbage) { gc(); } return ContainerHelpers.binarySearch(mKeys, mSize, key); } //根據 value 查詢對應的索引值 public int indexOfValue(E value) { if (mGarbage) { gc(); } for (int i = 0; i < mSize; i++) { if (mValues[i] == value) { return i; } } return -1; } //與 indexOfValue 方法類似,但 indexOfValue 方法是通過比較 == 來判斷是否同個物件 //而此方法是通過 equals 方法來判斷是否同個物件 public int indexOfValueByValue(E value) { if (mGarbage) { gc(); } for (int i = 0; i < mSize; i++) { if (value == null) { if (mValues[i] == null) { return i; } } else { if (value.equals(mValues[i])) { return i; } } } return -1; }
七、垃圾回收
因為 SparseArray 中可能會出現只移除 value 和 value 兩者之一的情況,導致陣列中存在無效引用,因此gc()
方法就用於移除無效引用,並將有效的元素值位置合併在一起
//垃圾回收 //因為 SparseArray 中可能出現只移除 value 和 value 兩者之一的情況 //所以此方法就用於移除無用的引用 private void gc() { int n = mSize; //o 值用於表示 GC 後的元素個數 int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; //元素值非預設值 DELETED ,說明該位置可能需要移動資料 if (val != DELETED) { //以下程式碼片段用於將索引 i 處的值賦值到索引 o 處 //所以如果 i == o ,則不需要執行程式碼了 if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o; }
八、優劣勢
從上文的解讀來看,SparseArray 的主要優勢有以下幾點:
- 避免了基本資料型別的裝箱拆箱操作
- 和 Map 每個儲存結點都是一個類物件不同,SparseArray 不需要用於包裝的的結構體,單個元素的儲存成本更加低廉
- 在資料量不大的情況下,查詢效率較高(二分查詢法)
- 延遲了垃圾回收的時機,只在需要的時候才一次進進行
劣勢有以下幾點:
- 插入新元素可能會導致移動大量的陣列元素
- 資料量較大時,查詢效率(二分查詢法)會明顯降低