JDK8的HashMap为什么要引入红黑树？

手机游戏开发者 · 2024-10-7 13:41:15

当HashMap的key辩论过多时，会导致链表过长。而链表的查询服从很差，因此引入红黑树优化查询服从。
为什么当链表长度大于8时间才会转红黑树而不是一开始直接使用红黑树：
树节点占用空间是平凡节点的两倍，因此在开始较短时间使用链表，占用空间少，查询性能也相差不大。但是当链表越来越长，查询服从徐徐变低，为保证查询服从才会舍弃链表转为红黑树，以空间换时间。
根据统计，HashMap链表长度为8的概率仅有不到万万分之一，这时链表的查询性能很差了。在这种极度稀有的情况下才会将链表转换为红黑树。

JDK8的HashMap为什么要引入红黑树？

所属分类: 问答交流

新帖推荐: 30日

推荐作品