Android源码系列(13) -- ArrayMap

Posted by phantomVK on September 16, 2018

一、类签名

ArrayMap 是通用的键值对映射数据结构,相比 HashMap 有更高内存利用率。因为 ArrayMap 使用数组结构保存映射:一个整形数组存放哈希值,一个 Object 数组存放 KeyValue

使用数组能避免为每个放入 Map 的entry创建额外对象(对比HashMap#Node),并能更有力地控制数组扩展的大小。

1
public final class ArrayMap<K, V> implements Map<K, V>

相比传统 HashMapArrayMap 速度更慢且不存放大量items的场景。因为ArrayMap通过二分查找搜索item,添加或移除元素需要操作数组的entries。容器仅持有数百个items时,两者性能差距不大。

ArrayMap_HASH_UML

为更平衡的内存利用率,ArrayMap不像其他标准Java容器类,它会在items移除同时缩小数组。也不能主动控制数组的大小:设置capacity后当任意item移除,数组大小会减少到刚好容纳所有item。

源码来自Android 26

二、常量

1
private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;

最低扩容容量

1
private static final int BASE_SIZE = 4;

cache size大小

1
private static final int CACHE_SIZE = 10;

特殊哈希数组值,表示container不可变

1
static final int[] EMPTY_IMMUTABLE_INTS = new int[0];

特殊不可变空ArrayMap常量表示空状态

1
public static final ArrayMap EMPTY = new ArrayMap<>(-1);

三、成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 缓存小数组对象避免垃圾回收
// mBaseCache[0]指向列表中的下一个数组
// mBaseCache[1]指向int[]
static Object[] mBaseCache;
static int mBaseCacheSize;

// 缓存小数组对象避免垃圾回收
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;

final boolean mIdentityHashCode;

// 哈希数组
int[] mHashes;

// 存放key-value的数组
Object[] mArray;

// 已保存items数量
int mSize;

MapCollections<K, V> mCollections;

四、构造方法

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
// 构造空ArrayMap,初始默认容量为0
public ArrayMap() {
    this(0, false);
}

// 根据给定容量值构造实例
public ArrayMap(int capacity) {
    this(capacity, false);
}

public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;

    if (capacity < 0) {
        // 此实例内容不可变,使用常量标记
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
        // 此实例内容可变,初始大小为0
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        // 根据指定大小进行构造
        allocArrays(capacity);
    }
    // 保存元素数量为0
    mSize = 0;
}

// 根据给定map构造实例
public ArrayMap(ArrayMap<K, V> map) {
    this();
    if (map != null) {
        putAll(map);
    }
}

五、静态方法

在保存hash的数组中,通过二分查找找出目标hash的索引值

1
2
3
4
5
6
7
8
9
10
11
private static int binarySearchHashes(int[] hashes, int N, int hash) {
    try {
        return ContainerHelpers.binarySearch(hashes, N, hash);
    } catch (ArrayIndexOutOfBoundsException e) {
        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            throw new ConcurrentModificationException();
        } else {
            throw e; // the cache is poisoned at this point, there's not much we can do
        }
    }
}

释放hash数组与key-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
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == (BASE_SIZE*2)) {
        // hashes.length == 8
        synchronized (ArrayMap.class) {
            // mTwiceBaseCacheSize最多保存10个
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                // 通过链表的方法保存
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                // 置空数组索引 [2,(size<<1)-1] 的entry
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mTwiceBaseCache = array;
                mTwiceBaseCacheSize++; // 已保存数量递增
            }
        }
    } else if (hashes.length == BASE_SIZE) {
        // hashes.length == 4
        synchronized (ArrayMap.class) {
            // mBaseCacheSize最多保存10个
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mBaseCache;
                array[1] = hashes;
                // 置空数组index [2,(size<<1)-1] 的entry
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++; // 已保存数量递增
            }
        }
    }
}

六、成员方法

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
// 通过key和hash找索引
int indexOf(Object key, int hash) {
    final int N = mSize;

    // ArrayMap为空,返回~0
    if (N == 0) {
        return ~0;
    }

    // 通过二分查找确认索引值
    int index = binarySearchHashes(mHashes, N, hash);

    // 索引小于零表示此key没有对应Entry
    if (index < 0) {
        return index;
    }

    // 该key和index所表示的'key'匹配,则表示index成功命中
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // 从index开始,检查后方索引的key是否匹配
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end; // 返回匹配的索引值
    }

    // 从index开始,检查前方索引的key是否匹配
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i; // 返回匹配的索引值
    }

    // 找不到对应key
    // 返回这个key的新条目可以直接插入的索引位置,值为负数
    // 方法直接使用哈希链的尾部位置,减少因插入而导致拷贝数组条目的数量
    return ~end;
}

