文档章节

Android应用性能优化之使用SparseArray替代HashMap

丁佳辉
 丁佳辉
发布于 2017/02/07 10:31
字数 1181
阅读 7
收藏 0

HashMap是java里比较常用的一个集合类,我比较习惯用来缓存一些处理后的结果。最近在做一个Android项目,在代码中定义这样一个变量,实例化时,Eclipse却给出了一个 performance 警告。

sparsearray

 

意思就是说用SparseArray <E> 来替代,以获取更好性能。老实说,对SparseArray并不熟悉,第一感觉应该是Android提供的一个类。按住Ctrl点击进入SparseArray的源码,果不其然,确定是Android提供的一个工具类。

android_util_sparsearray

 

单纯从字面上来理解,SparseArray指的是稀疏数组(Sparse array) ,所谓稀疏数组就是数组中大部分的内容值都未被使用(或都为零),在数组中仅有少部分的空间使用。因此造成内存空间的浪费,为了节省内存空间,并且不影响数组中原有的内容值,我们可以采用一种压缩的方式来表示稀疏数组的内容。

假设有一个9*7的数组,其内容如下:

sparsearray_pic1

 

在此数组中,共有63个空间,但却只使用了5个元素,造成58个元素空间的浪费。以下我们就使用稀疏数组重新来定义这个数组:

sparsearray_pic2.jpg

 

其中在稀疏数组中第一部分所记录的是原数组的列数和行数以及元素使用的个数、第二部分所记录的是原数组中元素的位置和内容。经过压缩之后,原来需要声明大小为63的数组,而使用压缩后,只需要声明大小为6*3的数组,仅需18个存储空间。

继续阅读SparseArray的源码,从构造方法我们可以看出,它和一般的List一样,可以预先设置容器大小,默认的大小是10:

 
  1. public SparseArray() {
  2. this(10);
  3. }
  4.  
  5. public SparseArray(int initialCapacity) {
  6. initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
  7.  
  8. mKeys = new int[initialCapacity];
  9. mValues = new Object[initialCapacity];
  10. mSize = 0;
  11. }

再来看看它对数据的”增删改查”。

它有两个方法可以添加键值对:

 
  1. public void put(int key, E value) {}
  2. public void append(int key, E value){}

有四个方法可以执行删除操作:

 
  1. public void delete(int key) {}
  2. public void remove(int key) {} //直接调用的delete(int key)
  3. public void removeAt(int index){}
  4. public void clear(){}

修改数据起初以为只有setValueAt(int index, E value)可以修改数据,但后来发现put(int key, E value)也可以修改数据,我们查看put(int key, E value)的源码可知,在put数据之前,会先查找要put的数据是否已经存在,如果存在就是修改,不存在就添加。

 
  1. public void put(int key, E value) {
  2. int i = binarySearch(mKeys, 0, mSize, key);
  3.  
  4. if (i > = 0) {
  5. mValues[i] = value;
  6. } else {
  7. i = ~i;
  8.  
  9. if (i < mSize &amp;&amp; mValues[i] == DELETED) {
  10. mKeys[i] = key;
  11. mValues[i] = value;
  12. return;
  13. }
  14.  
  15. if (mGarbage &amp;&amp; mSize > = mKeys.length) {
  16. gc();
  17.  
  18. // Search again because indices may have changed.
  19. i = ~binarySearch(mKeys, 0, mSize, key);
  20. }
  21. …………

所以,修改数据实际也有两种方法:

 
  1. public void put(int key, E value)
  2. public void setValueAt(int index, E value)

最后再来看看如何查找数据。有两个方法可以查询取值:

 
  1. public E get(int key)
  2. public E get(int key, E valueIfKeyNotFound)

其中get(int key)也只是调用了 get(int key,E valueIfKeyNotFound),最后一个从传参的变量名就能看出,传入的是找不到的时候返回的值.get(int key)当找不到的时候,默认返回null。

查看第几个位置的键:public int keyAt(int index)
有一点需要注意的是,查看键所在位置,由于是采用二分法查找键的位置,所以找不到时返回小于0的数值,而不是返回-1。返回的负值是表示它在找不到时所在的位置。

查看第几个位置的值:
public E valueAt(int index)
查看值所在位置,没有的话返回-1:
public int indexOfValue(E value)
最后,发现其核心就是折半查找函数(binarySearch),算法设计的很不错。

 
  1. private static int binarySearch(int[] a, int start, int len, int key) {
  2. int high = start + len, low = start - 1, guess;
  3.  
  4. while (high - low > 1) {
  5. guess = (high + low) / 2;
  6.  
  7. if (a[guess] < key)
  8. low = guess;
  9. else
  10. high = guess;
  11. }
  12.  
  13. if (high == start + len)
  14. return ~(start + len);
  15. else if (a[high] == key)
  16. return high;
  17. else
  18. return ~high;
  19. }

相应的也有SparseBooleanArray,用来取代HashMap <Integer, Boolean> ,SparseIntArray用来取代HashMap <Integer, Integer> ,大家有兴趣的可以研究。

总结:
SparseArray是android里为<Interger,Object> 这样的Hashmap而专门写的类,目的是提高效率,其核心是折半查找函数(binarySearch)。在Android中,当我们需要定义
HashMap <Integer, E> hashMap = new HashMap <Integer, E> ();
时,我们可以使用如下的方式来取得更好的性能.
SparseArray <E> sparseArray = new SparseArray <E> ();

注:

文中关于稀疏数组(Sparse array)的定义说明参照至:
http://hi.baidu.com/piaopiao_0423/item/d8cc2b99729f8380581461d1

本文转载自:https://liuzhichao.com/p/832.html

共有 人打赏支持
丁佳辉
粉丝 19
博文 412
码字总数 197400
作品 0
浦东
程序员

暂无文章

《Netkiller Java 手札》· 二进制文件操作大全

本文节选自《Netkiller Java 手札》 Netkiller Java 手札 Mr. Neo Chan, 陈景峯(BG7NYT) 中国广东省深圳市望海路半岛城邦三期 518067 +86 13113668890 <netkiller@msn.com> $Id: book.xml 6......

netkiller-
13分钟前
0
0
Fiddler Debugger post请求

常用的两种: 第一种默认的 对应URL为www 的要用请求头为:Content-Type: application/x-www-form-urlencoded 请求参数为 :param1=1234¶m2=12345 注:有些接口是指定用这种的第二方式并不...

轻量级赤影
20分钟前
1
0
如何搭建母婴亲子类知识社区

近期社交领域融资动作频繁,海尔高管、海尔医疗有限公司总裁管礼庆创办的母婴知识分享社区平台Alwayslove于上月获得700万天使轮融资。 Alwayslove是一个母婴知识分享社区平台,采用UGC模式,...

ThinkSNS账号
22分钟前
0
0
Android 自定义构建类型 BuildType

最近接触到自定义构建类型 BuildType,发现这一块有些地方稍不注意的话会被绕进去浪费点时间,既然我这边已经花费时间了,如果正好你也需要接触到 BuildType,也许接下来分享的 tips 可能会帮...

猴亮屏
23分钟前
1
0
美团点评基于 Flink 的实时数仓建设实践

引言 近些年,企业对数据服务实时化服务的需求日益增多。本文整理了常见实时数据组件的性能特点和适用场景,介绍了美团如何通过 Flink 引擎构建实时数据仓库,从而提供高效、稳健的实时数据服...

美团技术团队
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部