HashMap 底层数据结构

JDK7：数组+链表
JDK8: 数组+链表+红黑树

JDK8 中的 HashMap 为什么要使用红黑树？

当元素个数小于一个阈值时，链表整体的插入查询效率要高于红黑树，当元素个数大于此阈值时，链表整体的插入查询效率要低于红黑树。此阈值在HashMap中为8

JDK8 中的 HashMap 什么时候将链表转化为红黑树？

这个题很容易答错，大部分答案就是：当链表中的元素个数大于8时就会把链表转化为红黑树。但是其实还有另外一个限制：当发现链表中的元素个数大于8之后，还会判断一下当前数组的长度，如果数组长度小于64时，此时并不会转化为红黑树，而是进行扩容。只有当链表中的元素个数大于8，并且**数组的长度大于等于64**时才会将链表转为红黑树。

上面扩容的原因是，如果数组长度还比较小，就先利用扩容来缩小链表的长度。

JDK8 中 HashMap 的 put 方法的实现过程？

  1. 根据key生成hashcode
  2. 判断当前HashMap对象中的数组是否为空，如果为空则初始化该数组
  3. 根据逻辑与运算，算出hashcode基于当前数组对应的数组下标i
  4. 判断数组的第i个位置的元素（tab[i]）是否为空
    1. 如果为空，则将key，value封装为Node对象赋值给tab[i]
    2. 如果不为空：
      1. 如果put方法传入进来的key等于tab[i].key，那么证明存在相同的key
      2. 如果不等于tab[i].key，则：
        1. 如果tab[i]的类型是TreeNode，则表示数组的第i位置上是一颗红黑树，那么将key和value插入到红黑树中，并且在插入之前会判断在红黑树中是否存在相同的key
        2. 如果tab[i]的类型不是TreeNode，则表示数组的第i位置上是一个链表，那么遍历链表寻找是否存在相同的key，并且在遍历的过程中会对链表中的结点数进行计数，当遍历到最后一个结点时，会将key,value封装为Node插入到链表的尾部，同时判断在插入新结点之前的链表结点个数是不是大于等于8，如果是，则将链表改为红黑树。
      3. 如果上述步骤中发现存在相同的key，则根据onlyIfAbsent标记来判断是否需要更新value值，然后返回oldValue
  5. modCount++
  6. HashMap的元素个数size加1
  7. 如果size大于扩容的阈值，则进行扩容

JDK7 与 JDK8 中 HashMap 的不同点

  1. JDK8中使用了红黑树
  2. JDK7中链表的插入使用的头插法（扩容转移元素的时候也是使用的头插法，头插法速度更快，无需遍历链表，但是在多线程扩容的情况下使用头插法会出现循环链表的问题，导致CPU飙升），JDK8中链表使用的尾插法（JDK8中反正要去计算链表当前结点的个数，反正要遍历的链表的，所以直接使用尾插法）
  3. JDK7的Hash算法比JDK8中的更复杂，Hash算法越复杂，生成的hashcode则更散列，那么hashmap中的元素则更散列，更散列则hashmap的查询性能更好，JDK7中没有红黑树，所以只能优化Hash算法使得元素更散列，而JDK8中增加了红黑树，查询性能得到了保障，所以可以简化一下Hash算法，毕竟Hash算法越复杂就越消耗CPU
  4. 扩容的过程中JDK7中有可能会重新对key进行哈希（重新Hash跟哈希种子有关系），而JDK8中没有这部分逻辑
  5. JDK8中扩容的条件和JDK7中不一样，除开判断size是否大于阈值之外，JDK7中还判断了tab[i]是否为空，不为空的时候才会进行扩容，而JDK8中则没有该条件了