【集合我能讲两小时009】jdk1.8的hashmap为什么在链表长度为8的时候判断红黑树？

jdk1.8的hashmap为什么在链表长度为8的时候判断红黑树？

在jdk1.8及以后的版本，hashmap采用的数据结构是，数组+链表，更改为在链表长度为8时，开始由链表转化为红黑树。

链表的时间复杂度是O(n)，红黑树的时间复杂度是o(logn),红黑树的时间复杂度是优于链表的。因为树节点所占空间是普通节点的2倍。所以当节点足够多时选择使用红黑树。也就是说，当节点比较少的时候，尽管红黑树的时间复杂度表现比链表好一些，但红黑树所占空间比链表大，综合考虑，在节点较多时，红黑树所占空间劣势相比查询性能的提升不那么明显时，转化为红黑时。

为什么选择8作为临界值呢？

在理想状况下，受随机分布hashcode的影响，链表中的节点遵循泊松分布。据统计链表中节点数是8的概率大概是千分之一，并且此时链表的性能很差了。在这种情况下，转化为红黑树，优化查询性能。