2019-08-27：为什么推荐用SparseArray代替HashMap？

[Moosphan]

[DaveBoy]

sparseArray使用的是双数组实现，寻址采用二分法，比hashmap链表上挨着查找快。
然后hashmap的好像会自动装箱，spare不会

[wangfengye]

• int作为键,减少自动装箱操作;
• value使用纯粹的数组,结构相比hashmap简单,
• 二分查找,小数据量下更高效
• 延时回收,remove只是修改值引用,不删数据,不会时不会频繁压缩数组,在gc()函数后真正删除

[wangfengye]

类似的结构有ArrayMap,ArraySet等. 都是相似的优化, ArraySet还对长度为4,8内部数组,做了全局缓存,减少频繁创建的性能开销

[chsmy]

并不能替换所有的HashMap。只能替换以int类型为key的HashMap。

HashMap中如果以int为key，会强制使用Integer这个包装类型，当我们使用int类型作为key的时候系统会自用装箱成为Integer，这个过程会创建对象一想效率。SparseArray内部是一个int数组和一个object数组。可以直接使用int减少了自动装箱操作。

[gabyallen]

因为sparseArray避免了对key的自动装箱（int转成integer），它的内部是采用2个数组来实现的；一个存储key 一个存储value；相对来说，性能更快，内部采用压缩方式节省内存空间；
sparseArray代替HashMap的时候最好存储的数量在千量级以下。
key必须是int类型，才可以替代hashmap

[xinyu618]

首先并不能说完全用SparseArray替代。在key是int并且数据量小于1000的情况下，用SparseArray替代确实在空间上性能要好，但是在时间上只能接近HashMap而已。
SparseArray的key固定是int所以减少了装箱和拆箱的操作
SpareArray内部是运用两个数组进行维护一个是keys存储key的，一个是values存储value的。由于key是int所以没有hash碰撞，在查找位置时用二分查找的方式，时间上比较有优势。
存储方法由于SparseArray存储的结构比HashMap简单，不需要维护链表等。所以存储上比HashMap好

[Alex-Cin]

1.. 并不慢;
2.. 省内存;

在数据量较小的安卓平台下, 安卓的集合框架, 更节省内存, 时间复杂度是log2n, 性能表现不俗;
如果是数据量较大, 例如超过1K, 还是用HashMap做, 更加合理一些;

hashMap, 图看不见, 点击去就好了
正如上面图示, hash 数组很有可能出现, 数组元素并未存满, 形成稀疏数组, 导致浪费内存;
所以 ArrayMap 更节省内存;

好多人回答, 为什么 ArrayMap 更节省内存, 总是回答, 扩容时候的系数, arraMap 存的是对象本身, HashMap 存的是 Node 包装类, 这个很多人, 就包括我. 后来我找答案了, 后续的面试中, 都会回答面试官想要我讲的, 稀疏数组的概念; 其实再做分析的时候, 很多人都看到了, 只是没往这方便想而已的.

[layiw]

数据结构方面：hashmap用的是链表。sparsearray用的是双数组。
性能方面：hashmap是默认16个长度，会自动装箱。如果key是int 的话，hashmap要先封装成Interger。sparseArray的话就就会直接转成int。所以spaseArray用的限制是key是int。数据量小于1k。如果key不是int小于1000的话。可以用Arraymap。

[feelschaotic]

SparseArray三大特点

双数组、删除O(1)、二分查找

为什么省内存？

HashMap 为了避免过多的哈希冲突，引入了负载因子，打个比方，负载因子使用默认值 0.75，这意味着容量达到了 75%，就会开始扩容，也就是必然有 25% 的空间是不存储数据而被浪费的。而 SparseArray 可以把数组利用到最后一个空间。

复杂度为什么这么低？

SparseArray 做了两个优化：

1. 引入 DELETE 标记
   既然底层使用了数组，数组的缺点是什么？—— 删除数据时需要搬移元素。SparseArray 对数组的删除不做数据搬移，引入 DELETE 标记，以此达到在删除时做到 O(1) 的时间复杂度。

在调用 size()和put()需要扩容时，才去清理 DELETE 标识。

2. 优化追加元素
   SparseArray 提供了一个 append() 方法，来优化追加的情况。该方法会判断追加的 key 值，是否大于数组中最大的值，如果是则直接追加在数组末尾，否则执行 put() 方法插入 mKey 数组。

[yline]

我来说一下，这个应该是时代的原因。

HashMap和SparseArray，都是用来存储Key-value类型的数据。
于是同样的需要面对几个问题，hash值的计算、扩容、hash冲突、装载率过低

他们最大的不同就是：SparseArray采用的是开放定址法；而HashMap采用的是链地址法。
由于链地址法，是动态的生成链表节点，时间效率不如开放定址法。但也因为如此，hashmap装载率上限比sparseArray高。

现在早已经不是内存稀缺的时代了，因此在数据量较小的场景，这一点内存效率是让位于时间效率的。

因此系统推荐sparseArray，推荐arrayMap，来替代HashMap。。这是共同的问题。

[junlandroid]

数据结构方面：hashmap用的是链表。sparsearray用的是双数组。
性能方面：hashmap是默认16个长度，会自动装箱。如果key是int 的话，hashmap要先封装成Interger。sparseArray的话就就会直接转成int。所以spaseArray用的限制是key是int。数据量小于1k。如果key不是int小于1000的话。可以用Arraymap。

ArrayMap的mHashes[]和mArray[]分别存储的是key（升序排列）和key-value，mArray大小是mHashes的2倍。与SparseArray相比key可以为任何类型。请问是你所说 “key不是int小于1000的话。可以用Arraymap。” 这样吗？

[mlinqirong]

sparseArray代替HanshMap的条件 key为int 并存储量小