Android开发使用SparseArray代替HashMap[转载]

物静知声远 發表於 2019-8-6 15:06:00

Android开发使用SparseArray代替HashMap[转载]

<div>
<div>
<h3>源作者：Android小Y 链接：https://www.jianshu.com/p/1828f14d7955 来源：简书</h3>
<h1>前言</h1>
Android开发中，一个好的应用，除了要有吸引人的功能和交互之外，在性能上也应该有高的要求，如果单单实现页面和业务功能只是完成了基本任务，Android系统对内存要求也是非常高的，稍不注意，就会发生某个页面绘制突然发生卡顿甚至OOM，这对产品的用户体验都是致命性的打击，这就需要我们在日常开发中注意性能方面的优化。
<h1>正文</h1>
Android开发中经常会使用一些数据结构来存储内存中的数据，其中HashMap是以键值对的形式进行存储，使用频率也非常高，它可以根据key方便地操作集合中的数据，但是由于HashMap内部是通过Hash扩容来开拓内存空间，在内存资源及其珍贵的Android系统中就不能达到很好的效果，所以Android推出了SparseArray，它是<code>android.util</code>包下特有的类，在某些场景下，它比HashMap占用更少的内存。 

<h1>为何HashMap占用内存较大？</h1>
为何<code>SparseArray</code>会比<code>HashMap</code>更节省内存，这要从它们各自的结构说起。HashMap底层数据结构是一个 数组+链表 的组合（关于数组和链表的概念，这里就不多阐述了），它采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 <code>map.put(key,Obect)</code> 方法时，系统将调用key对象的 <code>hashCode()</code> 方法得到其 hashCode 值（每个Java对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值）。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值再hash一遍来决定该元素在数组中的存储位置。
但是这就存在一个问题，如果两个key算出来的hash值刚好相等，也就是存放的数组位置一样时，就产生了Hash冲突（因为原本数组的那个位置已经有一个元素存放着，而一个位置只能存放一组数据），那HashMap是怎么解决这种冲突的呢？ 
HashMap采用链表法来解决Hash冲突，也就是说，如果发生这种情况，HashMap会在数组中冲突的那个位置，将后加入的元素指向原来占有数组位置的那个元素，从而追加形成一个链表： 

<div class="image-package">
<div class="image-container" style="max-width: 400px; max-height: 400px">
<div class="image-view" data-width="400" data-height="400"><img style="cursor: zoom-in" src="//upload-images.jianshu.io/upload_images/16311248-802207b779698455.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/400" alt="" data-original-src="//upload-images.jianshu.io/upload_images/16311248-802207b779698455.png" data-original-width="400" data-original-height="400" data-original-format="image/png" data-original-filesize="12381"></div>

</div>
<div class="image-caption">HashMap</div>

