Android 为什么推荐使用 SparseArray 来替代 HashMap?

SparseArray 也许你没听过, 那正好今天就来学习一下咯, 这也是 Android 官方推荐使用的, 所以我们需要了解一下他的优势和劣势在哪些地方

首先 SparseArray 用来和 HashMap 做比较, 在安卓项目中, 你新建一个 HashMap 对象, 注意下面会有下划线, 里面有提示

翻译成白话文的意思就是建议使用 SparseArray 替代 HashMap 来获得更好的表现我们都知道 HashMap 在 java 中很常用, 并且也很吃香, 面试官经常会问到 HashMap 源码实现, 既然 HashMap 的表现都这么牛逼了, 那么为什么 Android 官方会推荐使用 SparseArray 呢? 不要急, 慢慢来~

首先来了解一下 SparseArray, 翻译过来称为稀疏数组, 所谓稀疏数组就是数组中大部分的内容值都未被使用 (或都为零), 在数组中仅有少部分的空间使用因此造成内存空间的浪费, 为了节省内存空间, 并且不影响数组中原有的内容值, 我们可以采用一种压缩的方式来表示稀疏数组的内容

下面有网上举例子的两张图, 我挪过来了, 如果涉及侵权问题, 请联系我删除哈, 毕竟自己照猫画虎重新画一个, 浪费时间, 没有必要:

可以看出来这是一个 9*7 的数组, 它所占用的空间为 63 个, 但是如图只有 5 个空间使用了, 其他的都是浪费, 浪费是可耻的, 所以按照稀疏数组的整理, 就变成了下面这张图所示

大家应该都能看懂吧, 二维数组对应的值, 那么这么一来所占空间仅仅为 3*6=18 个了, 相比起来是否节省很多, 所以这就是为什么 Android 官方推荐使用 SparseArray 的原因了, 我们稍后来验证

下面我们来写一段程序来看看 SparseArray 和 HashMap 在处理数据上面的性能情况

HashMap 正向插入数据HashMapmap=newHashMap();

longstart=System.currentTimeMillis();

for(inti=0;i<100000;i++){

map.put(i,String.valueOf(i));

}

longmemory=Runtime.getRuntime().totalMemory();

longend=System.currentTimeMillis();

longusedTime=end-start;

System.out.println("HashMap 消耗的时间是:"+usedTime+",HashMap 占用的内存是:"+memory);

输出结果:

SparseArray 正向插入数据SparseArraysparse=newSparseArray<>();

longstart=System.currentTimeMillis();

for(inti=0;i<100000;i++){

sparse.put(i,String.valueOf(i));

}

longmemory=Runtime.getRuntime().totalMemory();

longend=System.currentTimeMillis();

longusedTime=end-start;

System.out.println("SparseArray 消耗的时间是:"+usedTime+",SparseArray 占用的内存是:"+memory);

输出结果:

公平起见, 这两段代码我都是分别运行在 Android 程序中的, 一次说明不了什么结果, 所以我重复启动了几次项目, 这个时候再做对比就很明显了, 这四次结果 SpaseArray 的内存占用都是明显低于 HashMap 的内存占用的, 消耗的时间好像也是这样的, 但是 Android 官方并没有提到效率这个问题, 我们之前分析 SpaseArray 的内存结果也没有发现这个现象, 那么这是为什么呢? 不要急, 下面我们反向来插入一次数据再做一次比较

HashMap 反向插入数据HashMapmap=newHashMap();

longstart=System.currentTimeMillis();

for(inti=100000-1;i>=0;i--){

map.put(i,String.valueOf(100000-i-1));

}

longmemory=Runtime.getRuntime().totalMemory();

longend=System.currentTimeMillis();

longusedTime=end-start;

System.out.println("HashMap 消耗的时间是:"+usedTime+",HashMap 占用的内存是:"+memory);

输出结果:

SparseArray 反向插入数据SparseArraysparse=newSparseArray<>();

longstart=System.currentTimeMillis();

for(inti=100000-1;i>=0;i--){

sparse.put(i,String.valueOf(100000-i-1));

}

longmemory=Runtime.getRuntime().totalMemory();

longend=System.currentTimeMillis();

longusedTime=end-start;

System.out.println("SparseArray 消耗的时间是:"+usedTime+",SparseArray 占用的内存是:"+memory);

输出结果:

运行了三次以后我都不好意思再运行了, 可以看到倒入的情况下, 消耗时间表现非常糟糕, 并且页面这个时候处于卡顿状态, 但是仍然有一点, 那就是 SparseArray 占用的内存依然比 HashMap 优秀的多, 由于 SparseArray 每次在插入的时候都要使用二分查找判断是否有相同的值被插入. 因此这种倒序的情况是 SparseArray 效率最差的时候

源码分析

打开 SparseArray 源码, 我们先看看左边的结构视图有哪些方法:

看看开头定义的变量privatestaticfinalObjectDELETED=newObject();

privatebooleanmGarbage=false;

privateint[]mKeys;

privateObject[]mValues;

privateintmSize;

很直接的可以看到有两个数组, 并且他们的命名都那么的直接, 一个存放 key, 一个存放 value, 还有一个大小

看看构造函数publicSparseArray(){

this(10);

}

publicSparseArray(intinitialCapacity){

if(initialCapacity==0){

mKeys=EmptyArray.INT;

mValues=EmptyArray.OBJECT;

}else{

mValues=ArrayUtils.newUnpaddedObjectArray(initialCapacity);

mKeys=newint[mValues.length];

}

mSize=0;

}

