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代替，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/547733.html
標籤：其他
上一篇：掃一掃，原來這么簡單