在安卓項目中, 新建一個 HashMap 對象, 會有提示: 建議使用 SparseArray 會有更好的表現(xiàn). 尤其是鍵為 Integer 類型的 maps, 更加高效. 尤其是 value 是原始數(shù)據(jù)類型時, 可以使用 SparseIntArray 等來避免裝箱的操作. (其實還有其它優(yōu)勢)
為什么叫 SparseArray?
SparseArray 稀疏數(shù)組. 為什么叫稀疏?
先來看下 Javascript 中關于稀疏數(shù)組的定義:
稀疏數(shù)組就是包含從 0 開始的不連續(xù)索引的數(shù)組. 通常, 數(shù)組的 length 屬性值代表數(shù)組中元素的個數(shù). 如果數(shù)組是稀疏的, length 屬性值大于元素的個數(shù). 可以用 Array() 構(gòu)造函數(shù)或簡單地指定數(shù)組的索引值大于當前數(shù)組長度來創(chuàng)建稀疏數(shù)組.
可能有點懵, 我先說下我寫完這篇筆記的理解. 在 SparseArray 數(shù)組中, 部分需要刪除的元素, 不會被立即從數(shù)組中刪除, 而是被標記為需要刪除. 只有在需要的時候, 才一次性去刪除和釋放空間. 這時, 數(shù)組的 length 長度不能反映有效元素的個數(shù), 因為被標記需要刪除的元素也被計算進去了. SparseArray 中, 有一個單獨的成員變量來計算實際有效元素的個數(shù). 所以 SparseArray 數(shù)組就是一大串數(shù)組中有很多標記為可刪除的元素, 所以是稀疏的, 零散的. 之后會詳細記錄對于刪除標志位的學習.
類型
Android Studio 給出的提示 - value 是原始數(shù)據(jù)類型時, 可以避免裝箱的操作. 那詳細看一下 SparseArray 給出的類型:
SparseArray <int, Object>
SparseBooleanArray <int, boolean>
SparseIntArray <int, int>
SparseLongArray <int, long>
LongSparseArray <long, Object>
會發(fā)現(xiàn)它和 HashMap 唯一不同的就是鍵值對的類型, HashMap的鍵值都為泛型, 但是 SparseArray 的鍵值只能為 int/long. 因為 long 的范圍更大, 所以 LongSparseArray 儲存的數(shù)據(jù)比 SparseArray 多.
int 的范圍是 -2^31 到 2^31-1, 而 long 是 -2^63 到 2^63-1
使用方法
SparseArray<String> sparseArray= new SparseArray<>();
// 增加元素
sparseArray.append(0, "myValue"); // append 方式, 追加. 其實也包含了 put. 后面源碼分析
sparseArray.put(1, "myValue"); // put 方式, 指定 key 更新
//刪除元素, 二者等同
sparseArray.remove(1);
sparseArray.delete(1);
//修改元素, put/append 相同的 key 值即可
sparseArray.put(1,"newValue");
sparseArray.append(1,"newValue");
設計思想
成員變量
首先來 SparseArray 的源碼, 其中定義了一些成員變量:
private static final Object DELETED = new Object();
private boolean mGarbage = false;
// 需要說明一下
// 這里的 mKeys 數(shù)組是按照 key 值遞增存儲的
private int[] mKeys;
private Object[] mValues;
private int mSize;
-
DELETED- 標志字段, 用于判斷是否刪除. -
mGarbage- 標志字段, 用于確定當前是否需要垃圾回收. -
mKeys數(shù)組 - 存儲 key.int類型. -
mValues數(shù)組 - 存儲值 -
mSize當前元素數(shù)量
append 方法
public void append(int key, E value) {
// 當 mSize 不為 0 并且不大于 mKeys 數(shù)組中的最大值時
// 因為 mKeys 是一個升序數(shù)組, 最大值即為 mKeys[mSize-1]
if (mSize != 0 && key <= mKeys[mSize - 1]) {
// 執(zhí)行 put 方法
put(key, value);
return;
}
// 不是 put 則證明需要新增
// 當垃圾回收標志 mGarbage 為 true 并且當前元素已經(jīng)占滿整個數(shù)組
if (mGarbage && mSize >= mKeys.length) {
gc(); // 執(zhí)行垃圾回收進行空間壓縮
}
// 當 mSize 為 0, 或者 key 值大于當前 mKeys 數(shù)組最大值的時候
// 在數(shù)組最后一個位置插入元素.
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
// 元素加一
mSize++;
}
會發(fā)現(xiàn)處理以下兩種情況:
- 如果是更新對應
key的值,append方法調(diào)用put方法. 此時key值不等于 0 且小于等于最大值. 因為key值之前有提到是遞增存儲. - 如果是新增. 即
key等于 0, 數(shù)組為空, 或者key大于當前最大值, 在最后插入.
put 方法
public void put(int key, E value) {
// 二分查找
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 查找到
if (i >= 0) {
mValues[i] = value; // 更新值
} else { // 沒有找到
i = ~i; // 獲得二分查找結(jié)束后, lo 的值
// 元素要添加的位置正好被標記為 DELETED, 直接覆蓋它的值即可.
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 垃圾回收, 但是空間壓縮后，mValues 數(shù)組和 mKeys 數(shù)組元素有變化, 需要重新計算插入的位置
if (mGarbage && mSize >= mKeys.length) {
gc();
// 重新二分查找插入的位置
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 在指定位置 i 處, 插入元素
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
// 元素加一
mSize++;
}
}
方法里的二分查找取反操作很奇怪, 我們先看下二分查找的代碼:
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; // 找到了
}
}
return ~lo; // 和普通二分查找不一樣的地方. 返回了負的 lo.
}
正常沒找到, 我們可能會返回 -1, 表示查找失敗就夠了. 那為什么返回一個 lo 的取反?
- 首先需要和 -1, 一樣的功能, 需要一個負數(shù)表示沒有找到.
- 這個 lo 值其實就是新元素的插入位置.
好了, 回到 put 方法, 在拿到待插入元素應該插入的位置之后, 它首先判斷需要插入的位置對應 mValues 數(shù)組的值是不是 DELETED, 如果是的話，直接覆蓋, 那為什么這樣做?
先看下 delete 方法源碼
public void delete(int key) {
// 查找要刪除的元素下標
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
SparseArray 也有 remove 方法, 它其實是直接調(diào)用 delete, 所以二者是一樣的效果.
看到這個 delete 方法, 并沒有直接去刪除, 而是將 value 值設為 DELETED 標志位. 然后設置 mGarbage 為 true, 也就是垃圾回收標志位. 再來看下之前緊跟著的 gc() 方法:
private void gc() {
int n = mSize; // 壓縮前數(shù)組大小
int o = 0; // 壓縮后數(shù)組大小, 初始為0
int[] keys = mKeys; // 保存新的 key 值的數(shù)組
Object[] values = mValues; // 保存新的 value 值的數(shù)組
for (int i = 0; i < n; i++) {
Object val = values[i];
// 如果沒有 DELETED 標志位
if (val != DELETED) {
// i != o, 說明前面已經(jīng)有元素被打上 DELETED 標簽
if (i != o) {
// 將位置 i 的元素移動到 o 處. 其實 o 處就是之前 DELETED 標簽的位置. 被覆蓋
keys[o] = keys[i];
values[o] = val;
values[i] = null; // 釋放空間
}
// 新數(shù)組元素加一
o++;
}
}
// 回收完畢, 還原標志位
mGarbage = false;
// 回收之后數(shù)組的大小
mSize = o;
}
所以是通過 gc() 方法, 根據(jù)標志位用 DELETED 之后的元素覆蓋該標志位的元素, 達到壓縮和空間釋放的目的.
為什么不直接刪除
回頭來看 put 方法:
// 添加元素時直接覆蓋 DELETED 標志位的元素
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
還記得這一段嗎? 在添加元素的時候, 如果對應的元素正好被標記了 DELETE, 那么直接覆蓋它即可! 這樣做, 和每次都刪除元素相比, 可以直接省去刪除元素的操作, 大大提高了效率. 只有空間不足的時候, 才調(diào)用 gc() 方法一次性壓縮空間, 效率進一步.
SparseArray 與 HashMap萄唇、ArrayMap 比較
SparseArray 的限制在于鍵必須是 int/long 類型, 值必須是Object類型. 這樣可以避免key自動裝箱產(chǎn)生過多的 Object. 但是這樣的話, 如果 key 值相同, 那么數(shù)據(jù)就會被直接覆蓋.
SparseArray不能保證保留插入順序, 在迭代的時候應該注意.SparseArray中沒有Iterator, 只實現(xiàn)了Cloneable接口, 沒有繼承Collection享郊、List或者Map接口.查找數(shù)據(jù)使用的是二分法, 明顯比通過 hashcode 慢, 所以數(shù)據(jù)越大, 查找速度慢的劣勢越明顯.
優(yōu)點:
- 避免了基本數(shù)據(jù)類型的裝箱操作
- 不需要額外的結(jié)構(gòu)體, 單個元素的存儲成本更低
- 數(shù)據(jù)量小的情況下, 隨機訪問的效率更高
缺點：
- 插入操作需要復制數(shù)組, 增刪效率降低
- 數(shù)據(jù)量巨大時, 復制數(shù)組成本巨大普筹，
gc()成本也大, 查詢效率也會明顯下降
總結(jié)
- 通過標志位, 延遲刪除機制的機制大大提高效率. 也是稀疏數(shù)組的意義所在.
- 鍵為
Integer類型的 maps, 更加高效. 尤其是 value 是原始數(shù)據(jù)類型時, 可以使用SparseIntArray等來避免裝箱. - 二分法相比于 hashmap, 在大體量數(shù)據(jù)時, 效率降低.
