类似于Map中存放键值对, 只不过key存放在使用int数组中,而value存放在Object数组中;
核心思想: 采用二分法查询key对应的位置,然后取出值或者插入值
put方法
1.采用二分法查找,获取key在mKeys数组的下标 i
2.如果i >= 0, 说明key在mKeys数组已存在, mValues[i] = value
3.如果i < 0, 说明key在mKeys数组中不存在, i = ~i 按位取反, i 为要添加的元素在数组中的下标
3.1 mValues[i] == DELETED, 表示下标 i 位置的元素有移除过, 如果新添加的元素也是下标 i,mKey[i]和mValues[i] 重新赋值
3.2 mValues[i] != DELETED, 如果mKeys数组中还有元素未赋值, 可能会偏移mKeys数组和mValues数组中的元素; 如果mKeys数组中的元素都赋值过了,对mKeys数组和mValues数组进行扩容,并偏移mKeys数组和mValues数组中的元素.最后都会将key和value分别赋值给mKey[i]和mValues[i];
public void put(int key, E value) {
/**
* 采用二分法查找key,返回的是key在在mKeys数组的下标
*/
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//1.mKeys中包含key,value替换
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
//添加之前,数组下标i位置的元素被删除过
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);
}
//添加元素 2.mKeys中不包含key,并且mKeys中元素没有添加满,添加元素;3.mKeys中不包含key,并且mKeys中元素添加满了,扩容,并添加元素
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
get方法
采用二分法查找,获取key在mKeys数组的下标 i,并返回 i
通过反射,查看添加元素后的变化情况
SparseArray<String> sparseArray = new SparseArray<>(3);
sparseArray.put(5, "wislie");
sparseArray.put(1, "kotlin");
sparseArray.put(1, "java");
sparseArray.put(9, "python");
sparseArray.put(6, "react");
sparseArray.put(4, "flutter");
//打印结果
keys:[5, 0, 0] values:[wislie, null, null] size:1 isGarbage:false
keys:[1, 5, 0] values:[kotlin, wislie, null] size:2 isGarbage:false
keys:[1, 5, 0] values:[java, wislie, null] size:2 isGarbage:false
keys:[1, 5, 9] values:[java, wislie, python] size:3 isGarbage:false
keys:[1, 5, 6, 9, 0, 0, 0, 0, 0] values:[java, wislie, react, python, null, null, null, null, null] size:4 isGarbage:false
keys:[1, 4, 5, 6, 9, 0, 0, 0, 0] values:[java, flutter, wislie, react, python, null, null, null, null] size:5 isGarbage:false
优点
1.使用二分法, key以升序的方式排列, 提升了内存的利用率及访问效率
2.使用int数组存储int类型的key，避免了int到Integer的自动装箱机制
使用场景
元素个数少于1000, 增删不频繁, key是整型
