一、HashMap
HashMap的数据结构
在java编程语言中，最基本的结构就是两种，一个是数组，另一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的。HashMap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列”）。
HashMap数据结构
带着问题理解HashMap
- HashMap默认长度为16（2^4）有什么意义？
- HashMap加载因子（loadfactor）为什么默认是0.75？
- key的hashCode与equals方法为什么要重写？
HashMap默认长度为16（2^4）有什么意义？
在HashMap中药要找到某个元素，需要通过key的hash值来求得对应数组中的位置。如何提高hashMap的访问性能，减少遍历链表？
static int indexFor(int h, int length) {
return h & (length-1);
}
首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。为什么hashMap的数组初始化大小都是2的次方大小时，hashMap的访问效率最高。
示意图
从上图知，左边两组是数组长度为16，右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
HashMap加载因子（loadfactor）为什么默认是0.75？
对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
对HashMap数组进行扩容（resize），最消耗性能。原数组中的数据必须重新计算其在新数组中的位置，并放进入。所以如果我们已经预知hashMap中的元素个数，那么预设元素的个数能够有效的提高hashMap的性能。
key的hashCode与equals方法为什么要重写？
hashMap数据结构get方法的过程：首先计算key的hashCode，找到数组中对应位置的某一个元素，然后通过key的equals方法再对应位置的链表中找到需要的元素。所以，hashCode与equals方法对于找到对应元素是两个关键方法。
Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等。
在改写equals方法的时候，需要满足以下三点：
(1) 自反性：就是说a.equals(a)必须为true。
(2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
(3) 传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。
通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
二、ArrayMap
简聊SparseArray
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型）。它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value。为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间。SparseArray只能存储key为int类型的数据，同时，SparseArray在存储和读取数据时候，使用的是二分查找法。
装箱和不装箱
满足下面两个条件我们可以使用SparseArray代替HashMap：
- 数据量不大，最好在千级以内
- key必须为int类型，这中情况下的HashMap可以用SparseArray代替
ArrayMap的数据结构
ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化。内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值。它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作。所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。
ArrayMap数据结构
当你想获取某个value的时候，ArrayMap会计算输入key转换过后的hash值，然后对hash数组使用二分查找法寻找到对应的index，然后我们可以通过这个index在另外一个数组中直接访问到需要的键值对。如果在第二个数组键值对中的key和前面输入的查询key不一致，那么就认为是发生了碰撞冲突。为了解决这个问题，我们会以该key为中心点，分别上下展开，逐个去对比查找，直到找到匹配的值。
ArrayMap获取数据
SparseArray与ArrayMap的选择
- 如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用；
- 如果key类型为其它的类型，则使用ArrayMap；
网友评论