为什么要用SparseArray来替换HashMap？

博文背景：

在Android 中使用HashMap 的时候看到过提示。

HashMap<Integer,Object> mp = new HashMap<Integer,Object>(); 

提示：Use new SparseArray<Object>(...) instead for better performance意思是，使用 SparseArray 将获得更好的性能
（注：这个提示我再eclipse 中见过，而在studio 中并没有看到过这种提示）

查阅网上资料关于SparseArray文档介绍，分析如下（ps:借鉴网上大佬的翻译）：

SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn’t rely on an extra entry object for each mapping.

（译文+个人理解）
SparseArrays不同于普通的对象数组。there can be gaps in the indices.（指针中能够存在空白？注：这句我不太理解，不知道怎样翻译，是说SparseArrays 是不连续存储？）。它的目的是比使用从整数映射对象的HashMap(简单来说就是 HashMap<Integer,Object>)有更有效的使用内存。

同一时候也避免auto-boxing（自己主动装箱）（注：auto-boxing（自己主动装箱）：将原始类型封装为对象类型。比方把int类型封装成Integer类型。）和数据结构对每条映射不依赖额外的Entry 对象（注：这里是和HashMap做的对照。在HashMap有须要引入Entry<K,V>,而SparseArrays比較简单，里面是两个一维数组 int[] mKeys; 和 Object[] mValues）

Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

注意，这个容器在数组数据结构中维持一个映射关系。使用二分查找法来找到key.它的目标不是为了适应数据结构中包括大量数据的情况。

通常情况下要比传统的HashMap慢，由于查找是用二分查找法搜索，加入和删除须要对数组进行加入和删除。

对于有几百条的数据的容器。性能差异不大，不超过50%（注：这里我理解的是， SparseArrays 的优势更体如今小数量上）

To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-used for the same key, or compacted later in a single garbage collection step of all removed entries. This garbage collection will need to be performed at any time the array needs to be grown or the the map size or entry values are retrieved.

为了提高性能，该容器提供了一个优化：当删除key键时。不是立刻删除这一项，而是留下须要删除的选项给一个删除的标记。

该条目能够被又一次用于同样的key,或者被单个垃圾收集器逐步删除完所有的条目后压缩。在不论什么时候。当数组须要增长（注：这里我理解为 put、append之类的操作）或者Map 的长度、entry的value须要被检索的时候，该垃圾收集器就会运行（注：这里能够从代码中发现。google在相应的方法中调用 gc() 方法）。

It is possible to iterate over the items in this container using

• {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
• keyAt(int) with ascending values of the index will return the
• keys in ascending order, or the values corresponding to the keys in ascending
• order in the case of valueAt(int).

在此使用此容器时，能够迭代遍历当中的item.. keyAt(int) 返回升序下的key .
valueAt(int) 返回升序状态下。key 相应的value值。

与HashMap比较优点？

key，value 类型的比較

HashMap | key：随意类型 | value：随意类型
SparseArray | key：Integer | value：随意类型
SparseBooleanArray | key：Integer | value：Boolean类型。
SparseIntArray | key：Integer | value：Integer类型。
LongSparseArray | key：Long | value：随意类型

依据需求的不同，找到合适的方法才是上上策。

内部存储的比較

SparseArray |: int[] mkeys和 Object[] mvalues 来存储key和value
HashMap | : 内部存储必须使用Entry<k,v>

其他分析

• 创建数据

以10000条数据为例。HashMap用去约13.2M内存，SparseArray共用去 8.626M内存。

• 数据插入

在正序插入数据时候，SparseArray比HashMap要快一些；HashMap无论是倒序还是正序开销差点儿是一样的。可是SparseArray的倒序插入要比正序插入要慢很多，为什么呢？
原因：SparseArray在检索数据的时候使用的是二分查找，所以每次插入新数据的时候SparseArray都须要又一次排序，所以逆序是最差情况。

• 数据检索

SparseArray中存在须要检索的下标时。SparseArray的性能略胜一筹可是当检索的下标比較离散时，SparseArray须要使用多次二分检索，性能显然比hash检索方式要慢一些了。

• 接口实现

  HashMap实现了Cloneable, Serializable SparseArray 实现了Cloneable 接口,也就是说SparseArray 是不支持序列化的。

• 运行速度上比较，见大神分析：（传送门）

源码就不粘贴了，分析部分代码：

<pre><code>
/**

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

• replacing the previous mapping from the specified key if there

• was one.
  通过指定的key和value加入一个键值对,假设这个位置已经存在一个了，则替换掉
  */
  public void put(int key, E value) {
  int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

  if (i >= 0) {
  mValues[i] = value;
  } else {
  i = ~i;

   if (i < mSize && mValues[i] == DELETED) {
       mKeys[i] = key;
       mValues[i] = 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++;
  

  }
  }

/**

• Puts a key/value pair into the array, optimizing for the case where
• the key is greater than all existing keys in the array.
  通过指定的key和value加入一个键值对,在原有的基础上添加
  */
  public void append(int key, E value) {
  if (mSize != 0 && key <= mKeys[mSize - 1]) {
  put(key, value);
  return;
  }
  </code></pre>

仅用于记录备忘分享，如有版权问题烦请私信！谢谢