底层数据结构
- 在jdk1.7及它之前是数组+链表；
在jdk1.8极其之后，是数组+（链表|红黑树）
jdk1.8数组索引计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
而索引值等于hash值和数组长度减一作与运算的结果。
由此也可以看出，HashMap允许键为空，之所以在计算hash值时，将原始hsahCode值与其右移16
位之后的值做异或操作，是为了综合高位数据，因为当数组长度较短时，利用上述算法计算索引值
原hashCode的高位数据会直接被丢弃，这样当数据低位hashCode类似时，产生hash碰撞的概率会
增大。
链表何时会转化为红黑树
当链表新增元素后长度大于8，并且数组的长度大于等于64时，链表会转化为红黑树。
- 为什么将链表转化为红黑树的时机选在此时
- 当数组的长度小于64时，可以通过扩容来缩短链表长度，且此时数组长度并不是很长，所以扩
容的开销是小于将链表转化为红黑树的开销的。 - 当链表的长度小于8时，此时链表遍历的开销并不算大，相反，如果在此时将链表转化为红黑树，
红黑树不仅所占内存空间更大，而且红黑树的维护开销更大；
当链表的长度大于8时，此时链表遍历的开销更大，应该创建红黑树来提高效率。
- 当数组的长度小于64时，可以通过扩容来缩短链表长度，且此时数组长度并不是很长，所以扩
红黑树何时会退化为链表
- 当数组扩容导致红黑树的拆分，树中的节点个数小于等于6时，红黑树会退化为链表。
- 当对红黑树中的节点进行remove操作时，如果root, root.left, root.right, root.left.left
为null时，红黑树也会退化为链表。
为什么数组的容量要为2的n次幂
* 当capacity = 2^n时，hash % capacity = hash & (capacity - 1)
* 当数组扩容时，链表会拆分，对于同一个链表中的节点来说，可通过 hash & oldCapacity是否等于零
拆分为两组，若等于零，则扩容之后索引位置不变，若不为零，则新索引位置等于旧索引位置加上旧的数
组容量。
数组扩容的负载因子为什么是0.75
- 若小于0.75则数组可能会频繁扩容，效率下降，空间利用率也会下降，但是链表的长度不会太长
- 若大于0.75则数组扩容频率下降，空间利用上升，但是链表的长度会变长
HashMap的put方法流程
- HashMap的数组是懒创建的，所以如果是第一次调用put会先创建数组；
- 计算key的hash值通过hash值得到数组索引，若数组索引处为null则直接new一个新的节点添加。
否则，比较第一个节点的key和参数中的key是不是同一个key，若不是，判断该节点是TreeNode
还是普通Node,然后按照对应的红黑树或者链表的方式去遍历进行更新或添加节点. - 若是链表添加节点，则在添加节点后要判断满不满足树化的条件。
- 如果是添加了节点，最后要判断需不需要对数组进行扩容。