为什么 HashMap 要用红黑树?

admin_user 2026-05-09
20 次浏览 0 个回答
最近在准备面试,复习到HashMap源码的时候,发现JDK 8里链表长度超过8就会转成红黑树。我大概知道是为了提高查找效率,但具体为什么要用红黑树而不是其他平衡树,比如AVL树?我自己查了一些资料,说红黑树插入和删除的旋转次数更少,但也没讲太清楚到底好在哪。我现在试着画过红黑树的插入过程,感觉逻辑挺绕的,不太明白为什么偏偏选它。希望有大佬能解释一下:HashMap用红黑树到底解决了什么核心问题?和AVL树比,在哈希表这种场景下优势在哪?最好能结合源码或者实际例子说明一下,谢谢!
PHP