2019-08-27：为什么推荐用SparseArray代替HashMap？
Opened this issue · 12 comments
sparseArray使用的是双数组实现，寻址采用二分法，比hashmap链表上挨着查找快。
然后hashmap的好像会自动装箱，spare不会
- int作为键,减少自动装箱操作;
- value使用纯粹的数组,结构相比hashmap简单,
- 二分查找,小数据量下更高效
- 延时回收,remove只是修改值引用,不删数据,不会时不会频繁压缩数组,在gc()函数后真正删除
类似的结构有ArrayMap,ArraySet等. 都是相似的优化, ArraySet还对长度为4,8内部数组,做了全局缓存,减少频繁创建的性能开销
并不能替换所有的HashMap。只能替换以int类型为key的HashMap。
HashMap中如果以int为key，会强制使用Integer这个包装类型，当我们使用int类型作为key的时候系统会自用装箱成为Integer，这个过程会创建对象一想效率。SparseArray内部是一个int数组和一个object数组。可以直接使用int减少了自动装箱操作。
因为sparseArray避免了对key的自动装箱（int转成integer），它的内部是采用2个数组来实现的；一个存储key 一个存储value；相对来说，性能更快，内部采用压缩方式节省内存空间；
sparseArray代替HashMap的时候最好存储的数量在千量级以下。
key必须是int类型，才可以替代hashmap
首先并不能说完全用SparseArray替代。在key是int并且数据量小于1000的情况下，用SparseArray替代确实在空间上性能要好，但是在时间上只能接近HashMap而已。
SparseArray的key固定是int所以减少了装箱和拆箱的操作
SpareArray内部是运用两个数组进行维护一个是keys存储key的，一个是values存储value的。由于key是int所以没有hash碰撞，在查找位置时用二分查找的方式，时间上比较有优势。
存储方法由于SparseArray存储的结构比HashMap简单，不需要维护链表等。所以存储上比HashMap好
1.. 并不慢;
2.. 省内存;
在数据量较小的安卓平台下, 安卓的集合框架, 更节省内存, 时间复杂度是log2n, 性能表现不俗;
如果是数据量较大, 例如超过1K, 还是用HashMap做, 更加合理一些;
hashMap, 图看不见, 点击去就好了
正如上面图示, hash 数组很有可能出现, 数组元素并未存满, 形成稀疏数组, 导致浪费内存;
所以 ArrayMap 更节省内存;
好多人回答, 为什么 ArrayMap 更节省内存, 总是回答, 扩容时候的系数, arraMap 存的是对象本身, HashMap 存的是 Node 包装类, 这个很多人, 就包括我. 后来我找答案了, 后续的面试中, 都会回答面试官想要我讲的, 稀疏数组的概念; 其实再做分析的时候, 很多人都看到了, 只是没往这方便想而已的.
数据结构方面：hashmap用的是链表。sparsearray用的是双数组。
性能方面：hashmap是默认16个长度，会自动装箱。如果key是int 的话，hashmap要先封装成Interger。sparseArray的话就就会直接转成int。所以spaseArray用的限制是key是int。数据量小于1k。如果key不是int小于1000的话。可以用Arraymap。
SparseArray三大特点
双数组、删除O(1)、二分查找
为什么省内存？
HashMap 为了避免过多的哈希冲突，引入了负载因子，打个比方，负载因子使用默认值 0.75，这意味着容量达到了 75%，就会开始扩容，也就是必然有 25% 的空间是不存储数据而被浪费的。而 SparseArray 可以把数组利用到最后一个空间。
复杂度为什么这么低？
SparseArray 做了两个优化：
- 引入
DELETE标记
既然底层使用了数组，数组的缺点是什么？—— 删除数据时需要搬移元素。SparseArray对数组的删除不做数据搬移，引入 DELETE 标记，以此达到在删除时做到 O(1) 的时间复杂度。
在调用 size()和put()需要扩容时，才去清理 DELETE 标识。
- 优化追加元素
SparseArray提供了一个append()方法，来优化追加的情况。该方法会判断追加的key值，是否大于数组中最大的值，如果是则直接追加在数组末尾，否则执行put()方法插入mKey数组。
我来说一下，这个应该是时代的原因。
HashMap和SparseArray，都是用来存储Key-value类型的数据。
于是同样的需要面对几个问题，hash值的计算、扩容、hash冲突、装载率过低
他们最大的不同就是：SparseArray采用的是开放定址法；而HashMap采用的是链地址法。
由于链地址法，是动态的生成链表节点，时间效率不如开放定址法。但也因为如此，hashmap装载率上限比sparseArray高。
现在早已经不是内存稀缺的时代了，因此在数据量较小的场景，这一点内存效率是让位于时间效率的。
因此系统推荐sparseArray，推荐arrayMap，来替代HashMap。。这是共同的问题。
数据结构方面：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。” 这样吗？
sparseArray代替HanshMap的条件 key为int 并存储量小