HashMap的缺点:
- 自动装箱导致的性能损失;
- 使用拉链法来解决hash冲突,如果hash冲突较多,需要遍历链表,导致性能下降,在Java 8 中,如果链表长度>8,会使用红黑树来代替链表;
- 由于loadFactor的存在,导致(1 - loadFactor) * capacity 的空间会浪费,capacity越大,浪费空间更多;
- 扩容时需要重新计算hash,浪费性能;
- 每一个value都由一个Node保存,Node除了保存本身的数据外,还需要其他冗余数据,如hash值,下一个节点的指针等;
SparseArray
的特点:
-
key
只能为int
类型,避免了自动装箱; - 使用二分法查找key,在查询指定key时需要进行二分查找,查询的时间复杂度为O(logN),添加删除亦如是;所以不适合大量数据,在数据量为1000以下(up to hundreds of items)时,其与HashMap之间的性能差别(difference)低于50%;
- 没有冗余数据;
- 为了提升性能,在删除数据时,并不马上调整压缩数组(压缩数组需要移动数组的元素),而是将被删除位置的value标记为DELETED,之后该位置可能被重用,在一次压缩中,清除掉所有的DELETED;
- 可以通过
keyAt(int)
和valueAt(int)
来遍历SparseArray
中的key
和value
; - 扩容时只是复制数组值,不需要进行hash计算;
总体来看,相对于HashMap
,SparseArray
是以时间换空间
;
SparseArray源码分析:
数据结构:
SparseArray
使用两个数组来分别存储key和value:
private int[] mKeys;// 存储key值的数组
private Object[] mValues;// 存储value值的数组 mKeys[i]---mValues[i]为一个键值对
private int mSize;// 存储键值对个数,确切地说,是当前存储的key值个数,key-value键值对均存储在数组中下标为 [0,mSize-1]之间的位置
private static final Object DELETED = new Object();// DELETED标记
private boolean mGarbage = false;// 用于判断是否需要进行压缩
构造方法:
public SparseArray() {
this(10);// 默认初始容量:10
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];// key value数组大小一致
}
mSize = 0;
}
添加key-value:
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);// 通过二分法查找key在mKeys中的索引
if (i >= 0) {
mValues[i] = value;// 覆盖已有值
} else {
// 如果没有找到,那么i值为 ~(0) 或 ~(mSize - 1),这里再取反,值就成了 0 或 (mSize - 1),参考源码 ContainerHelpers.binarySearch(mKeys, mSize, key)
i = ~i;
if (i < mSize && mValues[i] == DELETED) {// 刚好是一个被删除的值直接替换
mKeys[i] = key;
mValues[i] = value;
return;
}
// 需要通过gc(),腾出新的空间
if (mGarbage && mSize >= mKeys.length) {
gc();
// gc() 后索引变了,需要重新找个位置,重新二分查找,确定key/value在数组中的索引
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);// 插入新key
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);// 插入新值
mSize++;
}
}
上述部分引用方法如下:
// # ContainerHelpers.binarySearch(int[], int, int)
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
}
// # SparseArray.gc()
// 对 mKeys 和 mValues 进行重新排列,将mValues中标记为DELETED的值清除掉
private void gc() {
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;// 更新mSize
}
// # GrowingArrayUtils.insert(int[], int, int, int);
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;// 扩容为之前的两倍
}
public static int[] insert(int[] array, int currentSize, int index, int element) {
// 不需要扩容
if (currentSize + 1 <= array.length) {
// 将之后的所有元素向后移一位 这里的时间复杂度为O(N)
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;// 插入元素到指定位置
return array;
}
// 扩容
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;// 插入元素到指定位置
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
查询:
public E get(int key) {
return get(key, null);
}
// 获得指定key的值,如果没有,返回 valueIfKeyNotFound
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];
}
}
删除:
public void remove(int key) {
delete(key);
}
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);// 二分法找到位置
if (i >= 0) {
// 将值修改为 DELETED
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;// 需要垃圾回收,必要时检查该变量,并对 mKeys 和 mValues 进行重新排序
}
}
// 这里并没有将 mSize - 1,因为如果将 mSize - 1,需要重新对 mKeys 和 mValues 进行重新移动
}
综上,SparseArray的时间复杂度:
- 增:O(N);因为需要移动数组元素;
- 查:O(logN).使用二分法查找;
- 删:O(logN);查找到要删除的key之后,将其value标记为DELETED;
- 改:O(logN);同删除,只是将value改为新值而已;
如果key为long类型的话,可以使用LongParseArray,其实现与ParseArray相同,只是mKeys为long[]
如果key为int类型:
- value为int类型,可以使用SparseIntArray
- value为long类型,可以使用SparseLongArray
- value为boolean类型,可以使用SparseBooleanArray
跟多关于Android的SparseArray相关,参考视频: