面试真题

结论：链表长度过大时查找复杂度退化为O(n)，转换为红黑树可将查找、插入、删除稳定控制在O(log n)。原理：以HashMap为例，当桶中节点数超过8且表容量≥64时链表转红黑树；红黑树是自平衡二叉搜索树，通过颜色翻转与旋转保持黑高平衡，最坏情况深度约2log(n+1)；而链表需遍历。对比：红黑树节点占用空间约为链表2倍，短链表转树反而慢，故设阈值8（泊松分布下冲突8概率千万分之6）。示例：冲突桶达16节点，链表需16次比较，红黑树最多4次。空间换时间应对哈希碰撞恶化。