前言
ArrayMap和SparseMap是android的系统API，是专门为移动设备而定制的，用于在一定情况下取代HashMap而达到节省内存的目的。
HashMap、ArrayMap和SparseArray实现原理及数据结构对比
1、HashMap
从HashMapdeep结构中可以看出，首先对key值求hash，根据hash结果确定在table数组中的位置，当出现哈希冲突时采用开放链地址法进行处理。
从空间角度分析，HashMap中会有一个利用率不超过负载因子（默认为0.75）的table数组，其次，对于HashMap的每一条数据都会用一个HashMapEntry进行记录，除了记录key、value外，还会记录下hash的值，及下一个entry的指针。
从时间效率分析，利用hash算法，插入和查找操作都很快，且一般情况下，每一个数组值后面不会存在很长的链表（因为出现hash冲突毕竟占比较小的比例），所以不考虑空间利用率的话，HashMap的效率非常高。
2、ArrayMap
ArrayMap利用两个数组，mHashes用来保存每一个key的hash值，mArray大小为mHashes的2倍，依次保存key和value。当插入时，根据key的hashcode()方法得到hash值，计算出在mArrays的index值，然后利用二分查找找到对应的位置进行插入，当出现哈希冲突时，会在index的相邻位置插入。
从空间效率考虑，ArrayMap每存储一条信息，需要保存一个hash值，一个key值，一个value值。对比下HashMap粗略地看，只是减少了一个指向下一个Entry的指针。
从时间效率上看，插入和查找的时候因为使用二分法，查找的时候应该是没有hash查找快，插入的时候，如果顺序插入的话效率肯定高，但如果是随机插入，会涉及到大量的数组搬移，数据量大，效率偏低。
3、SparseArray
SparseArray相对来说简单多了，但是不要以为它可以取代前两种，SparseArray只能在key为int的时候才能使用，因为key为int也就不需要什么hash值了，只要int值相等，那就是同一个对象，插入和查找也是基于二分法，所以原理和ArrayMap基本一致。
从空间上对比，与HashMap，去掉了Hash值的存储空间，没有next的指针占用，还有其他一些小的内存占用，节省了不少空间。
从时间上对比，插入和查找的情形和ArrayMap基本一致，可能存在大量的数组搬移，但是避免了装箱的环节，效率上还是相对可观的。
小结
- 在数据量小的时候一般认为1000以下，当key为int的时候，使用SparseArray确实是一个不错的选择，内存大概能节省30%左右，相比用HashMap，因为它的key值不需要装箱，所以时间性能平均来看也优于HashMap，建议使用。
- ArrayMap相对于SparseArray，特点是key值类型不受限制，任何情况下都可以取代HashMap，但是通过研究和测试发现，ArrayMap的内存节省并不明显，也就是在10%左右，但是时间性能是最差的。