int indexOfNull() {
    final int N = mSize;

    // ArrayMap为空,返回~0
    if (N == 0) {
        return ~0;
    }

    int index = binarySearchHashes(mHashes, N, 0);

    // 哈希值没有命中,表示此kay没有对应的条目
    if (index < 0) {
        return index;
    }

    // 该key和index所表示的'key'匹配,则表示index成功命中
    if (null == mArray[index<<1]) {
        return index;
    }

    // 从index开始,检查后方索引的key是否匹配
    int end;
    for (end = index + 1; end < N && mHashes[end] == 0; end++) {
        if (null == mArray[end << 1]) return end;
    }

    // 从index开始,检查前方索引的key是否匹配
    for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
        if (null == mArray[i << 1]) return i;
    }

    // 找不到对应key
    // 返回这个key的新条目可以直接插入的索引位置,值为负数
    // 方法直接使用哈希链的尾部位置,减少因插入而导致拷贝数组条目的数量
    return ~end;
}

// 分配数组空间
private void allocArrays(final int size) {
    // 若mHashes为EMPTY_IMMUTABLE_INTS,表示此ArrayMap是不可变的,并抛出异常
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }

    if (size == (BASE_SIZE*2)) {
        // size == 8,从缓存中复用数组
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) {
                final Object[] array = mTwiceBaseCache;
                mArray = array;
                // mTwiceBaseCache = mTwiceBaseCache[0]
                mTwiceBaseCache = (Object[])array[0];
                // 取出缓存的hashes赋值给mHashes复用
                mHashes = (int[])array[1];
                // 置空索引0和索引1的空间
                array[0] = array[1] = null;
                // 已缓存数组数量递减
                mTwiceBaseCacheSize--;
                return;
            }
        }
    } else if (size == BASE_SIZE) {
        // size == 4,从缓存中复用数组
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                // mBaseCache = mBaseCache[0]
                mBaseCache = (Object[])array[0];
                // 取出缓存的hashes赋值给mHashes复用
                mHashes = (int[])array[1];
                // 置空索引0和索引1的空间
                array[0] = array[1] = null;
                // 已缓存数组数量递减
                mBaseCacheSize--;         
                return;
            }
        }
    }
    
    // size大小不是4或8就创建新数组并赋值
    mHashes = new int[size];
    mArray = new Object[size<<1];
}

// 清空所有键值对数据
@Override
public void clear() {
    // 已保存元素数量不为空
    if (mSize > 0) {
        // ohashes 为 oldHashes
        final int[] ohashes = mHashes;
        // oarray 为 oldArray 
        final Object[] oarray = mArray;
        // osize 为 oldSize
        final int osize = mSize;
        // 设置EmptyArray.INT,表明为空
        mHashes = EmptyArray.INT;
        // 设置EmptyArray.OBJECT,表明为空
        mArray = EmptyArray.OBJECT;
        // 已保存item为0
        mSize = 0;
        // 释放数组空间
        freeArrays(ohashes, oarray, osize);
    }

    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
        throw new ConcurrentModificationException();
    }
}

// 清除所有items,但不减少ArrayMap已开辟空间
public void erase() {
    if (mSize > 0) {
        final int N = mSize<<1;
        final Object[] array = mArray;
        for (int i=0; i<N; i++) {
            array[i] = null;
        }
        mSize = 0;
    }
}

// 保证ArrayMap扩容到minimumCapacity个空间
public void ensureCapacity(int minimumCapacity) {
    final int osize = mSize;
    if (mHashes.length < minimumCapacity) {
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        // 创建新数组空间
        allocArrays(minimumCapacity);
        // 迁移items到新数组空间
        if (mSize > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, osize);
            System.arraycopy(oarray, 0, mArray, 0, osize<<1);
        }
        // 释放旧数组空间
        freeArrays(ohashes, oarray, osize);
    }

    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) {
        throw new ConcurrentModificationException();
    }
}

// 检查key是否包含在数组中
@Override
public boolean containsKey(Object key) {
    return indexOfKey(key) >= 0;
}

 // 返回key在集合中的索引
