分析版本：support-v4-22.2.1

ArrayMap 继承于 SimpleArrayMap ，实现了 Map 接口中的所有方法。

ArrayMap

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
    MapCollections<K, V> mCollections;

    public ArrayMap() {
        super();
    }

    /**
     * 给定大小的ArrayMap
     */
    public ArrayMap(int capacity) {
        super(capacity);
    }

    /**
     * 通过一个ArrayMap或者SimpleArrayMap来实现一个ArrayMap
     */
    public ArrayMap(SimpleArrayMap map) {
        super(map);
    }

    /**
     * 得到Map集合
     */
    private MapCollections<K, V> getCollection() {
        if (mCollections == null) {
            mCollections = new MapCollections<K, V>() {
                @Override
                protected int colGetSize() {
                    return mSize;
                }

                //mArray存的是值，该变量在SimpleArrayMap中
                @Override
                protected Object colGetEntry(int index, int offset) {
                    return mArray[(index<<1) + offset];
                }

                //通过key得到位置索引
                @Override
                protected int colIndexOfKey(Object key) {
                    return indexOfKey(key);
                }

                //通过value得到位置索引
                @Override
                protected int colIndexOfValue(Object value) {
                    return indexOfValue(value);
                }

                @Override
                protected Map<K, V> colGetMap() {
                    return ArrayMap.this;
                }

                @Override
                protected void colPut(K key, V value) {
                    put(key, value);
                }

                @Override
                protected V colSetValue(int index, V value) {
                    return setValueAt(index, value);
                }

                @Override
                protected void colRemoveAt(int index) {
                    removeAt(index);
                }

                @Override
                protected void colClear() {
                    clear();
                }
            };
        }
        return mCollections;
    }

    /**
     * 通过调用MapCollections的containsAllHelper来判断该ArrayMap是否包含collection
     */
    public boolean containsAll(Collection<?> collection) {
        return MapCollections.containsAllHelper(this, collection);
    }

    /**
     * 将Map的类中的内容添加到ArrayMap中
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        ensureCapacity(mSize + map.size());
        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    /**
     * 通过调用MapCollections的removeAllHelper来除掉collection中有的值
     */
    public boolean removeAll(Collection<?> collection) {
        return MapCollections.removeAllHelper(this, collection);
    }

    /**
     * 取ArrayMap和collection的交集
     */
    public boolean retainAll(Collection<?> collection) {
        return MapCollections.retainAllHelper(this, collection);
    }

    /**
     * 返回一个set用来遍历，注意：这是一个小效率非常低的方法，会产生很多平时变量
     *
     * Note: the semantics of this
     * Set are subtly different than that of a HashMap: most important,
     * the Map.Entry object returned by its iterator is a single
     * object that exists for the entire iterator, so you can not hold on to it
     * after calling Iterator.next.
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        return getCollection().getEntrySet();
    }

    /**
     * 返回一个set用来遍历key，注意：这是一个小效率非常低的方法，会产生很多平时变量
     */
    @Override
    public Set<K> keySet() {
        return getCollection().getKeySet();
    }

    /**
     * 返回一个Collections用来遍历value，注意：这是一个小效率非常低的方法，会产生很多平时变量
     */
    @Override
    public Collection<V> values() {
        return getCollection().getValues();
    }
}

ArrayMap 中的具体实现方法是在 SimpleArrayMap 中实现的，而 ArrayMap 中实现 Map 接口的方法中，许多不建议使用，因为相比起 HashMap 等，效率要低的多。

SimpleArrayMap

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
public class SimpleArrayMap<K, V> {
  
    /**
     * The minimum amount by which the capacity of a ArrayMap will increase.
     * This is tuned to be relatively space-efficient.
     */
    private static final int BASE_SIZE = 4;
  
    /**
     * Maximum number of entries to have in array caches.
     */
    private static final int CACHE_SIZE = 10;
  
    int[] mHashes;
    Object[] mArray;
    int mSize;

    /**
     * Caches of small array objects to avoid spamming garbage.  The cache
     * Object[] variable is a pointer to a linked list of array objects.
     * The first entry in the array is a pointer to the next array in the
     * list; the second entry is a pointer to the int[] hash code array for it.
     */
    static Object[] mBaseCache;
    static int mBaseCacheSize;
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;
  
    /**
     * 创建一个空的ArrayMap，默认容量是0
     */
    public SimpleArrayMap() {
        mHashes = ContainerHelpers.EMPTY_INTS;//static final int[] EMPTY_INTS = new int[0];
        mArray = ContainerHelpers.EMPTY_OBJECTS;// static final Object[] EMPTY_OBJECTS = new Object[0];
        mSize = 0;
    }

