本文源码基于 JDK 1.8.0_101 。
在 JDK 1.8 之前，HashMap 采用 槽数组 + 单链表 来实现；
在 JDK 1.8 开始采用 槽数组 + 单链表 + 红黑树 来实现。
1. 为什么引入红黑树？
解决哈希冲突时、链表过长导致访问效率低下的问题。
为什么是红黑树不是其他树：
二叉排序树在极端情况下会退化成线性结构。
平衡二叉树（AVL树）是严格平衡树，在增加或删除节点时，旋转次数比红黑树要多。红黑树的统计性能高于 AVL 树。红黑树特性，RBT树上的每个节点，都要遵循下面的规则：
① 每个节点都是红色或者黑色；
② 根节点必须始终是黑色；
③ 没有两个相邻的红色节点；
④ 对每个结点，从该结点到其子孙节点的所有路径上包含相同数目的黑结点。