public int indexOfKey(Object key) {
    return key == null ? indexOfNull()
            : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

// 检查value在数组中的索引值
int indexOfValue(Object value) {
    final int N = mSize*2;
    final Object[] array = mArray;
    if (value == null) {
        // value为空,则查找第一个值为空的索引
        for (int i=1; i<N; i+=2) { // 每次递增2,保证索引指到值的位置上
            // array[i]匹配null
            if (array[i] == null) {
                return i>>1; // 整形值通过右移1位完成除以2的操作,即i/2
            }
        }
    } else {
        // value不为空,则查找第一个值匹配的索引
        for (int i=1; i<N; i+=2) { // 每次递增2,保证索引指到值的位置上
            // array[i]value
            if (value.equals(array[i])) {
                return i>>1; //  整形值通过右移1位完成除以2的操作,即i/2
            }
        }
    }

    // 集合中没有指定key,返回-1
    return -1;
}

// 检查value是否包含在数组中,此调用会对整个数组进行线性查找
@Override
public boolean containsValue(Object value) {
    return indexOfValue(value) >= 0;
}

// 根据key从数组中获取对应值,没有对应值则返回null
@Override
public V get(Object key) {
    // 根据key算出所在数组的索引值
    final int index = indexOfKey(key);
    // 从索引值取值,若索引值为负数,则返回null
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

// 根据key的索引从数组中取key
public K keyAt(int index) {
    // 根据索引值直接取key
    return (K)mArray[index << 1];
}

// 根据key的索引从数组中取value
public V valueAt(int index) {
    // 根据索引值直接取value
    return (V)mArray[(index << 1) + 1];
}

// 根据key的索引在数组中设置新值,已有旧值作为结果返回
public V setValueAt(int index, V value) {
    // 计算value索引
    index = (index << 1) + 1;
    // 获取旧元素
    V old = (V)mArray[index];
    // 存入新元素
    mArray[index] = value;
    // 返回旧元素
    return old;
}

// 检查数组是否为空
@Override
public boolean isEmpty() {
    return mSize <= 0;
}

// 向ArrayMap中存入新的<Key, value>,如果key有对应旧value,则旧value会被替换
@Override
public V put(K key, V value) {
    // 原数组元素数量
    final int osize = mSize;
    // 根据变量key算出来的哈希值
    final int hash;
    // 索引值
    int index;
    // key为空则搜索值为空的索引
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // 通过key计算hash
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        // key和hash查找索引
        index = indexOf(key, hash);
    }

    if (index >= 0) {
        // 已有key在mArray数组的索引
        index = (index<<1) + 1;
        // 取出旧值
        final V old = (V)mArray[index];
        // 数组相同位置存入新值
        mArray[index] = value;
        // 返回旧值
        return old;
    }

    index = ~index;
    if (osize >= mHashes.length) {
        // 计算n值:
        //   1. osize < BASE_SIZE   返回 BASE_SIZE
        //   2. BASE_SIZE <= osize < BASE_SIZE*2 返回 BASE_SIZE*2
        //   3. BASE_SIZE*2 <= osize               返回 osize+(osize>>1)
        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 (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }
        
        // ohashes元素全部复制到mHashes
        // oarray元素全部复制到mArray
        if (mHashes.length > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
        
        // 释放ohashes和oarray的空间
        freeArrays(ohashes, oarray, osize);
    }

    // 原有元素为新key-value腾出空位
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }

    // 数组已创建完毕,且原有元素位置都移动好,则在指定位置放入新key-value
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;

    // 以保存元素数量递增
    mSize++;
    return null;
}

// 不验证数组是否有足够空间即插入key-value
public void append(K key, V value) {
    int index = mSize;
    // kay的hash
    final int hash = key == null ? 0
            : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
    
    // 空间不足直接抛出异常
    if (index >= mHashes.length) {
        throw new IllegalStateException("Array is full");
    }

    if (index > 0 && mHashes[index-1] > hash) {
        RuntimeException e = new RuntimeException("here");
        e.fillInStackTrace();
        put(key, value);
        return;
    }

    // 空间足够,正常插入key-value
    mSize = index+1;
    // 存入哈希值
    mHashes[index] = hash;
    index <<= 1;
    // 存入key-value
    mArray[index] = key;
    mArray[index+1] = value;
}

// 使用append()会导致array maps失效,尤其是同一个key出现了多次
// 此方法验证array map是有效的,并在出现问题时抛出IllegalArgumentException
public void validate() {
    final int N = mSize;
    // 最多一个键值对的话,不可能存在重复,直接退出
    if (N <= 1) {
        return;
    }

    int basehash = mHashes[0]; // 初始index为0
    int basei = 0;

    // 先通过检查所有哈希值,看是否重复,如果哈希值不重复就算验证通过
    // 初始i为1,和index为0的哈希进行对比
    for (int i=1; i<N; i++) {
        int hash = mHashes[i];
        if (hash != basehash) {
            basehash = hash;
            basei = i;
            continue;
        }

        // 存在哈希值相同,向前检查看key是否出现重复
        final Object cur = mArray[i<<1];
        for (int j=i-1; j>=basei; j--) {
            final Object prev = mArray[j<<1];
            // 出现相同key
            if (cur == prev) {
                throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);
            }
            
            // 出现相同key
            if (cur != null && prev != null && cur.equals(prev)) {
                throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);
            }
        }
    }
}

