专栏首页技术小黑屋深入剖析 Android中的 ArrayMap

深入剖析 Android中的 ArrayMap

数据集合在任何一门编程语言中都是很重要的一部分,在 Android 开发中,我们会实用到ArrayList, LinkedList, HashMap等。其中HashMap是用来处理键值对需求的常用集合。 而Android中引入了一个新的集合,叫做ArrayMap,为键值对存储需求增加了一种选择。

ArrayMap是什么

  • 一个通用的key-value映射数据结构
  • 相比HashMap会占用更少的内存空间
  • android.util和android.support.v4.util都包含对应的ArrayMap类

ArrayMap的内部结构

如上图所示,在ArrayMap内部有两个比较重要的数组,一个是mHashes,另一个是mArray。

  • mHashes用来存放key的hashcode值
  • mArray用来存储key与value的值,它是一个Object数组。

其中这两个数组的索引对应关系是

1 2 3

mHashes[index] = hash; mArray[index<<1] = key; //等同于 mArray[index * 2] = key; mArray[(index<<1)+1] = value; //等同于 mArray[index * 2 + 1] = value;

注:向左移一位的效率要比 乘以2倍 高一些。

查找数据

查找数据是容器常用的操作,在Map中,通常是根据key找到对应的value的值。

ArrayMap中的查找分为如下两步

  • 根据key的hashcode找到在mHashes数组中的索引值
  • 根据上一步的索引值去查找key所对应的value值

其中占据时间复杂度最多的属于第一步:确定key的hashCode在mHahses中的索引值。

而这一步对mHashes查找使用的是二分查找,即Binary Search。所以ArrayMap的查询时间复杂度为 ‎O(log n)

确定key的hashcode在mHashes中的索引的代码的逻辑

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

