HashMap
- 创建一个 hashMap时, 默认是一个容量为16的数组，数组中的每一个元素却又是一个链表的头节点。或者说HashMap内部存储结构 是使用哈希表的拉链结构（数组＋链表）
这种存储数据的方法 叫做拉链法
image
-
拉链法中的数组索引 是如何得到的? 通过计算元素key的hash值,然后对HashMap中数组长度取余得到该元素存储的位置。计算公式为 hash(key)%/len 。如果有多个元素的key的hash值相同,后一个元素并不会覆盖上一个元素，而是采取链表的方式，把之后加进来的元素加入链表末尾,从而解决hash冲突的问题（链地址法）
image - HashMap中默认的存储大小就是一个容量为16的数组。当hashMap存储元素达到当前元素的75%时,hashMap 的存储空间会扩大，而且扩大的新空间一定时原来的2倍。
当hashMap 达到扩容条件时,HashMap会以2倍的速度扩容，当我们有几十万、几百万数据时，hashMap 将造成内存空间的消耗和浪费。
SparseArray 稀疏矩阵
- SparseArray 存储 整型类型的 key
- SparseArray 比HashMap 更省内存,某些条件下 性能更好,主要是因为它避免了对key的自动装箱。
对比
HashMap<Integer,Object> hashMap = new HashMap<>();
SparseArray<Object> sparseArray = new SparseArray<>();
- SparseArray 内部使用两个数组来存储key 和 value。并且在存储和查找数据时 都使用二分查找法,因此SparseArray内部的key都是有序的。
HashMap<Integer,Object> hashMap = new HashMap<>();
SparseArray<Object> sparseArray = new SparseArray<>();
基本方法:
public void put(int key, E value)
public void remove(int key)
public void delete(int key)
public E get(int key)
public E get(int key, E valueIfKeyNotFound)
ArrayMap
- ArrayMap 是一个 <key,value>映射的数据结构。它设计上更多考虑内存的优化。内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值。
- 它和SparseArray一样，也会对key使用二分法进行从小到大排序。在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作。
- ArrayMap 与 SparseArray最大的一点不同就是 ArrayMap的key可以为任意的类型。而SparseArray的key只能是整型。
三者的使用场景：
HashMap 与 SparseArray比较
- 当数据量在1000以上,推荐使用HashMap。
- 当数据量 在500-1000，HashMap 和SparseArray性能差不多。
- 当数据量 少于500时,使用SparseArray 要优于HashMap。
SparseArray 与 ArrayMap使用场景：
- 当 key为整型时,推荐使用SparseArray
- 当 key为其它类型时,推荐使用ArrayMap
参考:
http://blog.csdn.net/u010687392/article/details/47809295
