Android中的SpareArray和ArrayMap实现分析
日常开发中,常用的存储键值对的数据结构是HashMap
,根据Java笔记之HashMap保存数据和Java笔记之计算Java对象的大小及其应用可以知道,HashMap
存储键值对会占用比较多的内存控件,而对于内存限制较大的Android平台来说,为了避免这种浪费,官方推荐我们使用SpareArray
和ArrayMap
,本文对这两个类的实现进行分析比较。
SpareArray
以及他的衍生类都是以基本类型为key
,因为避免了自动装箱,并且用数组直接保存key、value(而非像HashMap
那样将其封装为Node
对象后再保存),因而节省了内存。
ArrayMap
则支持所有类型的key,他是将key
和value
全部保存在一个数组中(n
位为key
,n+1
位为value
),避免了将其封装为Node
对象带来的内存消耗。
当要保存的数据量比较小(小于几千个)的时候,如果KEY是基本类型,推荐使用SparseArray
及其衍生类以节省内存,如果KEY是其他类型则使用ArrayMap
;否则使用HashMap
更加高效。
SpareArray
SpareArray
以及他的衍生类主要用于以基本类型
为key
保存非大量数据的场景。
相比HashMap
而言,他的优点主要在于没有对保存的数据二次封装,没有对基本类型的数据自动装箱,存储单个数据的成本小,也没有hash
计算。
但他在添加数据时需要扩展数组(涉及到新建、复制数组,gc()
等),在删除数据时需要缩减数组 (查看gc()
等源码发现他的数组只会增加,不会缩减),以及通过二分法查找索引都会消耗性能。
为了避免每次删除时都需要缩减数组,
SpareArray
在删除数组时只会将其赋值为DELETED
,在下次调用其private void gc()
方法时丢弃掉这些数据
先看一下SpareArray
的结构:
1 | public class SparseArray<E> implements Cloneable { |
void put(int key, E value)
添加方法先用二分法查找key
对应的位置:
- 如果有,则直接覆盖
- 如果没有,则取反得到应该
插入的位置
,并分别插入key
和value
1 | public void put(int key, E value) { |
E get(int key)
获取数据,先用二分法查找,如果找到就返回对应的值
,否则返回null
。
1 | public E get(int key) { |
void remove(int key)
删除key
以及对应的数据
。
同样先用二分法查找对应位置
,有的话则标记为DELETED
,等待下次gc()
时丢弃。
1 | public void remove(int key) { |
gc()
在上文中我们看到,删除数据时,mGarbage
被标记为true
,这样当下一次进行put/valueAt/append/size
等涉及到数组大小查询、改动等时,就出触发gc()
以便整理数组结构。
1 | private void gc() { |
HashMap与SpareArray及其衍生类对应关系
参考下图
ArrayMap
ArrayMap
实现了Map<K, V>
接口,他的API和HashMap
相差无几,但是由于没有对数据再包装,动态调整数组的大小,一定范围内他比HashMap
内存效率高。
但是如果保存大量数据(超过千位)时,由于他需要二分法查找的影响会比HashMap
慢很多。
ArrayMap
特殊之处在于将key
,value
保存到了同一个数组mArray中(n位保存key,n+1位保存value)。
先看一下ArrayMap
的结构:
1 | static Object[] mBaseCache; |
在使用时:
计算
key
的hash值
,1
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
然后使用
indexOf()
在mHashes
中进行二分法查找对应的index
1
index = indexOf(key, hash);
indexOf()
方法会先用二分法查找hash
对应的index
,如果index<0
则返回index
;否则在对比mArray
中对应位置mArray[index<<1]
的key
与要查询的key
:- 两者一致:返回
index
- 两者不一致:从
index
开始,先向后,再向前查询是否有相同的key
,如果有返回对应index
- 以上都没有找到:对
mHashes
中最后一个与key的hash一致的后一位index
取反,并返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) {
return index;
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}- 两者一致:返回
V put(K key, V value)
当添加item
时,按照前述规则,先在mArray
中查找key
对应的索引index
:
index >= 0
:已经有键为key
的数据,直接覆盖旧值并返回index < 0
:没有键为key
的数据,对数组进行扩容,并保存对应数据1
2
3
4index = ~index;//上文indexOf()中计算得出的key应该添加的位置
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
V get(Object key)
get()
方法就比较简单了,先查找key
的索引,然后取出对应的数据value
并返回即可:
1 | public V get(Object key) { |
V remove(Object key)
remove()
方法也会先使用indexOfKey()
计算key的index
,然后删除对应位置的数据
。
此外,如果mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3
的话,还会缩减数组的大小
为osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2)
:
1 | public V removeAt(int index) { |