    /**
     * 创建一个给定容量的ArrayMap
     */
    public SimpleArrayMap(int capacity) {
        if (capacity == 0) {
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
    }

    /**
     * 通过一个ArrayMap来创建一个新的ArrayMap
     */
    public SimpleArrayMap(SimpleArrayMap map) {
        this();
        if (map != null) {
            putAll(map);
        }
    }
  
    /**
     * 扩容，分配新的数组
     */
	private void allocArrays(final int size) {
        //如果是8
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
				//如果mTwiceBaseCache不为null
                if (mTwiceBaseCache != null) {
                	//将mTwiceBaseCache赋值给mArray
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    //将之前保存在0和1的拿出来
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    //清空
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    return;
                }
            }
        } else if (size == BASE_SIZE) {//如果是4
            synchronized (ArrayMap.class) {
				//如果mBaseCache不为null
                if (mBaseCache != null) {
                	//将mBaseCache赋值给mArray
                    final Object[] array = mBaseCache;
                    mArray = array;
                    //将之前保存在0和1的拿出来
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    //清空
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    return;
                }
            }
        }
		//创建mHashes数组和mArray数组
        mHashes = new int[size];
        mArray = new Object[size<<1];
    }
  
    public void putAll(SimpleArrayMap<? extends K, ? extends V> array) {
        final int N = array.mSize;
        //确认目前数组放的下
        ensureCapacity(mSize + N);
        //当前数组没有值
        if (mSize == 0) {
            if (N > 0) {//将内容复制到mHash和mArray中
                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
                mSize = N;
            }
        } else {//如果原来就有值，那么直接通过for循环将信息写入
            for (int i=0; i<N; i++) {
                put(array.keyAt(i), array.valueAt(i));
            }
        }
    }
  
    /**
     * 判断目前数组是否够大
     */
    public void ensureCapacity(int minimumCapacity) {
        if (mHashes.length < minimumCapacity) {
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            //分配数组（创建新的数组）
            allocArrays(minimumCapacity);
            //把旧的数组信息整到新的数组上
            if (mSize > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, mSize);
                System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
            }
            //释放
            freeArrays(ohashes, oarray, mSize);
        }
    }
  
	private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        //如果是8
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                //此时mTwiceBaseCacheSize值为0，必然小于CACHE_SIZE
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                	//将现有的mTwiceBaseCache赋值给数组的第一个
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
					//清除剩下的
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    //将数组赋值给mTwiceBaseCache，就是将mTwiceBaseCache替换掉了，原来的mTwiceBaseCache在该数组的第0位置上
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                }
            }
        } else if (hashes.length == BASE_SIZE) {//如果是4
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                	//将mBaseCache赋值给数组的第一个
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    //清除剩下的
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    //将数组赋值给mBaseCache
                    mBaseCache = array;
                    mBaseCacheSize++;
                }
            }
        }
    }
}

put(K key, V 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
public class SimpleArrayMap<K, V> {
  
    public V put(K key, V value) {
        //当前值的hash
        final int hash;
        //当前值的索引
        int index;
        if (key == null) {//如果key为null，那么hash为0
            hash = 0;
            index = indexOfNull();//找得到返回正数，找不到返回负数
        } else {//如果key不为null，那么hash就是keyhashCode值
            hash = key.hashCode();
            index = indexOf(key, hash);//找得到返回正数，找不到返回负数
        }
        //如果index的值是大于等于0的
        if (index >= 0) {
        	//index*2+1，即value的位置
            index = (index<<1) + 1;
            //得到旧的value
            final V old = (V)mArray[index];
            //将新的value赋值进去
            mArray[index] = value;
            //返回旧的value
            return old;
        }
		//如果index为负，那么这里变为正数
        index = ~index;
        if (mSize >= mHashes.length) {//现有的值的数量与hash数组大小对比
        	//mSize如果大于等于8，那么n=mSize+mSize/2;如果mSize小于8且大于等4，n=8；如果mSize小于4，n=4
            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);
        }
		//将index后面的内容往后面移
        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;
    }
  
    int 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;
        }
		//二分查找hash值对应的key
        int index = ContainerHelpers.binarySearch(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.
        //如果找到，判断key是否正确
        if (key.equals(mArray[index<<1])) {
            return index;
        }

        //如果key的equals方法不匹配，找对应的key，先往后找
        // 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;//找不到，返回一个负数出去
    }

    int indexOfNull() {
        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }
		//二分查找hash值对应的key
        int index = ContainerHelpers.binarySearch(mHashes, N, 0);

        // 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.
        //如果找到，判断key是否正确
        if (null == mArray[index<<1]) {
            return index;
        }

        //找对应的key
        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == 0; end++) {
            if (null == mArray[end << 1]) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
            if (null == 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;
    }
}

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
public class SimpleArrayMap<K, V> {

