HashMap解决冲突是采用链表，性能上就抱有疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(n)的查找时间，这将是多么大的性能损失。

然后JDK8就解决了这个问题，在最坏的情况下，链表的查找时间复杂度为O(n)，而红黑树一直是O(logn)，这样会提高HashMap的效率。

而JDK8采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阈值的时候，这个链表就将转换成红黑树。