SparseArray、ArrayMap

前言

SparseArray、ArrayMap均为安卓官方开源的map,相比于HashMap,他们具有更高的性能,更加节约内存

SparseArray 介绍

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.
Note that this container keeps its mappings in an array data structure, using a binary search to find keys.

  • 整数映射到对象
  • 节约内存
  • 避免自动装包 (int转integer)
  • 映射不需要额外的对象
  • 使用二分查找

SparseArray源码分析

创建对象数组及int数组,默认大小为10

1
2
3
4
5
6
7
8
9
10
11
12
13
public SparseArray() {
this(10);
}
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;
}

二分查找key,如果存在即更新数据,不存在判断是否被标记为删除(值为DELETED对象),若标记为删除则重新赋值

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
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
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);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}

二分查找key,不存在标记为删除返回默认值

1
2
3
4
5
6
7
8
9
10
11
12
13
public E get(int key) {
return get(key, null);
}
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];
}
}

二分查找是否有该key,找到后将value赋值为DELETED对象,将mGarbage改为true

1
2
3
4
5
6
7
8
9
10
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}

调用一些方法时,会判断mGarbage,为true调用gc(),在gc方法中将不为DELETED的对象前移动

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
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);
}

扩容(数组put时调用该方法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static long[] insert(long[] array, int currentSize, int index, long element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}

小于4直接扩容到8,大于4即增加一倍

1
2
3
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}

ArrayMap介绍

ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional java.util.HashMap. It keeps its mappings in an array data structure – an integer array of hash codes for each item, and an Object array of the key/value pairs. This allows it to avoid having to create an extra object for every entry put in to the map, and it also tries to control the growth of the size of these arrays more aggressively (since growing them only requires copying the entries in the array, not rebuilding a hash map).

  • key->value(均为对象)
  • 相比于hashmap更节约内存
  • 两个数组,一个数组存放hash值,一个数组存放 key,value,key,value…

ArrayMap源码

无参构造函数中map容量为0,put时扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ArrayMap() {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
mSize = 0;
}
public ArrayMap(int capacity) {
if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity);
}
mSize = 0;
}

根据hash、key在mHashes数组中寻找index,index2为key存放位置,index2+1存放value,扩容时,若当前size大于2BaseSize则扩容为1.5当前size,小于2BaseSize且大于BaseSize扩容为2BaseSize,小于BaseSize则扩容为BaseSize

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
37
38
39
40
41
42
43
@Override
public V put(K key, V value) {
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (mSize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (mHashes.length > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, mSize);
}
if (index < mSize) {
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}

二分查找mHashes中index,index*2为key则表明已存储过(现在更新),否则从index往前往后寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
if (index < 0){
return index;
}
if (key.equals(mArray[index<<1])) {
return index;
}
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}

查找当前key对于index,在mArry中index*2+1即为对应value

1
2
3
4
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}