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可以为任意的类型。而SparseAraay的key只能是整型。