    public V removeAt(int index) {
        final Object old = mArray[(index << 1) + 1];
        if (mSize <= 1) {//清空
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
            mSize = 0;
        } else {
            //当大小大于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.
                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
                //临时变量存放旧hash数组和array数组
                final int[] ohashes = mHashes;
                final Object[] oarray = mArray;
                //分配新的数组
                allocArrays(n);

                mSize--;
                //将原先的数组的index之前的值传进去
                if (index > 0) {
                    System.arraycopy(ohashes, 0, mHashes, 0, index);
                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
                }
                //要删除的index值小于现在的大小
                if (index < mSize) {
                    //将index后面的赋值到新的数组中
                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
            } else {//不需要重新分配数组
                mSize--;
                if (index < mSize) {
                    //将index后面的往前移
                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
                //对应的位置设为null
                mArray[mSize << 1] = null;
                mArray[(mSize << 1) + 1] = null;
            }
        }
        return (V)old;
    }
}

remove 方法在特定情况下会进行内存重新分配，保证 ArrayMap 的内存合理区间，减少对内存的占用

其他 API

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
75
76
77
78
79
80
81
82
83
84
85
public class SimpleArrayMap<K, V> {

    //清空
    public void clear() {
        if (mSize != 0) {
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
            mSize = 0;
        }
    }
  
    //是否包含这个key
    public boolean containsKey(Object key) {
        return indexOfKey(key) >= 0;
    }
  
    //key的索引
    public int indexOfKey(Object key) {
        return key == null ? indexOfNull() : indexOf(key, key.hashCode());
    }
  
    //value的索引 
    int indexOfValue(Object value) {
        final int N = mSize*2;
        final Object[] array = mArray;
        if (value == null) {
            for (int i=1; i<N; i+=2) {
                if (array[i] == null) {
                    return i>>1;
                }
            }
        } else {
            for (int i=1; i<N; i+=2) {
                if (value.equals(array[i])) {
                    return i>>1;
                }
            }
        }
        return -1;
    }
  
    //是否包含这个value
    public boolean containsValue(Object value) {
        return indexOfValue(value) >= 0;
    }
  
    //通过key得到value
    public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }
  
    //得到index索引位置上的key
    public K keyAt(int index) {
        return (K)mArray[index << 1];
    }

    //得到index索引上的value
    public V valueAt(int index) {
        return (V)mArray[(index << 1) + 1];
    }
  
    //设置index索引上的value
    public V setValueAt(int index, V value) {
        index = (index << 1) + 1;
        V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    //通过key来删除
    public V remove(Object key) {
        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }
        return null;
    }
  
    //大小
    public int size() {
        return mSize;
    }
}

图说

ArrayMap 结构

结构

查找

查找

当要获取某个 value 的时候，ArrayMap 会计算输入 key 转换过后的 hash 值，然后对 hash 数组使用二分查找法寻找到对应的 index，然后我们可以通过这个 index 在另外一个数组中直接访问到需要的键值对。如果在第二个数组键值对中的 key 和前面输入的查询 key 不一致，那么就认为是发生了碰撞冲突。为了解决这个问题，会以该 key 为中心点，分别上下展开，逐个去对比查找，直到找到匹配的值。

删除插入

删除插入

ArrayMap 的插入与删除的效率是不够高的，但是如果数组的列表只是在一百这个数量级上，则完全不用担心这些插入与删除的效率问题。

与 HashMap 内存占用对比

与 HashMap 内存占用对比

总结

  • ArrayMap 根本不是哈希表，其实就是一个二叉查找树。有两个数组：key 的 hash 值数组，与对象数组的 key 索引对应，该数组用于二分查找；对象数组，存储真正的键值对，偶数索引是 key ，奇数索引是 value
  • 为了快速扩展数组空间，使用了 static 的 array cache
  • mBaseCache，如果 ArrayMap 的数据量从 4，增加到 8，用该数组保存之前使用的 mHashes 和 mArray ，这样如果数据量再变回 4 的时候，可以再次使用之前的数组，不需要再次申请空间，这样节省了一定的时间；
  • ArrayMap 可以使用 index 遍历，会快一些
  • ArrayMap 提供了数组收缩的功能，在 clear 或 remove 后，会重新收缩数组

最适合的使用场景

  • 对象个数的数量级最好是千以内
  • 数据组织形式包含 Map 结构

参考