</div>

 
HashMap中初始的存储大小就是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有不论什么元素。也要分别一块内存空间给它，并且，我们再不断的向HashMap里put数据时，当达到一定的容量限制时，HashMap的空间将会扩大为原来的2倍，所以HashMap是比较占内存的。
<h1>为何SparseArray更为优化？</h1>
先了解一个基本概念——什么是自动装箱？ 
自动装箱就是指自动将基本数据类型转换为包装器类型，比如下面这句代码：
<pre class="hljs undefined"><code>Integer i = 99;
</code></pre>
99是基本数据类型，将它直接赋值给Integer类型对象i时，就会自动将我们的基本类型int包装成Integer。装箱操作会创建对象，频繁的装箱操作会消耗许多内存，影响性能。
<hr>
而SparseArray又称为稀疏数组，与HashMap不同，其内部是直接通过维护两个数组来实现存储：
<div class="cnblogs_code">
<pre>public class SparseArray<E> implements Cloneable {

private int[] mKeys;
private Object[] mValues;
...
}</pre>
</div>
可以看到，一组存储键，一组存储值，key数组的类型是int型，也就是说，SparseArray只支持key为int类型的数据存储，关键就在这里，由于它是直接维护了一个int数组，那么key就避免了自动装箱的过程，举个例子，比如我们用HashMap存储下面这组数据：
<div class="cnblogs_code">
<pre>HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "test");
hashMap.put(2, "test");
hashMap.put(3, "test");</pre>
</div>
每次put进去的时候，由于传进去的是1，2，3，都是int基本类型，HashMap会自动帮我们包装成Integer类型的对象（也就是刚说的自动装箱），那么就肯定会消耗更多内存。但如果是SparseArray来存储的话，就直接将key存储在key数组了，省去了装箱这个过程，从而节省了内存开销。
另一方面，对SparseArray增删查改操作时，其内部会不断检查回收无用空间，从而压缩占用的内存大小，我们看下它的<code>put</code>方法：
<div class="cnblogs_code">
<pre>public void put(int key, E value) {
 //先调用二分法查询该key在数组中的位置
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

 if (i >= 0) {
 //大于0说明已经存在数组中，可以直接赋值
 mValues = value;
 } else {
 //小于0说明这是一个新的键值对，且它应该插在数组中的第i个位置
 i = ~i;
 //根据DELETED来查询当前位置的值是否已经被删除
 if (i < mSize && mValues == DELETED) {
 mKeys = key;
 mValues = value;
 return;
 }
 //如果当前容量已满
 if (mGarbage && mSize >= mKeys.length) {
 //回收无效空间
 gc();

 // Search again because indices may have changed.
 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
 }

 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
 mSize++;
 }
}</pre>
</div>
可以看到，<code>SparseArray</code>会先调用二分法去查询key应该存放在数组中的位置，所以<code>SparseArray</code>的key数组一定是有序排列的，然后会用一个<code>DELETED</code>来作为当前位置的元素是否已经被删除，<code>DELETED</code>会在调用<code>remove</code>移除元素的时候赋给对应位置Value，如下：
<div class="cnblogs_code">
<pre>public void remove(int key) {
delete(key);
}

public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

if (i >= 0) {
 if (mValues != DELETED) {
 mValues = DELETED;
 mGarbage = true;
 }
}
}</pre>
</div>
<code>SparseArray</code>通过这个来作为它压缩空间的一个标志（即该位置可不可以被回收），这样子也进一步节省了空间。
从刚才可以看出，无论是SparseArray的<code>put</code>还是<code>delete</code>（其实其他操作比如<code>get</code>也都是通过二分法寻找下标），都是通过二分法去查询这个key应该被存放的位置。而HashMap在插入的时候，不需要去遍历整个集合，而是直接通过hash计算出位置插入。所以在插入效率上，SparseArray会比HashMap稍慢一些，但在数据量不大的情况下，两者的差别不大。
<h1>结语</h1>
<code>SparseArray</code>与<code>HashMap</code>相比，最大的优势在于内存方面，无论数据量级大小如何，<code>SparseArray</code>所占用的内存都会比HashMap小，在Android中内存是极为重要的，所以在需要保存<Integer,Object>键值对的场景中，推荐使用<code>SparseArray</code>替换<code>HashMap</code>。换句话说，<code>SparseArray</code>是Android中为<Integer,Object>这样的HashMap专门写的类，它避开了自动装箱并且压缩稀疏数组，目的就是为了节省内存。 
另外，Android还提供了其他几种类似的集合类：<code>SparseIntArray</code>、<code>SparseBooleanArray</code>、<code>SparseLongArray</code>，可以支持存储<Integer,Integer>、<Integer,Boolean>、<Integer,Long>的数据类型，也就是同时让Value也避开了装箱过程，进一步优化。

</div>

 </div>

</div>
<div id="MySignature" role="contentinfo">
<div style="text-align: center">
本文来自博客园，作者：观心静，转载请注明原文链接：https://www.cnblogs.com/guanxinjing/p/11309032.html 
<div style="color:orange;font-size:16px;">本文版权归作者和博客园共有，欢迎转载，但必须给出原文链接，并保留此段声明，否则保留追究法律责任的权利。 </div>
</div> 
来源：https://www.cnblogs.com/guanxinjing/p/11309032.html

頁: [1]

琼殿技术论坛's Archiver

Android开发 使用SparseArray代替HashMap[转载]

Android开发使用SparseArray代替HashMap[转载]