面试系列Java中级：为什么HashMap引入红黑树？_hashmap为什么引入红黑苏

        因为在JDK1.7之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个数组中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

HashMap的红黑树是如何解决的？

HashMap开始将链表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了

为什么不直接采用红黑树还要用链表？ 

因为红黑树需要进行左旋，右旋操作， 而单链表不需要，
如果元素小于8个，查询成本高，新增成本低
如果元素大于8个，查询成本低，新增成本高