SparseArray家族 SparseArray基於鍵值對存儲數據,key為int,value為object,簡單使用如下: //聲明 SparseArray<String> sparseArray= new SparseArray<>(); //增加元素,append方式 sparseArray ...
SparseArray家族
SparseArray基於鍵值對存儲數據,key為int,value為object,簡單使用如下:
//聲明
SparseArray<String> sparseArray= new SparseArray<>();
//增加元素,append方式
sparseArray.append(0, "myValue");
//增加元素,put方式
sparseArray.put(1, "myValue");
//刪除元素,二者等同
sparseArray.remove(1);
sparseArray.delete(1);
//修改元素,put或者append相同的key值即可
sparseArray.put(1,"newValue");
sparseArray.append(1,"newValue");
//查找,遍歷方式1
for(int i=0;i<sparseArray.size();i++){
Log.d(TAG,sparseArray.valueAt(i));
}
//查找,遍歷方式2
for(int i=0;i<sparseArray.size();i++){
int key = sparseArray.keyAt(i);
Log.d(TAG,sparseArray.get(key));
}
LongSparseArray 和SparseArray 相比,唯一的不同就是key值為long,所以LongSparseArray可以存儲的數據元素就比SparseArray多,int的範圍是-2^31 到 231-1,而long是-263 到 2^63-1。
SparseBooleanArray,SparseIntArray,SparseLongArray,這三個數據結構的key值的類型也是int,value值的類型也固定,SparseBooleanArray的value固定為boolean類型,SparseIntArray的value固定為int類型,SparseLongArray的value固定為long類型。
總結一下這四種數據結構的key,value類型:
SparseArray <int, Object>
LongSparseArray <long, Object>
SparseBooleanArray <int, boolean>
SparseIntArray <int, int>
SparseLongArray <int, long>
上述四種數據結構的key類型都是int,而不是Integer,相較於使用HashMap的話,省去了裝箱拆箱過程,查詢、存儲等操作效率更高,而且int的存儲開銷也遠小於Integer。
SparseArray實現原理
SparseArray內部的重要屬性:
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
}
DELETED
static final 的一個靜態Object實例,當一個鍵值對被remove後,會在對應key的value下放置該對象,標記該元素已經被刪除,只是標記刪除,沒有真正的刪除。
mGarbage
當值為true,標誌數據結構中有元素被刪除,可以觸發gc對無效數據進行回收,真正刪除。
mKeys
用於存放Key的數組,通過int[] 進行存儲,與HashMap相比減少了裝箱拆箱的操作,同時一個int只占4位元組;一個重要特點,mKeys的元素是升序排列的,也是基於此,我們才能使用二分查找。
mValues
用於存放與Key對應的Value,通過數組的position 進行映射;如果存放的是int型等,可以用SparseIntArray ,存放的Values也是int數組,性能更高。
mSize
mSize的大小等於數組中mValues的值等於非DELETED的元素個數。
remove方法源碼:
public void delete(int key) {
//查找對應key在數組中的下標,如果存在,返回下標,不存在,返回下標的取反;
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//key存在於mKeys數組中,將元素刪除,用DELETED替換原value,起標記作用;
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
/**
* @hide
* Removes the mapping from the specified key, if there was any, returning the old value.
*/
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;
}
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
二分查找:
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation.
//第一個參數array為keys的數組,第二個為數組中元素個數(與keys的length不一定相等),第三個value為目標的key
static int binarySearch(int[] array, int size, int value) {
//lo為二分查找的左邊界
int lo = 0;
//hi為二分查找的右邊界
int hi = size - 1;
//還沒找到,繼續查找
while (lo <= hi) {
//左邊界+右邊界處以2,獲取到mid 的index
final int mid = (lo + hi) >>> 1;
//獲取中間元素
final int midVal = array[mid];
// 目標key在右部分 。。。。感覺這部分太簡單了
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
//相等,找到了,返回key對應在array的下標;
return mid; // value found
}
}
//沒有找到該元素,對lo取反!!!!!很重要
return ~lo; // value not present
}
該方法是通過二分查找返回了當前key的對應於mKeys數組的下標,如果沒有找到,就返回一個特殊的負數。二分法返回的數值如果非負數,我們則對其所對應的value進行替換成DELETED,用於標記該key已經被刪除,但是key仍然存在於mKeys數組,因此刪除是一個偽刪除同時,我們將garbage賦值true,代表數組中可能存在垃圾。
put方法源碼:
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//原來已經有key,可能是remove後,value存放著DELETED,也可能是存放舊值,那麼就替換
if (i >= 0) {
mValues[i] = value;
} else {
//沒有找到,對i取反,得到i= lo(ContainerHelpers.binarySearch)
i = ~i;
//如果i小於數組長度,且mValues==DELETED(i對應的Key被延遲刪除了)
if (i < mSize && mValues[i] == DELETED) {
//直接取代,實現真實刪除原鍵值對
mKeys[i] = key;
mValues[i] = value;
return;
}
//數組中可能存在延遲刪除元素且當前數組長度滿,無法添加
if (mGarbage && mSize >= mKeys.length) {
//真實刪除,將所有延遲刪除的元素從數組中清除;
gc();
//清除後重新確定當前key在數組中的目標位置;
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//不存在垃圾或者當前數組仍然可以繼續添加元素,不需要擴容,則將i之後的元素全部後移,數組中仍然存在被DELETED的垃圾key;
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
//新元素添加成功,潛在可用元素數量+1
mSize++;
}
}
put方法也調用了ContainerHelpers.binarySearch方法先進行查找,查找到大於0,則在數組中找到了對應的key,此時,直接將value進行替換即可;如果沒有找到,返回的是~lo,將i取反後,此時i就是我們需要插入的位置。
此刻,我們找到了i,就是目標位置,如果沒有設置延遲刪除(DELETED),那麼由於數組的特點,我們需要將i序號之後的數組後移,這樣就會產生一個較大的性能損耗;,但是如果我們設置了延遲刪除且mValue[i]上當前的元素恰巧為DELETED,那麼此時我們可以用當前的key替換原來mKeys的key,且用當前value替換DELETED;這樣就成功避免了一次數組的遷移操作。
但是事情不可能永遠湊巧,如果,i上的元素並非恰好被刪除呢?那麼此時我們會判斷mGarbage,如果為true那麼我們執行一次gc,將無效數據移除,再進行一次二分查找,然後將i之後的數據全部後移,將當前key插入;如果mGarbage為false,那麼證明其中的數據全部存在,因此不需要gc,直接進行元素插入並將數組後移。
Get方法源碼:
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];
}
}
與HashMap做比較
1、key類型都是int,而不是Integer,相較於使用HashMap的話,省去了裝箱拆箱過程,查詢、存儲等操作效率更高,而且int的存儲開銷也遠小於Integer
2、使用二分查找法判斷元素的位置,所以,在獲取數據的時候非常快,時間複雜度為O(lgN),比HashMap快的多,因為HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素。
3、使用場景
雖說SparseArray性能比較好,但是由於其添加、查找、刪除數據都需要先進行一次二分查找,所以在數據量大的情況下性能並不明顯,將降低至少50%。滿足下麵兩個條件我們可以使用SparseArray代替HashMap:
a:數據量不大,最好在千級以內,如果在數據量比較大時,它的性能將退化至少50%。
b:key必須為int類型,這中情況下的HashMap可以用SparseArray代替。