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

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

提问者：帅平 问题分类：面试刷题
HashMap的数据结构是数组+链表/红黑树，那什么情况下才会用到红黑树呢？
Java面试题
发布于：9个月前 (03-16) IP属地：四川省
1 个回答
步江湖
步江湖
当数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树，当红黑树大小为6时，会退化为链表。
这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量。
链表查询时间复杂度O(N)，插入时间复杂度O(1)，红黑树查询和插入时间复杂度O(logN)
发布于：9个月前 (03-16) IP属地：四川省
我来回答