默认的构造函数也会调用重载方法并给初始容量设为 10

看看插入方法 put/**

* Adds a mapping from the specified key to the specified value,

* replacing the previous mapping from the specified key if there

* was one.

*/

// 注释已经说明了如果 key 不存在, 则插入 key 和 value, 如果 key 存在, 则替换原来的 value

// 所以这个方法也可以当作修改

publicvoidput(intkey,Evalue){

// 通过二分法查找 key

inti=ContainerHelpers.binarySearch(mKeys,mSize,key);

if(i>=0){

// 如果 i>0, 说明之前已经存在了这个 key, 所以直接覆盖原来的 value

mValues[i]=value;

}else{

// 如果 i<0, 说明 key 不存在, 所以 i 肯定是负数, 所以我们要取相反数

i=~i;

// 如果 i 在 mSize 范围之内并且之前的值被删除了, 那么直接进行赋值即可

if(i

mKeys[i]=key;

mValues[i]=value;

return;

}

// 如果大小超过了 keys 的长度, 说明存在无效的数据, 这个时候需要回收了

if(mGarbage&&mSize>=mKeys.length){

gc();

// Search again because indices may have changed.

// 回收完后引用可能改变了, 所以需要对 key 重新二分法查找并取反

i=~ContainerHelpers.binarySearch(mKeys,mSize,key);

}

mKeys=GrowingArrayUtils.insert(mKeys,mSize,i,key);

mValues=GrowingArrayUtils.insert(mValues,mSize,i,value);

mSize++;

}

}

看看插入方法 append/**

* Puts a key/value pair into the array, optimizing for the case where

* the key is greater than all existing keys in the array.

*/

publicvoidappend(intkey,Evalue){

if(mSize!=0&&key<=mKeys[mSize-1]){

put(key,value);

return;

}

if(mGarbage&&mSize>=mKeys.length){

gc();

}

mKeys=GrowingArrayUtils.append(mKeys,mSize,key);

mValues=GrowingArrayUtils.append(mValues,mSize,value);

mSize++;

}

可以看出来, append 方法其实很简单, 它也是调用了 put 方法完成键值对的插入, 并且调用回收的逻辑也是一样的

看看删除的 4 种方法1.delete(intkey)

/**

* Removes the mapping from the specified key, if there was any.

*/

publicvoiddelete(intkey){

inti=ContainerHelpers.binarySearch(mKeys,mSize,key);

if(i>=0){

if(mValues[i]!=DELETED){

mValues[i]=DELETED;

mGarbage=true;

}

}

}

如果通过二分法能找到 key, 就将对应的索引对应的 value 设置为 DELETED 常量, 并且标识 mGarbage = true2.remove(intkey)

publicvoidremove(intkey){

delete(key);

}

直接调用 delete 方法3.removeAt(intindex)

publicvoidremoveAt(intindex){

if(mValues[index]!=DELETED){

mValues[index]=DELETED;

mGarbage=true;

}

}

原理和 delete 方法一样4.clear()

publicvoidclear(){

intn=mSize;

Object[]values=mValues;

for(inti=0;i

values[i]=null;

}

mSize=0;

mGarbage=false;

}

这个方法顾名思义, 将数组内容全部清空置为 null

看看修改的方法 setValueAt(int index, E value)publicvoidsetValueAt(intindex,Evalue){

if(mGarbage){

gc();

}

mValues[index]=value;

}

如果标记为垃圾的话, 先进行一次垃圾回收, 然后再将指定的值设置到对应的索引上

看看获取方法 get()get(int key, E valueIfKeyNotFound)publicEget(intkey){

returnget(key,null);

}

publicEget(intkey,E valueIfKeyNotFound){

inti=ContainerHelpers.binarySearch(mKeys,mSize,key);

if(i<0||mValues[i]==DELETED){

returnvalueIfKeyNotFound;

}else{

return(E)mValues[i];

}

}

其实最终调用的都是 get(int key, E valueIfKeyNotFound) 方法, 只不过第一个找不到 key 对应的 value 时返回的是 null, 第二个方法则可以由我们自己指定的默认值

总结

大家一定要注意, 我们插入的 key 并不是索引的角标, 不要以为是 int 型就是角标了, 那就错了, 其实和 map 一样, 都是通过 key 来查找 value, 我们传入 key 通过二分法生成一个 index, 这个 index 才是角标

注意内存二字很重要, 因为它仅仅提高内存效率, 而不是提高执行效率, 所以也决定它只适用于 android 系统 (内存对 android 项目有多重要, 地球人都知道)

最后引用别人总结的比较好的一段话来结束这篇文章:

SparseArray 有两个优点: 1. 避免了自动装箱 (auto-boxing),2. 数据结构不会依赖于外部对象映射我们知道 HashMap 采用一种所谓的 Hash 算法来决定每个元素的存储位置, 存放的都是数组元素的引用, 通过每个对象的 hash 值来映射对象而 SparseArray 则是用数组数据结构来保存映射, 然后通过折半查找来找到对象但其实一般来说, SparseArray 执行效率比 HashMap 要慢一点, 因为查找需要折半查找, 而添加删除则需要在数组中执行, 而 HashMap 都是通过外部映射但相对来说影响不大, 最主要是 SparseArray 不需要开辟内存空间来额外存储外部映射, 从而节省内存

来源: http://blog.csdn.net/woshizisezise/article/details/79361458