一羹铅、SparseArray原理
SparseArray中采用的是雙數(shù)組的方式，在SparseArray有一個int數(shù)組和一個Object數(shù)組驹沿，SparseArray在remove的時候友多，也不會將內(nèi)存回收，而是對remove的index位置對應(yīng)的Object數(shù)組的數(shù)據(jù)設(shè)置為DELETED皂贩，DELETED也是一個Object對象，這樣做的目的是為了復(fù)用昆汹，因?yàn)镾parseArray插入數(shù)據(jù)會根據(jù)傳入的index進(jìn)行插入明刷，可能會在數(shù)組的中間插入，而如果有可以復(fù)用的满粗，那么就不需要復(fù)制拷貝的操作辈末，直接復(fù)用就可以了，這樣就省去了對數(shù)據(jù)復(fù)制拷貝移動的操作映皆，節(jié)約了性能的消耗挤聘。
SparseArray在增刪查詢的時候，對應(yīng)的key所在的索引位置捅彻，均是采用的二分查找的方式進(jìn)行组去。
二、SparseArray#put
1.SparseArray#put
public void put(int key, E value) {
// 通過二分查找查詢對應(yīng)的key在mKeys數(shù)組中的位置
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 如果i大于0步淹，說明mKeys中有該key从隆，則直接替換value
if (i >= 0) {
mValues[i] = value;
} else {
// 如果mKeys中沒有該key诚撵，則返回的是最接近且key的一個非運(yùn)算值
// 將該值再一次取非
i = ~i;
// 判斷該key是否滿足條件，并且是否是之前被remove的广料，如果是砾脑，則進(jìn)行復(fù)用
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果mSize大于mKeys數(shù)組長度，并且mGarbage為true艾杏，進(jìn)行g(shù)c回收
// mGarbage是在remove操作之后才置為true的韧衣，但是為true并不會立馬gc進(jìn)行回收
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 如果不能復(fù)用，則進(jìn)行正常的數(shù)據(jù)插入
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
2.ContainerHelpers#binarySearch
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; // value found
}
}
return ~lo; // value not present
}
3.GrowingArrayUtils#insert
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
// 在put的時候currentSize就是傳入的mSize
assert currentSize <= array.length;
// 如果currentSize+1之后還是小于等于array數(shù)組的長度
// 說明不需要擴(kuò)容购桑，可以直接將數(shù)據(jù)添加進(jìn)入
// 但是在添加的時候需要進(jìn)行數(shù)據(jù)的復(fù)制拷貝移動操作畅铭，將插入到當(dāng)前位置后續(xù)的數(shù)據(jù)向后移動一位
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
// 構(gòu)建新的數(shù)組
@SuppressWarnings("unchecked")
T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
growSize(currentSize));
// 將index位置前面的數(shù)據(jù)都從舊的數(shù)組中拷貝到新的數(shù)組中，拷貝index位置前面的index個數(shù)據(jù)
System.arraycopy(array, 0, newArray, 0, index);
// 對index位置進(jìn)行賦值
newArray[index] = element;
// 將舊的數(shù)組中的index位置開始向后的數(shù)據(jù)都拷貝到新的數(shù)組中
// 拷貝個數(shù)就是舊的數(shù)組長度減去index
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
// 數(shù)組擴(kuò)容時勃蜘，新的數(shù)組長度計算硕噩，是在當(dāng)前長度的基礎(chǔ)上進(jìn)行翻倍
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
三、SparseArray的刪除操作
remove操作其實(shí)就是將對應(yīng)位置上的value置為DELETED缭贡，并且將mGarbage設(shè)置為true
public void remove(int key) {
delete(key);
}
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
public void removeAt(int index) {
if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
// Check if exception should be thrown outside of the critical path.
throw new ArrayIndexOutOfBoundsException(index);
}
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
四炉擅、SparseArray的get操作
SparseArray的get操作，其實(shí)也是通過二分查找查詢到key在對應(yīng)的mKeys中的索引位置阳惹，然后找得到對應(yīng)的value谍失，如果value對應(yīng)的是DELETED或者索引位置小于0，則說明查詢不到對應(yīng)的數(shù)據(jù)莹汤，返回一個null或者自定義的一個返回值
public E get(int key) {
return get(key, null);
}
@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];
}
}
五快鱼、gc回收操作
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
// 這里的gc回收操作，其實(shí)就是回收index位置上value為DELETED的纲岭，將之置為null
// 并且將后續(xù)的數(shù)據(jù)全部前移一位
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;
// Log.e("SparseArray", "gc end with " + mSize);
}
