ConcurrentHashMap 红黑树会退化 成单向链表
时间: 2023-12-12 20:35:51 浏览: 29
ConcurrentHashMap是基于散列表实现的,底层使用数组+链表+红黑树+CAS算法实现的。在ConcurrentHashMap中,当链表长度大于等于8时,链表就会转化为红黑树,以提高查询效率。而在扩容时,如果TreeNode的长度小于等于6,就会退化为链表。这是因为当链表长度小于等于6时,使用链表的查询效率更高,而使用红黑树反而会降低效率。因此,ConcurrentHashMap中的红黑树会在特定情况下退化为单向链表。
相关问题
ConcurrentHashMap 用的是红黑树还是?
在JDK8及之前的版本中,ConcurrentHashMap使用了数组+链表的方式来实现并发安全。每个数组元素都是一个链表的头节点,用于解决哈希冲突。但在JDK8之后的版本中,当链表长度超过阈值(默认为8)时,会将链表转换为红黑树,以提高查询效率。
红黑树是一种自平衡的二叉查找树,它保持了良好的平衡性和高效的查找、插入和删除操作。将链表转换为红黑树能够在处理冲突时提供更高效的性能。
需要注意的是,并不是所有的链表都会被转换为红黑树,只有当链表长度超过阈值时,并且当前ConcurrentHashMap的容量达到一定程度时,才会进行转换。而当红黑树的节点数量小于一定程度时,又会将红黑树转换回链表,以避免过多的内存开销。
总结起来,ConcurrentHashMap在JDK8及之后版本中使用了数组+链表+红黑树的混合结构来实现并发安全和高效的操作。
ConcurrentHashMap为什么使用红黑树
ConcurrentHashMap使用红黑树的原因是为了提高在散列表中查询元素的效率。散列表实现的ConcurrentHashMap在插入元素后,会调用balanceInsertion()方法来让红黑树重新恢复平衡。红黑树作为一种自平衡的二叉查找树,可以保证在最坏情况下的查找、插入和删除操作的时间复杂度都是O(log n)。这样可以在散列表的扩容和哈希冲突较多的情况下,提供更快的查询性能。