// 把array变量中的所有键值对存入实例中
public void putAll(ArrayMap<? extends K, ? extends V> array) {
    // 获取当前实例array长度
    final int N = array.mSize;
    // 确保当前ArrayMap有足够空间保存array的所有元素
    ensureCapacity(mSize + N);

    if (mSize == 0) {
        // 原ArrayMap没有元素,批量插入所有新元素
        if (N > 0) {
            System.arraycopy(array.mHashes, 0, mHashes, 0, N);
            System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
            mSize = N;
        }
    } else {
        // 原ArrayMap有元素,逐个插入新元素
        for (int i=0; i<N; i++) {
            put(array.keyAt(i), array.valueAt(i));
        }
    }
}

// 从ArrayMap中移除该key和对应value
@Override
public V remove(Object key) {
    // 根据key查找对应索引
    final int index = indexOfKey(key);

    // 索引值大于0表示key存在
    if (index >= 0) {
        // 移除该key
        return removeAt(index);
    }
    
    // key没有找到,返回null
    return null;
}

// 根据给定的index移除目标键值对,方法结果返回键值对的值
public V removeAt(int index) {
    // 旧value的值old
    final Object old = mArray[(index << 1) + 1];
    // 原ArrayMap元素数量
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        freeArrays(mHashes, mArray, osize);
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        nsize = 0;
    } else {
        nsize = osize - 1;
        // mHashes.length > 8 && mSize < mHashes.length/3
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            // 缩小数组的空间,并且大小不低于BASE_SIZE*2
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);
            
            // 出现并发修改,抛出异常
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }
            
            if (index > 0) {
                // 从ohashes拷贝[0, index)到mHashes
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                // 从oarray拷贝[0,index << 1)到mArray
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }

            if (index < nsize) {
                // 从ohashes拷贝剩余items到mHashes
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                // 从oarray拷贝剩余items到mArray
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
        } else {
            if (index < nsize) {
                // mHashes数组,index后的hash逐个前移一位
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                // mArray数组,(index + 1) << 1后的元素前移
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
            // mArray最后两个空间置空 
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }
    mSize = nsize;
    return (V)old;
}

// 返回ArrayMap保存键值对数量
@Override
public int size() {
    return mSize;
}

// 检查元素和本实例是否等同
@Override
public boolean equals(Object object) {
    // 为同一个对象返回false
    if (this == object) {
        return true;
    }
    
    // 先检查对象object是否为Map的子类,不是则无法进行比较,返回false
    if (object instanceof Map) {
        Map<?, ?> map = (Map<?, ?>) object;
        // 先检查元素数量,以便快速确认失败并返回false
        if (size() != map.size()) {
            return false;
        }
        
        // 类型一致且数量一样,需要逐个对比元素是否一样
        try {
            for (int i=0; i<mSize; i++) {
                K key = keyAt(i);
                V mine = valueAt(i);
                Object theirs = map.get(key);
                if (mine == null) {
                    if (theirs != null || !map.containsKey(key)) {
                        return false;
                    }
                } else if (!mine.equals(theirs)) {
                    return false;
                }
            }
        } catch (NullPointerException ignored) {
            return false;
        } catch (ClassCastException ignored) {
            // 比较过程中元素类型转换抛出异常,返回false
            return false;
        }
        // 两个map的元素完全相同,返回true
        return true;
    }
    // 两个map的元素不完全相同,返回false
    return false;
}