HashMap为什么要用红黑树？

文章地址 数据结构笔试面试知识集合之HashMap的红黑树

当HashMap中有大量的元素存放都同一个桶中时，这个桶下有一条长长的链表，这个时候HashMap就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。

针对这种情况，JDK1.8中引入了红黑树来优化这个问题，为什么不引入二叉查找树呢？因为二叉查找树的一般操作的执行时间为O(lgn)，但是二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。与单链表一样。

所以此时我们需要红黑树它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。