概述
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文主要分析一下HashMap中红黑树树化的过程。
红黑树（red black tree）
- 一个节点标记为红色或者黑色。
- 根是黑色的。
- 如果一个节点是红色的，那么它的子节点必须是黑色的（这就是为什么叫红黑树）。
- 一个节点到到一个null引用的每一条路径必须包含相同数目的黑色节点（所以红色节点不影响）。
其实RB Tree和著名的AVL Tree有很多相同的地方，困难的地方都在于将一个新项插入到树中。了解AVL Tree的朋友应该都知道为了维持树的高度必须在插入一个新的项后必须在树的结构上进行改变，这里主要是通过旋转，当然在RB Tree中原理也是如此。
...阅读原文
