見名知意
SparseArray "稀疏數(shù)組", 是數(shù)組，key是整數(shù)波势，但key不是連續(xù)的翎朱。如下圖，key并不是4到10連續(xù)的尺铣，它只是零星地存儲了幾個自己想要的數(shù)據(jù)拴曲。跟HashMap理解一樣。
SparseArray內部維持著2個數(shù)組keys,values凛忿。通過找到key在數(shù)組中的索引index,從而找到key對應的數(shù)據(jù)values[index]澈灼。
SparseArray內部數(shù)據(jù)結構
基本操作
- 創(chuàng)建實例： 可以指定初始的容量(keys和values數(shù)組)大小，也可以不傳店溢，如果不傳入的話叁熔，默認大小為10。
val sparseArray = SparseArray<String>(5)
- 增加數(shù)據(jù) : put和append都可以床牧。注意append并不像我們平常接觸的那樣是在末尾追加肖方，它最終還是調用put科侈，還是保持key從小到大的順序。
sparseArray.apply {
put(7, "seven")
put(10, "ten")
append(4, "four") //盡管是append的郁轻，數(shù)據(jù)還是在最前面
}
- 數(shù)據(jù)迭代: keyAt(), get(key), 按照key的從小到大的順序顯示
Log.d(TAG,"==> iterator before remove.")
for (i in 0 until sparseArray.size()) {
val key = sparseArray.keyAt(i)
val value = sparseArray.get(key)
Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four
// key = 7,value = seven
// key = 10,value = ten
- 刪除數(shù)據(jù): remove(key)或者delete(key)娩怎。 remove(key)代碼實現(xiàn)還是調用delete(key)
sparseArray.remove(7)
sparseArray.remove(8)
Log.d(TAG,"==> iterator after remove.")
for (i in 0 until sparseArray.size()) {
val key = sparseArray.keyAt(i)
val value = sparseArray[key]
Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four
// key = 10,value = ten
與HashMap區(qū)別
看這用法，跟HashMap沒啥區(qū)別，難道HashMap不香嘛？
我們知道當HashMap中的key是普通的數(shù)字類型的話耳贬，我們key是要經過裝箱過程的，如int到Integer, long 到 Long泳姐。這個裝箱的過程存在一定的性能消耗效拭。而且暂吉，HashMap存儲value的時候需要依賴額外的Entry類型胖秒，這也帶來一定的開銷。
所以當我們需要一個簡單的key為int這種原始數(shù)字類型時慕的，可以使用SparseArray, 而key為long時阎肝，可使用LongSparseArray。
但是肮街，為維持key的有序性风题，增刪的過程需要使用二分搜索key數(shù)組，查的過程也需要通過二分搜索找到key的索引嫉父，當數(shù)據(jù)量過大的時候沛硅，二分搜索帶來的開銷會比裝箱、類型創(chuàng)建帶來的開銷要大绕辖。
因此使用SparseArray要求：
- 數(shù)據(jù)的key為int或者long
- 數(shù)據(jù)量小
源碼分析
主要分析put和delete的過程摇肌，這2過程直接奠定了其他算法的實現(xiàn)。
- 增加的過程 put(key1,value)仪际。
- 通過二分搜索key, 判斷是否已經有歷史數(shù)據(jù)
- 有歷史數(shù)據(jù)直接覆蓋围小，沒有的話， 垃圾回收清除刪除的數(shù)據(jù)树碱，擴容數(shù)組肯适，再插入到指定索引位置
public void put(int key, E value) {
// 1. 二分搜索找到key在keys數(shù)組中的位置
// 如果key在keys中找到，那么返回對應索引位置
//如果沒有找到的話成榜，返回插入位置的取反 ~insertIndex 為負值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
// 2. 1如果找到了框舔，但是數(shù)據(jù)時處于刪除的狀態(tài)(刪除key,不會直接從keys中刪除key, 而是把其值負值為DELETED的內部常量，見delete過程)赎婚，直接覆蓋
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 2.2 垃圾回收(有刪除了的值)刘绣，并且數(shù)據(jù)滿員了，進行垃圾回收見gc(), 并重新獲得插入的位置
// 如果垃圾數(shù)清除的話惑淳，那么清除了额港，后續(xù)就不需要再進行擴容數(shù)組操作了
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 2.2 插入數(shù)據(jù)，擴容數(shù)組或者直接插入數(shù)據(jù)歧焦，見insert()
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
private static int[] insert(int[]array,int currentSize, int index, int element){
assert currentSize <= array.length;
if(currentSize + 1 <= array.length){ //數(shù)據(jù)未滿
System.arraycopy(array,index,array,index + 1,currentSize - index);
array[index] = element;
return array;
}
//擴容數(shù)組 * 2
int[] newArray = new int[growSize(currentSize)];
System.arraycopy(array,0,newArray,0,index);
newArray[index] = element;
System.arraycopy(array,index,newArray,index + 1 , array.length - index);
return newArray;
}
private static int growSize(int currentSize){
return currentSize <= 4 ? 8 : currentSize * 2;
}
// 垃圾回收移斩，清除多余的值肚医，快慢指針，覆蓋清除DELETED
private void gc() {
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 = o;
}
- 刪除過程 delete(key1)
刪除的過程中向瓷，并沒有直接通過刪除key的方式來縮短key數(shù)組肠套，而是將其值標記為刪除狀態(tài)，賦值為DELETED猖任。這樣避免不必要的刪除和插入操作你稚，當重新增加數(shù)據(jù)時，可以直接將值更新為最新的值朱躺。
例如： remove(7); put(7,"Seven") 這兩個連續(xù)操作的過程就不需要先刪除7刁赖，然后key數(shù)組和value數(shù)組7之后的元素整體往前移動，而后插入過程也不用整體向后移動长搀。
不過也正是因為刪除過程不進行實際刪除宇弛，當我們需要獲得真實的內部數(shù)據(jù)(如size)的時候，如果mGarbage為true,即有垃圾數(shù)據(jù)的時候源请，我們每次都需要先進行垃圾回收刪除數(shù)據(jù)枪芒，再返回真實的數(shù)據(jù)。
public void delete(int key) {
// 一樣是二分搜索
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED; //標記為DELETED
mGarbage = true;
}
}
}
