全部面试刷题微服务数据库消息队列搜索引擎大数据运维 go语言机器学习

HashMap的数据结构是数组+链表/红黑树，那什么情况下才会用到红黑树呢？

提问者：帅平问题分类：面试刷题

HashMap的数据结构是数组+链表/红黑树，那什么情况下才会用到红黑树呢？

您阅读本篇文章共花了：

Java面试题

发布于：1年前 (2023-03-16) IP属地：四川省

1 个回答

步江湖

当数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树，当红黑树大小为6时，会退化为链表。
这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量。
链表查询时间复杂度O(N)，插入时间复杂度O(1)，红黑树查询和插入时间复杂度O(logN)

发布于：1年前 (2023-03-16) IP属地：四川省

我来回答