HashMap 简介
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）。
底层数据结构分析
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (数组长度- 1) & hash 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
红黑树:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）为空(NIL或NULL)的叶子节点是黑色。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
优点
1. 如果插入一个节点引起了树的不平衡，平衡二叉树和红黑树都是最多只需要2次旋转操作。但是在删除节点引起树的不平衡时，最坏情况下，平衡二叉树需要维护该节点整条路径的平衡性，因此需要旋转的量级O(logN)，而红黑树最多只需3次旋转，只需要O(1)的复杂度。
2. 其次，平衡二叉树的结构相较RB-Tree来说更为平衡，在插入和删除节点更容易引起Tree的不平衡，因此在大量数据需要插入或者删除时，平衡二叉树需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于平衡二叉树高度平衡，因此AVL的搜索效率更高。
