HashMap
简介
HashMap 采用key/value存储结构，每个key对应唯一的value
查询和修改的速度都很快，能达到O(1)的平均时间复杂度，非线程安全的，且不保证元素存储的顺序
存储结构
JDK 1.8中，HashMap 的实现采用了（数组 + 链表 + 红黑树）的复杂结构
添加元素时，根据元素的hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素，则把元素以链表的形式放置在链表的尾部
当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则会把链表转化为红黑树，从而提高效率
数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率
核心成员变量
int DEFAULT_INITIAL_CAPACITY = 1 << 4
数组默认的初始容量为16
int MAXIMUM_CAPACITY = 1 << 30
数组最大的容量为2的30次方
float DEFAULT_LOAD_FACTOR = 0.75f
默认的装载因子为0.75
int TREEIFY_THRESHOLD = 8
当一个桶中的元素个数大于等于8时进行树化
int UNTREEIFY_THRESHOLD = 6
当一个桶中的元素个数小于等于6时把树转化为链表
int MIN_TREEIFY_CAPACITY = 64
当桶的个数达到64的时候才进行树化
Node<K,V>[] table
数组，又叫作桶（bucket）
float loadFactor
装载因子，不建议修改，会影响扩容的速度
int threshold
表示当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor
重点理解扩容和树化的时机
1、容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化<br>
2、装载因子用来计算容量达到多少时才进行扩容，默认装载因子为0.75<br>
size > threshold
3、树化，当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时反树化<br>
构造方法
HashMap()
空参构造方法，全部使用默认值<br>
HashMap(int initialCapacity, float loadFactor)
判断传入的初始容量和装载因子是否合法<br>
计算扩容门槛，扩容门槛为传入的初始容量最近的2的n次方<br>
HashMap(int initialCapacity)
调用HashMap(int initialCapacity, float loadFactor)构造方法，传入默认装载因子<br>
几处优化
优化后的降低冲突概率的hash算法
代码实现
思想：计算好的hash值右移16位的结果与计算好的hash值进行异或运算作为真正的hash值，保留hash值高16位和低16的特征
结果：hash值的高低16位都可以参与后面索引位置的运算，降低冲突的概率
高性能hash寻址算法
代码实现
思想：hash值与（n - 1）进行与运算，计算元素在哪个桶中(hash 寻址)
结果：hash值与（n - 1）进行与运算，性能更好
数组刚开始的初始值，以及未来每次扩容的值，都是2的n次方，只要保证数组的大小是2的n次方，就可以保证hash值与（n - 1）进行与运算和直接hash值对数组长度取模计算元素对应数组索引位置index的效果一样
高性能rehash算法
hash值对数组长度取模计算元素对应数组索引位置index的性能不高，所以是基于hash值与（n-1）进行与运算来优化性能
JDK 1.8，扩容一定是2的倍数，保证说，每次扩容之后，重新rehash，元素的位置要么还是原来的那个index（5）的位置，要么是变成原来的index（5）+ oldCap（16） = 21的位置
put(K key, V value))
第一步，计算key的hash值
第二步，如果桶（数组）数量为0，则初始化桶，无参构造函数会使用默认初始容量，默认负载因子
第三步，(n - 1) & hash 计算元素在哪个桶中(hash 寻址)，也就是元素在数组中的index位置
第四步，插入元素
第一种情况，如果这个桶中还没有数据，则创建一个节点放在桶中的第一个位置
如果这个桶中已经存在元素
第二种情况，如果桶中第一个位置的元素的key和插入元素的key相同，则判断是否需要替换旧值，并直接返回旧值
第三种情况，如果桶中元素是一棵红黑树，则在红黑树中插入一个节点
第四种情况，则遍历桶对应的链表查找key是否存在于链表中
如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化，链表转成红黑树
树化的条件：链表的长度大于等于8，同时，数组的长度大于64
树化的过程：先是把链表转成TreeNode组成的双向链表，然后将双向链表转成一棵红黑树
树化的效果：优化性能，链表和红黑树的时间复杂度
第五步，插入元素成功，数组数量加1，并判断是否需要扩容
数组扩容
底层是基于数组实现，存在扩容问题
扩容原理非常简单，2倍扩容
扩容的过程：JDK 1.7，重新rehash，基于key的hash值对数组长度取模进行重新计算，重新在新的数组里找到新的位置，很多key在新数组的位置都不一样，之前冲突的key，现在可能就分布在新数组不同的位置，这里具体看下JDK 1.8对rehash的优化
get(Object key)
第一步，计算key的hash值
第二步，(n - 1) & hash 计算元素在哪个桶中(hash 寻址)，也就是元素在数组中的index位置
第三步，匹配元素
第一种情况，如果当前位置元素的hash值和要获取元素的hash值一样，并且key也相同，匹配元素
否则
第二种情况，如果当前桶位置是一棵红黑树，遍历红黑树，直至匹配元素
第三种情况，如果当前桶位置是一个链表，遍历链表，直至匹配元素
第四步，返回元素key对应的value值
LinkedHashMap
对于HashMap来说，如果遍历HashMap，遍历的结果，不会按照插入key-value元素的顺序进行遍历
LinkedHashMap是HashMap的子类，会记录插入key-value元素的顺序，可以实现顺序遍历
底层基于链表实现，内部维护一个双向链表，迭代遍历的时候，会从链表头部顺序遍历
新增元素
LinkedHashMap重写newNode(int hash, K key, V value, Node<K,V> e)方法，会将元素加入到内部的双向链表的尾部
覆盖元素
默认情况下，覆盖元素不会改变元素在双向链表的顺序
如果需要改变元素在双向链表中的顺序，可以将accessOrder参数设置为true，保证说每次覆盖元素都会把元素移动到双向链表的尾部
afterNodeAccess(Node<K,V> e)方法代码实现
删除元素
将元素从内部双向链表中移除
afterNodeRemoval(Node<K,V> e)方法代码实现
TreeMap
对于HashMap来说，如果遍历HashMap，遍历的结果，不会按照插入key-value元素的顺序进行遍历
底层基于红黑树实现，自己实现的一个数据结构
TreeMap会按照key的大小顺序进行排序，可以定制Comparator，自己实现排序的算法
(key/value) 的映射结构，Map 中的元素是一个 key 只能对应一个 value，不能存在重复的key
