概述
-
ArrayMap 实现了implements Map<K, V>接口,所以它也是一个关联数组、哈希表。存储以key->value 结构形式的数据。它也是线程不安全的,允许key为null,value为null。
-
它相比HashMap,空间效率更高。
-
它的内部实现是基于两个数组。
一个int[]数组,用于保存每个item的hashCode.
一个Object[]数组,保存key/value键值对。容量是上一个数组的两倍。
它可以避免在将数据插入Map中时额外的空间消耗(对比HashMap)。
而且它扩容的更合适,扩容时只需要数组拷贝工作,不需要重建哈希表。
和HashMap相比,它不仅有扩容功能,在删除时,如果集合剩余元素少于一定阈值,还有收缩(shrunk)功能。减少空间占用。 -
因为其会对key使用二分法进行从小到大排序,
在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作。所以其是按照key的排序存储的。
总结
*每次插入时,根据key的哈希值,利用二分查找,去寻找key在int[] mHashes数组中的下标位置。
- 如果出现了hash冲突,则从需要从目标点向两头遍历,找到正确的index。
- 扩容时,会查看之前是否有缓存的 int[]数组和object[]数组
- 如果有,复用给mArray mHashes
- 容规则:如果容量大于8,则扩容一半。(类似ArrayList)
- 根据key的hash值在mHashs中的index,如何得到key、value在mArray中的下标位置呢?key的位置是index2,value的位置是index2+1,也就是说mArray是利用连续的两位空间去存放key、value。
- 根据元素数量和集合占用的空间情况,判断是否要执行收缩操作
*如果 mHashes长度大于8,且 集合长度 小于当前空间的 1/3,则执行一个 shrunk,收缩操作,避免空间的浪费 - 类似ArrayList,用复制操作去覆盖元素达到删除的目的。
网友评论