系列文章地址:
Android容器类-ArraySet原理解析(一)
Android容器类-ArrayMap原理解析(二)
Android容器类-SparseArray原理解析(三)
Android容器类-SparseIntArray原理解析(四)
相较于其他设备,移动设备有自己的特点,内存小是一个很突出的问题,Google针对android设备的这一特点,开发了一套容器框架,目的就是为了更加高效地利用内存。接下来就对这些容器进行一下总结。
组织结构
以上是android中容器的实现继承结构,简单梳理一下:
ArraySet
实现了Set
和Collections
接口,在api 23中添加ArrayMap
实现了Map
接口,在api 19中添加SparseArray
,SparseIntArray
,SparseBooleanArray
实现了Cloneable
接口,在api 1中添加SparseLong
实现了Cloneable
接口,在api 18中添加
分类
从**功能
**上划分,可以将以上容器划分为两类:
-
存储元素
ArraySet
优化了HashSet
对元素的存储 -
存储键值对 相较于
HashMap
,具体的优化方向如下:
ArrayMap
优化了HashMap
存储Object --> Object
的键值存储;
SparseArray
优化了int --> Object
的键值存储;
SparseIntArray
优化了int --> int
的键值存储;
SparseBooleanArray
优化了int --> boolean
的键值存储;
SparseLongArray
优化了int --> long
的键值存储。
优化方法
从组织结构可以看出,可以将这些容器分为3类:ArraySet
,ArrayMap
和剩余的容器。通过前面的分析可以知道,ArraySet
和ArrayMap
使用的相同的优化方式,SparseArray
在进行优化的时候使用gc
垃圾回收策略,故从优化方法上进行分类的话可以分一下三类:
ArraySet
,ArrayMap
使用数组mKeys
存储key
的hash值,hash值在mKeys
的位置为index
,并将value存储到mValues
数组对应下标的位置(ArrayMap
中key
和value
分别在mValues
的index * 2
和index * 2 + 1
的位置)。查找或者修改元素时,使用二分查找在mKeys
中找到元素在mValues
的下标,然后进行修改或者返回。SparseArray
使用int
类型的mKeys
数组存储int
类型的键,下标为index
,将Object
类型的value
存储在在Object
类型的数组mValues
的index
位置,在查找和修改时,使用二分查找在mKeys
中找到元素在mValues
的下标,然后进行修改或者返回。在删除value
时,SparseArray
并不直接进行数组元素的移动,而是将待删除的value
标记为DELETED
状态,在gc
的过程中将所有非DELETED
状态的元素移动到数组的最前面,从而减少二分查找的时间。SparseIntArray
,SparseLongArray
,SparseBooleanArray
这3个容器可以理解成专用容器,使用int
类型数组和对应类型的数组;使用二分查找快速查找元素,然后进行删除,修改,添加操作。
优化共同点与差异
虽然这些容器存储的元素类型不同,但是通过分析可以发现他们在内存优化中的共同点,接下来就分析下这些容器在优化上存在的共同点和差异。
共同点
-
数据结构
这里的数据结构是指容器的底层存储结构,虽然在
ArrayMap
中mValues的长度是mKeys的2倍,但也仅仅是数组长度上的差异,底层存储使用的思想仍然是一样的;int
类型的数组mKeys
里的元素时按照升序进行排列的。相较于HashMap
使用Node
结构存储,这样的存储方式使用更小的存储空间存储k-v
,同时避免了原始数据类型的自动装箱。 -
查找方法 在组织结构中列出的容器,他们在进行元素查找时,都会先在
mKeys
数组中利用二分查找找到元素的下标index
,然后使用index
到mValues
数组中对value
进行操作。 -
获取带插入下标 在进行元素插入时,会首先使用二分查找在
mKeys
数组中查找元素的下标,如果元素不存在,则二分查找会返回元素待插入位置的取反。
不同点
- 对
key
的处理ArraySet
,ArrayMap
底层实现时,会计算待插入元素的hash值,根据hash值,在mKeys
找到待插入位置;SparseArray
和SparseXXXArray
存储的时候直接使用key
值,不会进行hash计算。 - 对
null
的处理ArraySet
和ArrayMap
允许插入key
为null
的元素,key
的hash值为0;SparseArray
和SparseXXXArray
存储的时由于直接使用int类型的数据作为key
,故不存在key
为null
的情况。 - 缓存 为了避免频繁的内存回收,
ArraySet
和ArrayMap
添加了缓存结构,SparseArray
和SparseXXXArray
没有缓存 - 扩容规则
ArraySet
和ArrayMap
在进行扩容的时,容量的变化规则为4, 8 , size * 2 / 3
,SparseArray
和SparseXXXArray
使用ArrayUtils.newUnpaddedArray
建立新的数据,将原来的数据拷贝到新数组中。
使用建议
虽然这些容器在Android设备上可以更高效地利用内存,但是还是存在使用使用限制。
- 兼容性 在组织结构中,可以看到,并不是所有的容器都是从api 1就开始提供的,在使用具体的容器时,需要考虑应用的兼容。
- 对性能的影响 虽然
ArrayMap
在删除时不直接使用移动元素的方式删除元素,但是在获取数组元素等操作中还是 - 对数量的限制 在对元素进行查找时会使用二分查找,元素数量较大(超过1000)时,查找效率会降低,相较于
HashMap
只要数量不超过1000,效率最多不会下降50%。
总结
前面说了很多,其实android容器优化的根本思想就是使用int
到其他类型的映射,使用数组保存着两个映射,用以优化HashMap
对k-v
的存储。这种优化适用于元素数量较少(少于1000)的情况。
关注微信公众号,最新技术干货实时推送
今天的文章Android容器类小结分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/13655.html