为什么Map桶【链表】中个数超过8才转为红黑树

  • Post author:
  • Post category:其他


要弄明白这个问题,我们首先要明白为什么要转换,这个问题比较简单,

因为Map中桶的元素初始化是链表保存的,其查找性能是O(n),而树结构能将查找性能提升到O(log(n))。

当链表长度很小的时候,即使遍历,速度也非常快,但是


当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。


至于为什么阈值是8,我想,去源码中找寻答案应该是最可靠的途径。

—————————————————————————————

Map桶中个数超过8才转为红黑树,即


阈值为8

8这个阈值定义在HashMap中,如下所示,这段注释只说明了8是bin(bin就是bucket,即HashMap中hashCode值一样的元素保存的地方)从链表转成树的阈值,但是并没有说明为什么是8:



/**



* The bin count threshold for using a tree rather than list for a



* bin. Bins are converted to trees when adding an element to a



* bin with at least this many nodes. The value must be greater



* than 2 and should be at least 8 to mesh with assumptions in



* tree removal about conversion back to plain bins upon



版权声明:本文为u013231917原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。