链表转红黑树

链表转红黑树阈值(8)的选择

泊松分布概率分析

在理想随机哈希码下,单个桶中出现8个元素的概率约为0.00000006(小于千万分之一),几乎不可能自然发生,因此把8作为触发阈值可以保证极端情况下的查找性能,同时避免在常规场景中无谓的树结构开销

空间与时间的折中

红黑树节点占用的空间大约为普通链表节点的两倍,将链表长度过短时就treeify会带来额外内存和旋转开销,不利于常规O(1)插入/查询的性能。因此仅在链表长度达到8时再treeify,能够以较小的空间成本换取极端情况下O(log n)的查找保证

红黑树降级回链表阈值(6)的选择

避免频繁转换

若将untreeify阈值同样设为8,当哈希冲突数在7至8之间波动时,桶会在链表和红黑树间频繁互相转换,导致不必要的旋转和内存分配/回收,进而影响性能。将回退阈值下调至6,可以扩大稳定区间,从而减少抖动​

设计中的其他考虑

桶容量要求(MIN_TREEIFY_CAPACITY)

HashMap在treeify前还额外要求表的容量(桶个数)必须至少为64(MIN_TREEIFY_CAPACITY),否则会优先进行扩容而非treeify,以避免在小表上引入树结构的复杂性和开销