int indexOf(Object key, int hash) { final int N = mSize; //快速判断是ArrayMap是否为空,如果符合情况快速跳出 if (N == 0) { return ~0; } //二分查找确定索引值 int index = ContainerHelpers.binarySearch(mHashes, N, hash); // 如果未找到,返回一个index值,可能为后续可能的插入数据使用。 if (index < 0) { return index; } // 如果确定不仅hashcode相同,也是同一个key,返回找到的索引值。 if (key.equals(mArray[index<<1])) { return index; } // 如果key的hashcode相同,但不是同一对象,从索引之后再次找 int end; for (end = index + 1; end < N && mHashes[end] == hash; end++) { if (key.equals(mArray[end << 1])) return end; } // 如果key的hashcode相同,但不是同一对象,从索引之前再次找 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { if (key.equals(mArray[i << 1])) return i; } //返回负值,既可以用来表示无法找到匹配的key,也可以用来为后续的插入数据所用。 // Key not found -- return negative value indicating where a // new entry for this key should go. We use the end of the // hash chain to reduce the number of array entries that will // need to be copied when inserting. return ~end; }

既然对mHashes进行二分查找,则mHashes必须为有序数组。

插入数据

ArrayMap提供给我们进行插入数据的API有

  • append(key,value)
  • put(key,value)
  • putAll(collection)

以put方法为例,需要注意的有

  • 新数据位置确定
  • key为null
  • 数组扩容问题

新数据位置确定

为了确保mHashes能够进行二分查找,我们需要保证mHashes始终未有序数组。

在确定新数据位置过程中

  • 根据key的hashcode在mHashes表中二分查找确定合适的位置。
  • 如果新添加的数据的索引不是最后位置,在需要对这个索引之后的全部数据向后移动

key为null时

当key为null时,其实和其他正常的key差不多,只是对应的hashcode会默认成0来处理。

1 2 3 4 5 6 7 8 9

public V put(K key, V value) { final int hash; int index; if (key == null) { hash = 0;//如果key为null,其hashcode算作0 index = indexOfNull(); } ... }

数组扩容问题

  • 首先数组的容量会扩充到BASE_SIZE
  • 如果BASE_SIZE无法容纳,则扩大到2 * BASE_SIZE
  • 如果2 * BASE_SIZE仍然无法容纳,则每次扩容为当前容量的1.5倍。

具体的计算容量的代码为

1 2 3 4 5 6 7

/** * The minimum amount by which the capacity of a ArrayMap will increase. * This is tuned to be relatively space-efficient. */ private static final int BASE_SIZE = 4; final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

删除数据

删除ArrayMap中的一项数据,可以分为如下的情况

  • 如果当前ArrayMap只有一项数据,则删除操作将mHashes,mArray置为空数组,mSize置为0.
  • 如果当前ArrayMap容量过大(大于BASE_SIZE*2)并且持有的数据量过小(不足1/3)则降低ArrayMap容量,减少内存占用
  • 如果不符合上面的情况,则从mHashes删除对应的值,将mArray中对应的索引置为null

ArrayMap的缓存优化

ArrayMap的容量发生变化,正如前面介绍的,有这两种情况

  • put方法增加数据,扩大容量
  • remove方法删除数据,减小容量

在这个过程中,会频繁出现多个容量为BASE_SIZE和2 * BASE_SIZE的int数组和Object数组。ArrayMap设计者为了避免创建不必要的对象,减少GC的压力。采用了类似对象池的优化设计。

这其中设计到几个元素

  • BASE_SIZE 值为4,与ArrayMap容量有密切关系。
  • mBaseCache 用来缓存容量为BASE_SIZE的int数组和Object数组
  • mBaseCacheSize mBaseCache缓存的数量,避免无限缓存
  • mTwiceBaseCache 用来缓存容量为 BASE_SIZE * 2的int数组和Object数组
  • mTwiceBaseCacheSize mTwiceBaseCache缓存的数量,避免无限缓存
  • CACHE_SIZE 值为10,用来控制mBaseCache与mTwiceBaseCache缓存的大小

这其中

  • mBaseCache的第一个元素保存下一个mBaseCache,第二个元素保存mHashes数组
  • mTwiceBaseCache和mBaseCache一样,只是对应的数组容量不同

具体的缓存数组逻辑的代码为

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

private static void freeArrays(final int[] hashes, final Object[] array, final int size) { if (hashes.length == (BASE_SIZE*2)) { synchronized (ArrayMap.class) { if (mTwiceBaseCacheSize < CACHE_SIZE) { array[0] = mTwiceBaseCache; array[1] = hashes; for (int i=(size<<1)-1; i>=2; i--) { array[i] = null; } mTwiceBaseCache = array; mTwiceBaseCacheSize++; if (DEBUG) Log.d(TAG, "Storing 2x cache " + array + " now have " + mTwiceBaseCacheSize + " entries"); } } } else if (hashes.length == BASE_SIZE) { synchronized (ArrayMap.class) { if (mBaseCacheSize < CACHE_SIZE) { array[0] = mBaseCache; array[1] = hashes; for (int i=(size<<1)-1; i>=2; i--) { array[i] = null; } mBaseCache = array; mBaseCacheSize++; if (DEBUG) Log.d(TAG, "Storing 1x cache " + array + " now have " + mBaseCacheSize + " entries"); } } } }

具体的利用缓存数组的代码为

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

private void allocArrays(final int size) { if (mHashes == EMPTY_IMMUTABLE_INTS) { throw new UnsupportedOperationException("ArrayMap is immutable"); } if (size == (BASE_SIZE*2)) { synchronized (ArrayMap.class) { if (mTwiceBaseCache != null) { final Object[] array = mTwiceBaseCache; mArray = array; mTwiceBaseCache = (Object[])array[0]; mHashes = (int[])array[1]; array[0] = array[1] = null; mTwiceBaseCacheSize--; if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes + " now have " + mTwiceBaseCacheSize + " entries"); return; } } } else if (size == BASE_SIZE) { synchronized (ArrayMap.class) { if (mBaseCache != null) { final Object[] array = mBaseCache; mArray = array; mBaseCache = (Object[])array[0]; mHashes = (int[])array[1]; array[0] = array[1] = null; mBaseCacheSize--; if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes + " now have " + mBaseCacheSize + " entries"); return; } } } mHashes = new int[size]; mArray = new Object[size<<1]; }

在Android中的应用

在Android Performance Pattern中,官方给出的使用场景为

1.item数量小于1000,尤其是插入数据和删除数据不频繁的情况。

2.Map中包含子Map对象

通过本文的介绍,我们对于ArrayMap应该有了一个比较深入的了解。虽然ArrayMap是Android系统中HashMap的一种替代,但是我们在使用时也要注意选择适宜的场景,切莫一概而论。

嗨,我是小广告:欢迎参加我的知乎Live 《我学安卓的那些套路》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ArrayMap数据结构分析

    ArrayMap是Android上特有的一个性能比较高的Map,和HashMap一样,也实现了Map接口。

    用户1108631
  • Java性能调优之容器扩容问题

    在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

    技术小黑屋
  • 深度解读ArrayMap优势与缺陷

    在移动设备端内存资源很珍贵,HashMap为实现快速查询带来了很大内存浪费。为此,2013年5月20日Google工程师Dianne Hackborn在Andr...

    程序亦非猿
  • Android开发之那些好用的数据结构与API

    由于Android Application 主要是Java语言开发的,所以在写程序的时候,很多朋友们都会用到Java里面常用的数据结构,但是Android中提供...

    YungFan
  • Android - 看似内存泄漏,实则不是,记一次内存泄漏的案例分析

      APP中常常会存在内存泄漏的问题,一个简单的测试方法是,多次进入和退出同一页面(Activity),使用adb shell中的dumpsys memi...

    宋凯伦
  • 深入理解Activity启动流程和AMS框架(一)

    Android应用程序的载体是APK文件,它是一个组件和资源的容器。APK文件和我们常见可执行文件的区别是:每个可执行文件在一个单独的进程中,但是APK文件可能...

    open
  • APK安装流程详解6——PackageManagerService启动前奏

    由于在后面讲解PackageManager流程启动的时候会 涉及到Setting类,我们就先预热下 Settings.java源码地址

    隔壁老李头
  • React-Native 安卓预加载优化方案

    React-Native安卓预加载优化方案本文针对使用React Native开发混合应用的过程中安卓端白屏时间较长的问题,提出了react-native安卓端...

    腾讯IVWEB团队
  • 腾讯Android研发岗必刷真题:说下组件之间的跳转和组件通信原理机制

    今天则会从更小细粒度入手,主要讲讲在组件化架构下组件与组件之间通信机制是如何、包括所谓的UI跳转,其实也是组件化通信,只不过它稍微特殊点,单独抽取出来而已。学习...

    Android技术干货分享
  • Android大厂面试经验分享(OPPO,字节,华为,阿里)

    我是从小公司跳出来的,最终入职OPPO,说实话这段时间的经历让我深深地感受到,我们为跳槽做的一些临时抱佛脚的提升跟那些大佬的沉淀比起来太渺小了。我们都知道找资料...

    没关系再继续努力
  • 让源码告诉你:Android 不要滥用 SharedPreferences(上)

    链接:https://www.jianshu.com/p/5fcef7f68341

    陈宇明
  • WebViewJavaScriptBridge深入剖析

    前一篇文章中,我们大致的讲述了一下JavaScriptCore这个库在iOS开发中的应用。在文中最后的阶段,我们提到了WebViewJavaScriptBrid...

    iOSSir
  • 深入剖析ThreadLocal

    朋友们在遇到线程安全问题的时候,大多数情况下可能会使用synchronized关键字,每次只允许一个线程进入锁定的方法或代码块,这样就可以保证操作...

    苏三说技术
  • 深入剖析 WebKit

    1990年 Berners-Lee 发明了 WorldWideWeb 浏览器,后改名 Nexus,在1991年公布了源码。

    用户7451029
  • 深入剖析 JavaScriptCore

    最近开始涉及 JS 的解析和处理工作,所以专门研究了下这块。特别是动态类型的处理以及不同引擎对于平台无关的字节码的设计和处理会有很大的帮助。

    用户7451029
  • 深入剖析:认识Oracle 中的 NULL 值

    杨廷琨,网名 yangtingkun 云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家 经常看到很多人提出和NULL有关的问题。N...

    数据和云
  • 深入剖析Android中最简单的数据存储方式:SharedPreferences

    今天来和大家分享一篇有关Android中数据存储的文章,它可以说是Android对数据的所有存储方式中最简单的一种存储了,它就是SharedPreference...

    灰小猿
  • Android中传值Intent与Bundle的区别小结

    Bundle 翻译成中文的意思是“捆绑”,常用在Activity间传递参数,之前一开始并不太待见,原因是Intent本身就可以传递,Intent.putExtr...

    砸漏
  • HashMap、LRU、散列表

    获取对象的hashcode以后,先进行移位运算,然后再和自己做异或运算,即:hashcode ^ (hashcode >>> 16),这一步甚是巧妙,是将高16...

    六月的雨

扫码关注云+社区

领取腾讯云代金券