美文网首页
android 容器--ArrayMap

android 容器--ArrayMap

作者: 往事一块六毛八 | 来源:发表于2019-11-05 15:13 被阅读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,用复制操作去覆盖元素达到删除的目的。

https://www.jianshu.com/p/1fb660978b14

相关文章

网友评论

      本文标题:android 容器--ArrayMap

      本文链接:https://www.haomeiwen.com/subject/pkzsbctx.html