HashMap与SparseArray简单总结
HashMap：
1、hashMap采用了数组+链表+红黑树来存储数据。
2、每一个键值对封装为一个节点Node<K,V>,存在一个数组Node<K,V>[] table，其元素为Node节点。其次，数组中每个元素也都有一个链表结构，此链表用来存储下标位置相同但内容不同的节点，每有一个这样的节点就插入到链表尾部。
3、put操作时，使用key的hashcode值计算其在table中的数组索引，遍历数组，找到该索引元素，如果为空，则直接将node插入到当前数组位置。
4、若不为空，判断两个key的hashcode值和内容是否相等，相等则直接替换value，插入完成。
5、若两个节点不是同一个，那么开始遍历节点所在的链表，在链表中查找比较key，没有查找到则插入到链表尾部。若链表size大于8，则将其转为红黑树，将节点插入到树中。为什么是8呢，可以看下源码里的解释，
``
``
设为8其实是一个保底策略。因为链表的长度分布满足泊松分布，长度为8的概率为千万分之六，可以说接近于0了。这么设置的用意在于，保证在极端情况下，链表不会无限制增长，否则查找消耗会非常大。此时将其转为红黑树，查找效率会优于链表。而只要我们哈希函数设唤伍置合理的话，链表的长度基本都达不到8，也不会出现转和运或为红黑树的最差情况。
6、table的初始size为16，每次添加完table元素后会判断是否超出悄迟，超出就进行扩容，扩容size总为2的幂。还有一个关键的属性，负载因子loadFactor，初始值为0.75。这个负载因子表示table的存储空间利用率，我们知道，table不是所有位置都会存储元素的。为什么要设为0.75，首先，如果这个负载因子越大，表明空间利用率越高，扩容的次数相对就少，但是这样在插入新元素时发生位置碰撞的几率就越大，进而就会增加对应链表的长度，那么链表变长了，查询效率相应地就变低了；而若负载因子越小，那么空间利用率越低，table中空闲位置越多，同样的表的长度相对地只能存储更少的元素，因此插入元素时发生扩容操作的机会就越大，元素更多的是存在table数组中，而不是发生冲突存到链表中，查找效率会比较快。
总结起来，上述两种情况各有优劣。综合考虑空间开销和查找效率，负载因子既不能太大也不能太小。又因为，链表的长度满足泊松分布，大于8的几率微乎其微，把负载因子设为0.75，链表长度基本不可能超过8，同时更不可能转化为红黑树了。所以设为0.75是在通常情况下，综合考虑了查找效率和空间开销的折衷选择。
7、关于红黑树，它也是一种二叉搜索树，红黑树的查找效率优于二叉搜索树，增删的效率优于平衡二叉树。可以认为是结合了两者的优点。
SparseArray：
1、sparsearray采用了int[] mKeys 和 Object[] mValues两个数组来分别存储key和value。
2、对于某个key值，先查找其在mKeys中的索引i，直接mValues[i]获取key对应的value，也就是说key与其对应的value存储下标是一样的。
且看sparsearray的put方法，非常易懂，
``
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
``
3.sparsearray对mKeys数组做了正序排列，因此，在进行遍历查找key时，使用的是二分查找法，一切为了效率。
4.sparsearray使用int类型，不同与hashmap使用Integer，省去了自动装箱过程，消耗更少内存。
总的来说，sparseArray内存性能优于hashMap，一般适用于key为整型值，数据量较少的应用场景。也是考虑内存优化时替代Hash Map的首选。
