本文为个人学习笔记分享，没有任何商业化行为，对其他文章的引用都会标记。如有侵权行为，请及时提醒更正！如需转载请表明出处
大家都知道真的HashMap Key值为integer时，为了防止包装类型频繁的装箱，Android推出了SparseArray来代替这种情况。SparseArray为什么高效？它有什么缺点？
从SparseArray类的类介绍中主要提到了两个点：
1.通过二分查找查找对应的Key，比HashMap速度快。但当数据量大时，效率是低于HashMap的。
2.为了提高性能，SparseArray对删除操作进行了优化，删除操作不会立刻执行压缩数组，而是标记删除已删除的条目，复用Key值。真正的删除操作会在索引或者Map数量增加时压缩。
一、SparseArray的数据结构
1.数据结构
private int[] mKeys;
private Object[] mValues;
由此可见，SparseArray的数据结构就是有一个索引数组和一个对象数组组成。
2.构造方法
/**
* Creates a new SparseArray containing no mappings.
*/
public SparseArray() {
this(10);
}
/**
* Creates a new SparseArray containing no mappings that will not
* require any additional memory allocation to store the specified
* number of mappings. If you supply an initial capacity of 0, the
* sparse array will be initialized with a light-weight representation
* not requiring any additional array allocations.
*/
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
SparseArray初始容量为10，可以通过构造函数自定义的大小。
3.Put方法
/**
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
//二分查找 返回对于key的位置,如果没找到返回<0的值。
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//找到位置。
if (i >= 0) {
mValues[i] = value;
} else {
//对搜索结果取反
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
//此判断 复用已经删除的key
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
// 需要回收或者容量大于数组的长度，需要触发gc()，此gc非VM的gc
gc();
//重新对key进行搜索
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//插入数据。
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
查看put的源码，查询使用二分查找提高效率，并对key进行复用，防止频发触发扩容。
4.gc方法
此gc非彼gc，gc的作用是对标记的对象进行整理，压缩重排数组，通过标记算法，可以减少数组的重新整理，提高效率。
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
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);
}
5.get方法
使用二分查找，时间复杂度O(log2).还可以自定义当没有搜索到数据时的返回值。
/**
* Gets the Object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
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];
}
}
SparseArray的源码其实很简单，而且思路特别清晰。只有大家多读源码才会发现其实没那么复杂。
总结一下
优点：
1.SparseArray代替Key为Int类型的HashMap，避免频繁装箱，提高效率。
2.SparseArray采用二分查找，效率高
3.SparseArray删除是假删除，复用Key，减少数组的重排，提高内存的使用效率。
缺点：
插入时会对Key进行排序
当数据量大的时候，gc操作会经常被触发，效率比HashMap还低。
建议数据量在小于1000的情况下使用SparseArray。
所以大家可以根据实际情况合理的选择适合自己的数据结构。
大家多多点赞，多多关注呀。你们的夸赞是我写作的动力
网友评论