美文网首页
ArrayMap分析

ArrayMap分析

作者: 我要离开浪浪山 | 来源:发表于2023-03-21 07:15 被阅读0次

    1、ArrayMap是什么

    • key-value键值映射的数据结构,相比HashMap内存空间占用更少内存管理效率高;
    • Android提供了内存效率更高的ArrayMap,解决HashMap更占内存的弊端;
    • ArrayMap是Android专门针对内存优化而设计的,用于取代Java API中的HashMap数据结构。
    • 为了更进一步优化key是int类型的Map,Android再次提供效率更高的数据结构SparseArray,可避免自动装箱过程。
    • 对于key为其他类型则可使用ArrayMap。
    • HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的,而SparseArray和ArrayMap性能略逊于HashMap,但更节省内存。

    2、ArrayMap是google 在Android平台上作出优化后的类

    很多人可能会觉得对ArrayMap陌生,但是其实不然,在Android 源码中大量地使用了arraymap进行内存中的数据储存和管理。

    举个例子 intent 传值:

    val intent = Intent()
    intent.putExtra("key","value")
    

    intent传值:


    d65d011dd3ec2fb4e0722ade777c682.png
     BaseBundle(@Nullable ClassLoader loader, int capacity) {
            mMap = capacity > 0 ?
                    new ArrayMap<String, Object>(capacity) : new ArrayMap<String, Object>();
            mClassLoader = loader == null ? getClass().getClassLoader() : loader;
        }
    

    bundle本质就是一个arrayMap

    3、那为什么Google使用Arraymap代替hashmap呢?我们使用它的时候有什么好处呢?

    操作大量数据的情况:五万条(执行速度对比):

    00432a61261a4ba2fc7949c3d82242a.png

    少量数据效果对比:500条(执行速度对比):

    b11efc2ce9c3a9196de79e6096b6fe6.png

    看上去好像并没有什么差异,反而在操作大量数据时,hashmap查询会快一些呢。

    4、看看内存占用的对比:

    1、储存大量数据(五万条)的情况:

    • arraymap占用了约等于 278KB的内存空间。
    • hashmap 占用了380KB,多了36%的内存占用。

    2、那么少量数据(500条)的情况呢:

    -hashmap 储存500条数据占用了约6.3KB内容,hashmap多占用了34%的内存空间。
    -arraymap储存500条数据仅占用了约4.7KB内存。

    2、总结:也就是说在Android平台上存放数万条数据的情况下。

    -二者读写速度类似,但是ArrayMap比hashmap减少30%的内存消耗。
    -这对于经常内存空间紧张。经常OOM的Android应用来说是一个不少的内存开支。

    5、ArrayMap分析:

    1、首先是put函数


    7e5c65652c718d9fd3a310c4fdca962.png

    2、ArrayMap 的put函数

    先来看put的注释描述,其实和hashmap是一样的。
    这两百行的代码,跳过其他部分,直接看结尾重点部分,我们就能直到他的数据结构样式了。

    v2-0bde5ee3e200906c6766157829177936_720w.jpg

    3、数据储存部分

    原来他存放了两个数组。一个存放的是hash,另外一个存放的是真正的数值。并且是按照下标进行对照,并没有用键值对的形式。

    翻译成图是这样的:

    v2-d0e2a282e359f276ae00fa35ee156fc1_r.jpg

    4、ArrayMap数据储存示意

    虽然看懂了他的结构,但还是不知道为什么会节省内存啊。

    直接进入下标计算和扩容机制部分。

    下标计算:

    v2-2dfebd42c2973b6541fd5f43d75a53ed_720w.jpg

    下标计算1

    414bd02042cf650e8765dcad4f7f676.png

    下标计算2

    v2-2d2d658392a3e1ec9013d3bf77433b7a_720w.jpg

    下标计算3

    我们可以看到arraymap的数组储存是有序的,根据二分法进行定位的。

    还有扩容机制,这里是添加时的扩容代码:

    v2-489f77cdaa0e80ca89d45099c5d6e2d7_720w.jpg

    添加元素时扩容

    删除元素的扩容代码:

    2b030f3f282546f64a0c5383ca806e6.png

    删除元素的扩容代码

    看到了。在ArrayMap的元素扩容是时刻变化的。也就是说会随时根据内容动态调整整体的大小。

    这也是一种用时间换取内存空间的优化思路。

    6、总结一下

    • ArrayMap的二分法查找和实时扩容机制,实现了一个有序的HashMap.并且可以在Android平台实现内存的节省。
    • 劣势是在ArrayMap整体集合数据发生改变时,会影响到元素操作的效率。
    • 理论上来说,在大数据量的情况下,更频繁的数据条数大幅度变化下,效率会变得更低。
    • 但是在我的实现过程中,发现其速度在数万条数据的情况下,相差无几。
    • 其实一般来说,我们不会在Android移动设备的内存中储存数万条数据,这也是为什么Google在Android的源码中大量使用ArrayMap的原因。

    参考:https://zhuanlan.zhihu.com/p/40364092

    相关文章

      网友评论

          本文标题:ArrayMap分析

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