集合初探--认识Map
1. HashMap
A）底层数据结构
·HashMap存储结构是由数组与单向链表构成（Hash表），如上图：水平方向是一个Entry数组，垂直方向是一个单向链表，每个数组元素都是单向链表的头，每个单向链表元素都具有相同index值（散列值）。
·这种结构决定了HashMap存取很快：由元素hash值确定操作哪个单向链表，影响的元素只涉及到某个链表，这就是所谓的“桶”机制（简单说不同的东西放在不同的位置，需要时才能快速找到）。
·HashMap每一个元素（数组或链表中的元素）都是一个包含四个属性：key,value,hash,next的一种数据结构，其中next指向链表中下一个元素；hash存储的是每个元素key的hash值。
·如果存在key=null的元素，则一定存在table[0]位置。上图table[0]链表后还有元素，这种情况若要发生，只有当元素的hash值为0的情况，index才为0。
·loadFactor--负载（装载）因子，定义为：散列表的实际元素数目(n)/散列表的容量(m)。负载因子与HashMap resize有关。默认值为DEFAULT_LOAD_FACTOR=0.75。
·负载因子衡量的是一个散列表的空间的使用程度，越大表示散列表的装填程度越高，反之愈小。
·对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，如果负载因子越大，空间利用更充分，但查找效率会降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
·capacity：HashMap容器大小，也就是数组table[]长度。默认值为DEFAULT_INITIAL_CAPACITY=16。最大值是MAXIMUM_CAPACITY=1 << 30。
·table（Entry[] table）：即为上面数据结构图中X方向的数组。
·threshold ：HashMap resize的临界值，即当HashMap中元素个数达到该值时，HashMap就会调用其resize方法，重新扩充大小。
·Entry：HashMap中的静态内部类。HashMap每个元素的实际存储结构。
B）构造方法
·构造HashMap：重点在于Entry对象数组的构造。
·可以看出，Entry数组大小capacity一定是2的倍数：即默认大小为16，或可以由传入参数initialCapacity控制，最终capacity也是>= initialCapacity的2的倍数。
·threshold的计算：capacity * loadFactor；loadFactor默认0.75，可以参数传入。
B）插入对象
很明显了，它的目的是让“1”变的均匀一点。
·Entry数组index的计算
很明显table.length是偶数时，冲突的可能性更小。这就是为什么capacity的值一定是2的倍数。
C）get对象，remove对象
·跟插入对象思路一样：先计算hash值，根据hash值得到数组的位置index，然后遍历单向链表，找到相应位置。
D）遍历对象
·KeySet遍历HashMap
·LinkedHashMap继承于HashMap，其基本操作与父类HashMap相似，通过重写父类相关方法，实现其特性。
·Entry也继承于HashMap中的Entry，但增加了两个属性：before--指向上一个Entry；after--指向下一个Entry，从而在哈希表的基础上又构成了双向链接列表。
·可以看出底层使用哈希表与双向链表来保存所有元素。除了通过增加header来作为双向链表的头元素，其哈希表存储方式跟HashMap完全一样。即有HashMap快速随机存取的特点，又能支持顺序遍历所有元素。
·按照何种顺序遍历是由accessOrder决定，accessOrder为false--插入顺序（上图即为插入三个元素后的结构，遍历顺序为header->1->2->3），为true--访问顺序。默认为插入顺序。
B）构造方法public V get(Object key) { // 调用父类HashMap的getEntry()方法，取得要查找的元素。 Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // 记录访问顺序。 e.recordAccess(this); return e.value;}void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // 如果定义了LinkedHashMap的迭代顺序为访问顺序， // 则删除以前位置上的元素，并将最新访问的元素添加到链表header之前。 if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); }}
3.TreeMap
·TreeMap底层采用一棵“红黑树”来保存集合中的 Entry（详细代码分析，学习红黑树算法后再来看，感兴趣的可以先参考：通过分析 JDK 源代码研究 TreeMap 红黑树算法实现）
·一个关于红黑树系列文章推荐：教你透彻了解红黑树
