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

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

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

1 个回答
步江湖
步江湖

当数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树,当红黑树大小为6时,会退化为链表。

这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量。

链表查询时间复杂度O(N),插入时间复杂度O(1),红黑树查询和插入时间复杂度O(logN)

发布于:6天前
我来回答