SparseArray簡(jiǎn)介(來(lái)源于文件頭注釋，android-23)
SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.
SparseArrays將整數(shù)映射到對(duì)象洞豁。與普通的對(duì)象數(shù)組不同粟瞬，索引中可能存在空白材蹬。它的目的是比使用HashMap將整數(shù)映射到對(duì)象的方式更節(jié)省內(nèi)存，這是因?yàn)樗?strong>避免了在鍵上自動(dòng)裝箱，而且它的數(shù)據(jù)結(jié)構(gòu)不依賴于每個(gè)映射額外的Entry條目對(duì)象蜒谤。
Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.
請(qǐng)注意棘劣，此容器將其映射保存在數(shù)組數(shù)據(jù)結(jié)構(gòu)中俏让，使用二分查找查找鍵。此實(shí)現(xiàn)不適合可能包含大量項(xiàng)的數(shù)據(jù)結(jié)構(gòu)。它通常比傳統(tǒng)的HashMap慢首昔，因?yàn)椴檎倚枰嫠阉鞴押龋砑雍蛣h除需要在數(shù)組中插入和刪除條目。對(duì)于容納數(shù)百個(gè)條目的容器勒奇，性能差異不顯著预鬓，小于50%。
To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-used for the same key, or compacted later in a single garbage collection step of all removed entries. This garbage collection will need to be performed at any time the array needs to be grown or the the map size or entry values are retrieved.
為了提高性能赊颠，容器在刪除鍵時(shí)進(jìn)行了優(yōu)化：不立即壓縮數(shù)組格二，而是將刪除的條目標(biāo)記為deleted。然后可以對(duì)相同的鍵重用該條目竣蹦，或者稍后在所有已刪除條目單獨(dú)垃圾收集步驟中壓縮該條目顶猜。在任何需要增長(zhǎng)數(shù)組或檢索映射大小或條目值的時(shí)候，都需要執(zhí)行此垃圾收集痘括。
It is possible to iterate over the items in this container using {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using <code>keyAt(int)</code> with ascending values of the index will return the keys in ascending order, or the values corresponding to the keys in ascending order in the case of <code>valueAt(int)</code>.
可以使用{@link #keyAt(int)}和{@link #valueAt(int)}迭代此容器中的項(xiàng)长窄。使用具有索引升序值的<code>keyAt(int)</code>對(duì)鍵進(jìn)行迭代，將按升序返回鍵纲菌，或者在<code>valueAt(int)</code>的情況下挠日，按升序返回鍵對(duì)應(yīng)的值。
特性
- 提供的
put翰舌，get操作仿Map肆资，內(nèi)部數(shù)據(jù)結(jié)構(gòu)采用兩個(gè)數(shù)組實(shí)現(xiàn)，一個(gè)存儲(chǔ)鍵（key灶芝，且類型為int郑原，限制了存儲(chǔ)的key類型），一個(gè)存儲(chǔ)值（value） - 初始容量為10
- key所在位置索引（index）通過(guò)二分查找確定夜涕，不適合大量數(shù)據(jù)存儲(chǔ)
- 采用原型模式犯犁，繼承
Cloneable，實(shí)現(xiàn)克隆邏輯
操作介紹
1. 查詢操作get
public E get(int key) {
return get(key, null);
}
public E get(int key, E valueIfKeyNotFound) {
// 根據(jù)key女器，在鍵數(shù)組中執(zhí)行二分查找
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 二分查找索引小于零表示未查找到酸役，mValues數(shù)組條目?jī)?nèi)容為DELETED表示數(shù)據(jù)已移除，這兩種都返回默認(rèn)值
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
1.1 二分查找
static int binarySearch(int[] array, int size, int value) {
int lo = 0; // 哨兵low
int hi = size - 1; // 哨兵high
while (lo <= hi) {
// 計(jì)算二分索引驾胆，無(wú)符號(hào)右移1位涣澡，相當(dāng)于除以2
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];// while條件下，不管上述移位如何運(yùn)算丧诺，mid下標(biāo)肯定不會(huì)越界
if (midVal < value) {
lo = mid + 1; // low從mid+1開(kāi)始
} else if (midVal > value) {
hi = mid - 1; // high從mid-1開(kāi)始
} else {
return mid; // value found
}
}
// 注意：未查找到入桂，返回負(fù)值
return ~lo; // value not present
}
2. 存入操作put
public void put(int key, E value) {
// 二分查找key所在索引位置
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 在值數(shù)組mValues中索引i位置存入value
mValues[i] = value;
} else {
i = ~i; // 按位非
// 復(fù)用被移除對(duì)象在mValues的槽位
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 索引位置無(wú)法查找到，說(shuō)明key并不在現(xiàn)有mKeys數(shù)組內(nèi)驳阎，需要擴(kuò)容
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
3. 移除操作delete
public void remove(int key) {
delete(key);
}
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
// 二分查找查詢數(shù)組的索引
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
// 先標(biāo)記成DELETED抗愁，并不立即縮減數(shù)組
mValues[i] = DELETED;
mGarbage = true;
}
}
}
3.1 指定索引移除操作
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
3.2 指定范圍移除操作
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
4. append操作
public void append(int key, E value) {
// 容量判斷
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
// 移除過(guò)數(shù)據(jù)需要gc
if (mGarbage && mSize >= mKeys.length) {
gc();
}
// 數(shù)組擴(kuò)容
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}
5. gc操作及時(shí)機(jī)
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize; // 當(dāng)前大小
int o = 0;// 哨兵oldIndex
int[] keys = mKeys;
Object[] values = mValues;
// 遍歷value數(shù)組馁蒂，發(fā)現(xiàn)GC對(duì)象，調(diào)整key和value數(shù)組
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;
}
// 無(wú)需gc的場(chǎng)景蜘腌， o和i保持一致沫屡，持續(xù)自增；一旦出現(xiàn)DELETED值撮珠，在整個(gè)遍歷的環(huán)節(jié)沮脖，o會(huì)落后于i
o++;
}
}
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
gc時(shí)機(jī)
前提有數(shù)據(jù)被移除，value成為DELETED芯急。gc時(shí)機(jī)勺届，原則上遵循頭文件的描述，具體如下：
- 加入數(shù)據(jù)（put或append）
- 根據(jù)索引訪問(wèn)key或value
- 根據(jù)key或value獲取索引（key是通過(guò)二分查找index志于，value是通過(guò)遍歷比對(duì)value獲取index）
- 指定索引位置設(shè)置value
- 訪問(wèn)當(dāng)前大小
