Android容器类小结

栏目: Android · 发布时间: 5年前

内容简介:相较于其他设备,移动设备有自己的特点,内存小是一个很突出的问题,Google针对android设备的这一特点,开发了一套容器框架,目的就是为了更加高效地利用内存。接下来就对这些容器进行一下总结。以上是android中容器的实现继承结构,简单梳理一下:从**

相较于其他设备,移动设备有自己的特点,内存小是一个很突出的问题,Google针对android设备的这一特点,开发了一套容器框架,目的就是为了更加高效地利用内存。接下来就对这些容器进行一下总结。

组织结构

Android容器类小结

以上是android中容器的实现继承结构,简单梳理一下:

  • ArraySet 实现了 SetCollections 接口,在api 23中添加
  • ArrayMap 实现了 Map 接口,在api 19中添加
  • SparseArraySparseIntArraySparseBooleanArray 实现了 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 和剩余的容器。通过前面的分析可以知道, ArraySetArrayMap 使用的相同的优化方式, SparseArray 在进行优化的时候使用 gc 垃圾回收策略,故从优化方法上进行分类的话可以分一下三类:

  • ArraySet , ArrayMap 使用数组 mKeys 存储 key 的hash值,hash值在 mKeys 的位置为 index ,并将value存储到 mValues 数组对应下标的位置( ArrayMapkeyvalue 分别在 mValuesindex * 2index * 2 + 1 的位置)。查找或者修改元素时,使用二分查找在 mKeys 中找到元素在 mValues 的下标,然后进行修改或者返回。
  • SparseArray 使用 int 类型的 mKeys 数组存储 int 类型的键,下标为 index ,将 Object 类型的 value 存储在在 Object 类型的数组 mValuesindex 位置,在查找和修改时,使用二分查找在 mKeys 中找到元素在 mValues 的下标,然后进行修改或者返回。在删除 value 时, SparseArray 并不直接进行数组元素的移动,而是将待删除的 value 标记为 DELETED 状态,在 gc 的过程中将所有非 DELETED 状态的元素移动到数组的最前面,从而减少二分查找的时间。
  • SparseIntArray , SparseLongArray , SparseBooleanArray 这3个容器可以理解成专用容器,使用 int 类型数组和对应类型的数组;使用二分查找快速查找元素,然后进行删除,修改,添加操作。

优化共同点与差异

虽然这些容器存储的元素类型不同,但是通过分析可以发现他们在内存优化中的共同点,接下来就分析下这些容器在优化上存在的共同点和差异。

共同点

  • 数据结构

    Android容器类小结
    这里的数据结构是指容器的底层存储结构,虽然在 ArrayMap 中mValues的长度是mKeys的2倍,但也仅仅是数组长度上的差异,底层存储使用的思想仍然是一样的; int 类型的数组 mKeys 里的元素时按照升序进行排列的。相较于 HashMap 使用 Node 结构存储,这样的存储方式使用更小的存储空间存储 k-v

    ,同时避免了原始数据类型的自动装箱。

  • 查找方法 在组织结构中列出的容器,他们在进行元素查找时,都会先在 mKeys 数组中利用二分查找找到元素的下标 index ,然后使用 indexmValues 数组中对 value 进行操作。

  • 获取带插入下标 在进行元素插入时,会首先使用二分查找在 mKeys 数组中查找元素的下标,如果元素不存在,则二分查找会返回元素待插入位置的取反。

不同点

  • key 的处理 ArraySet , ArrayMap 底层实现时,会计算待插入元素的hash值,根据hash值,在 mKeys 找到待插入位置; SparseArraySparseXXXArray 存储的时候直接使用 key 值,不会进行hash计算。
  • null 的处理 ArraySetArrayMap 允许插入 keynull 的元素, key 的hash值为0; SparseArraySparseXXXArray 存储的时由于直接使用int类型的数据作为 key ,故不存在 keynull 的情况。
  • 缓存 为了避免频繁的内存回收, ArraySetArrayMap 添加了缓存结构, SparseArraySparseXXXArray 没有缓存
  • 扩容规则 ArraySetArrayMap 在进行扩容的时,容量的变化规则为 4, 8 , size * 2 / 3SparseArraySparseXXXArray 使用 ArrayUtils.newUnpaddedArray 建立新的数据,将原来的数据拷贝到新数组中。

使用建议

虽然这些容器在Android设备上可以更高效地利用内存,但是还是存在使用使用限制。

ArrayMap
HashMap

总结

前面说了很多,其实android容器优化的根本思想就是使用 int 到其他类型的映射,使用数组保存着两个映射,用以优化 HashMapk-v 的存储。这种优化适用于元素数量较少(少于1000)的情况。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web Anatomy

Web Anatomy

Robert Hoekman Jr.、Jared Spool / New Riders / 2009-12-11 / USD 39.99

At the start of every web design project, the ongoing struggles reappear. We want to design highly usable and self-evident applications, but we also want to devise innovative, compelling, and exciting......一起来看看 《Web Anatomy》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具