安卓开发中 HashMap 与 SparseArray 的比较

问题来自 Android Studio 的智能(zhang)提示,当你试图使用 int 作为一个 Map 的 Key 值时,AS 都会弹出提示告知推荐使用安卓特有的(Java 是没有的)SparseArray(稀疏数组)来替代且可以得到更好的性能,即使用 HashMap<int, ?> 类型时会推荐使用 SparseArray<?> 替代。

作为杠精有着刨根问底这一优秀品质、并且在项目需求中确实需求性能的我,决定一探究竟,究竟更好的性能是表现在哪些方面,更好是有多好?

官方文档的解释是这样的:

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.

意思就是,与普通 Map 不同,SparseArray 不会对每一个 value 都提供空间来保存。

那这又是什么意思呢?比如 HashMap 中,尽管我没有使用一个地址,但是可能该地址仍然会被保存,因为 HashMap 会保存一个完整的表,见下图。

HashMap原理.png

而 SparseArray 则不保存完整的表,它只保存表哪个位置被使用了,该位置的值是多少,类似一维表,而 HashMap 则更像是二维表。

显而易见,由于保存的数据少,SparseArray 对内存的占用更少,并且在数据较少的时候正向查询效率极高!

SparseArray 采用了二分查找法,就是说先从头查找一定内存内的数据,如果没有找到需要查找的数据,会扩大搜索的内存范围继续查找,以此类推。

那么好处和坏处已经很明显了,HashMap 直接计算 Hash code 查找内容,于是在数据比较少的时候速度不如 SparseArray,可是数据越多,两者速度差异越小,最后 HashMap 是会反超 SparseArray 的速度的,并且因为 SparseArray 是从头开始查询,如果咱们逆向查询(比如查询最后一个数据)需要的时间非常非常非常长

但是,SparseArray 因为存储数据的方式,内存占用始终比 HashMap 小,在安卓中单个堆栈的最大内存为 16MB,因此内存方面的节省也是有必要的,可以合理考虑牺牲掉一部分性能来换取内存表现。

可是我的项目数据量说多也不多,说不多也多,这个时候内存是不可能溢出的,并且这个数据量来看 SparseArray 效率不一定还能超过 HashMap,那么我只好选择性能了(嘻…嘻嘻嘻.jpg)!


注意:只有在 Map 的 Key 值为 int 类型的时候才可使用 SparseArray,Integer 都不可以!这也是 SparseArray 效率较高的原因之一,数据无需封包。