共 3 篇相关文章
这篇讲的是一个经典的Java面试题：为什么HashMap的桶中链表长度达到8才转为红黑树？作者从一个好友的阿里面试经历切入，直接打开了源码中的注释，发现它只记录了阈值，却未解释原因。 文章的核心在于对源码“Implementation notes”的深入解读。作者指出，红黑树节点占用的空间是普通节点的两倍，因此转换是一种空间与时间的权衡。更关键的是，文章引用了源码中一段关于泊松分布的注释：在随机哈希算法下，桶中节点数量遵循特定的概率分布，链表长度达到8的概率极低（仅约千万分之六）。这从统计学角度证明了阈值8的选取并非随意，而是经过严谨计算的。 此外，文章也驳斥了一种常见但不够严谨的“性能对比”解释，强调了设计背后的科学性。通过剖析源码与概率模型，这篇文章将一个常见面试考点还原成了其严谨的设计思想，适合所有想理解Java集合框架底层优化的开发者。
这篇讲的是红黑树，作者从一个初学者的常见困惑出发：红黑树情况太多，似乎很难。文章给出的核心解法是“合并”——通过归结和简化情况来降低理解门槛。 作者首先回顾了红黑树必须满足的五个性质，然后直接切入数据结构定义和基础的二叉搜索树操作。全文的重点放在对插入与删除算法的拆解上。对于插入，文章将其归结为三种核心情况，通过逐步调整颜色和旋转来维持性质。对于删除，分析则更为细致，分多种情况（例如“兄弟节点颜色”或“侄节点颜色”不同）讨论了重新着色和旋转的策略，并配以直观的印象图和伪代码。 整篇文章像一份详尽的算法推演笔记，通过枚举具体场景并展示调整步骤，试图将复杂的平衡操作变得有迹可循。对于想从原理层面弄懂红黑树实现细节的读者，这种直面各种案例的讲解方式可能比单纯记忆规则更有帮助。
这篇讲的是如何从零开始理解红黑树这个经典数据结构。作者没有直接抛出复杂定义，而是带着读者层层拆解：先厘清“二叉树”与“二叉搜索树”的基础特征，再切入红黑树的核心命题——如何通过额外的规则（如节点颜色约束）维持树的平衡性，从而保证搜索、插入和删除操作的稳定效率。 文章特别强调了“平衡”在动态数据结构中的实际意义，并对比了完全平衡与近似平衡的权衡思路。对于红黑树五大性质的推导过程，文中通过简化的示意图展示了旋转操作如何局部调整树形而不破坏全局秩序，这种直观的呈现对理解其巧妙设计很有帮助。 如果你正在学习高级数据结构，或是对平衡树的工程实现感兴趣，这篇笔记提供了一个从概念到直观的平滑入口，有助于建立对红黑树更扎实的直觉认知。
