美的终面: 说一下HashMap为什么要用红黑树,红黑树有什么优点?二叉树的时间复杂度是多少?

[MicroKibaco]

[MicroKibaco]

数据结构很薄弱,需要恶补!

java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。

红黑树他有如下特性: 1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

二叉树的时间 最终查找、插入、删除的时间复杂度最坏情况下都是O(logn)