Android ArrayMap

发表于 更新于 分类于

ArrayMap 是一种键值映射的数据结构，比 HashMap 更节省内存。它通过数组来存储映射关系，一个 int 数组存储 key 的 hash code，一个 Object 数组存储 key 和 value，可以避免在插入元素到 map 时创建额外的对象。

  1. ArrayMap 和 HashMap 类似。HashMap 是以空间换时间，ArrayMap 是以时间换空间。
  2. 节省内存。缓存机制（缓存 4 和 8 时的数组）。
  3. 非线程安全；
  4. 二分查找；
  5. 扩容机制。4 -> 8 -> 8+8/2=12 -> 12+12/2=18

基于 androidx.collection:collection:1.1.0.

类结构

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
Base implementation of ArrayMap that doesn't include any standard Java container API interoperability.
*/
public class SimpleArrayMap<K, V> {}

/**
ArrayMap is a generic key->value mapping data structure
that is designed to be more memory efficient than a traditional java.util.HashMap,
this implementation is a version of the platform's android.util.ArrayMap
that can be used on older versions of the platform.
*/
public class ArrayMap<K, V> extends SimpleArrayMap<K, V>
    implements Map<K, V> {}

arraymap_uml
arraymap_structure

  • mHashes 记录所有 key 的 hashcode 值组成的数组，从小到大排序，使用二分查找；
  • mArray 是一个记录着 key-value 键值对所组成的数组，是 mHashes 大小的 2 倍；

构造方法

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
/**
* Create a new empty ArrayMap.  The default capacity of an array map is 0, and
* will grow once items are added to it.
*/
public SimpleArrayMap() {
    mHashes = ContainerHelpers.EMPTY_INTS;
    mArray = ContainerHelpers.EMPTY_OBJECTS;
    mSize = 0;
}

/**
* Create a new ArrayMap with a given initial capacity.
*/
public SimpleArrayMap(int capacity) {
    if (capacity == 0) {
        mHashes = ContainerHelpers.EMPTY_INTS;
        mArray = ContainerHelpers.EMPTY_OBJECTS;
    } else {
        allocArrays(capacity);
    }
    mSize = 0;
}

/**
* Create a new ArrayMap with the mappings from the given ArrayMap.
*/
public SimpleArrayMap(SimpleArrayMap<K, V> map) {
    this();
    if (map != null) {
        putAll(map);
    }
}

默认的构造函数不分配内存，添加数据时根据需要分配，也可以在初始化时指定 ArrayMap 的大小，此时会分配内存。

添加数据

  1. V put(K key, V value)
  2. V putIfAbsent(K key, V value)
  3. void putAll(@NonNull SimpleArrayMap<? extends K, ? extends V> array)

key 可以为 null，但是至多有一个 null key。如果 key 不存在，返回 null, 否则返回旧 value。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
Add a new value to the array map.
key – The key under which to store the value. Must not be null. If this key already exists in the array, its value will be replaced.
value – The value to store for the given key.
Returns the old value that was stored for the given key, or null if there was no such key.
*/
@Nullable
public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    //key 为 null, hash 始终为 0，所以只能保存一条记录。
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // key 不为空，计算 key 的 hash 值
        hash = key.hashCode();
        // 查找元素在 mHashes 数组中的位置
        index = indexOf(key, hash);
    }
    //key 存在，返回旧值。
    if (index >= 0) {
        index = (index<<1) + 1;
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    index = ~index;
    //第一次添加数据或容量已满时扩容
    if (osize >= mHashes.length) {
        //4, 8, 8+8/2=12, 12+12/2=18
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= 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);
        }

        //释放旧数组内存，回收 4 和 8 的数组
        freeArrays(ohashes, oarray, osize);
    }

    //插入元素，需要将index位置后的数据通过拷贝往后移动一位
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    //添加数据，size 加 1，返回 null
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;
}

查找数据

  1. V get(Object key)
  2. V getOrDefault(Object key, V defaultValue)
1
2
3
4
5
6
7
8
9
10
11
@Nullable
public V get(Object key) {
    return getOrDefault(key, null);
}

public V getOrDefault(Object key, V defaultValue) {
    //获取在 mHashes 数组中的索引
    final int index = indexOfKey(key);
    //index < 0 返回默认值；否则返回在 mArray 数组中的值
    return index >= 0 ? (V) mArray[(index << 1) + 1] : defaultValue;
}

主要是通过二分查找得到 key 在 mHashes 数组中的位置 index，再根据 index 在 mArray 数组中得到查找的值。

删除数据

  1. V remove(Object key)
  2. boolean remove(Object key, Object value)
  3. V removeAt(int 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Remove the key/value mapping at the given index.
* @param index The desired index, must be between 0 and {@link #size()}-1.
* @return Returns the value that was stored at this index.
*/
public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    //只有一条记录
    if (osize <= 1) {
        freeArrays(mHashes, mArray, osize);
        mHashes = ContainerHelpers.EMPTY_INTS;
        mArray = ContainerHelpers.EMPTY_OBJECTS;
        nsize = 0;
    } else {
        nsize = osize - 1;
        //容量大于 8，而且数据量小于容量的 1/3 时，回收内存
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            // Shrunk enough to reduce size of arrays.  We don't allow it to
            // shrink smaller than (BASE_SIZE*2) to avoid flapping between
            // that and BASE_SIZE.
            //计算需要的容量，最小容量为 8，可以避免从 4 到 8 扩容
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            // 分配更小容量的数组
            allocArrays(n);

            //复制数据到新数组
            if (index > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
        } else {
            //当被移除的元素不是数组最末尾的元素时，则需要将后面的数组往前移动
            if (index < nsize) {
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
            //删除旧值
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    mSize = nsize;
    return (V)old;
}

缓存机制

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//只缓存长度是 4 和 8 的数组
private static final int BASE_SIZE = 4;
//最大缓存数量，避免无限缓存
private static final int CACHE_SIZE = 10;
//静态变量，所有实例共享
static @Nullable Object[] mBaseCache;
static int mBaseCacheSize;
static @Nullable Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;

//如果存在一倍或二倍缓存，则直接使用缓存，否则使用创建新数组。
private void allocArrays(final int size) {
    if (size == (BASE_SIZE*2)) {
        synchronized (SimpleArrayMap.class) {
            if (mTwiceBaseCache != null) {
                final Object[] array = mTwiceBaseCache;
                mArray = array;
                mTwiceBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mTwiceBaseCacheSize--;
                return;
            }
        }
    } else if (size == BASE_SIZE) {
        synchronized (SimpleArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                return;
            }
        }
    }

    mHashes = new int[size];
    mArray = new Object[size<<1];
}

//只缓存容量为 4 和 8 的数组。其他容量的数组由 GC 回收。
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == (BASE_SIZE*2)) {
        synchronized (SimpleArrayMap.class) {
            //缓存未满
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                //array[0]指向原来的缓存池
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                //释放剩余的内存空间
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                //mTwiceBaseCache指向新加入缓存池的array
                mTwiceBaseCache = array;
                mTwiceBaseCacheSize++;
            }
        }
    } else if (hashes.length == BASE_SIZE) {
        synchronized (SimpleArrayMap.class) {
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mBaseCache;
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++;
            }
        }
    }
}

缓存的第一条元素缓存 key-value 数组，第二条元素缓存 hash 数组。

arraymap_cache1
arraymap_cache2

相关的数据结构

  1. ArraySet
  2. SparseArray/SparseBooleanArray/SparseIntArray
  3. LongSparseArray

参考

[1] 深度解读 ArrayMap 优势与缺陷 - Gityuan