android 容器--ArrayMap
2019-11-05 本文已影响0人
往事一块六毛八
概述
-
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，用复制操作去覆盖元素达到删除的目的。
