|
01 概述 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文主要分析一下HashMap中红黑树树化的过程。 02 红黑树（red black tree） 一个节点标记为红色或者黑色。 根是黑色的。 如果一个节点是红色的，那么它的子节点必须是黑色的（这就是为什么叫红黑树）。 一个节点到到一个null引用的每一条路径必须包含相同数目的黑色节点（所以红色节点不影响）。 其实RB Tree和著名的AVL Tree有很多相同的地方，困难的地方都在于将一个新项插入到树中。了解AVL Tree的朋友应该都知道为了维持树的高度必须在插入一个新的项后必须在树的结构上进行改变，这里主要是通过旋转，当然在RB Tree中原理也是如此。 03 两种旋转和一种典型的变换 旋转的方向： 变换过程： 互相关联： 单向关联： 代表红色的节点： 代表黑色的节点： 代表一个不会破坏红黑树结构的部分，可能是节点，或者是一个子树，总之不会破环当前树的结构。这个部分会由于旋转而连接到其他的节点后面，我们可以理解成由于重力原因它掉到了下面的节点上：
单旋转变换。双旋转变换（需要两次反方向的单旋转）。当遇到两个子几点都为红色的话执行颜色变换，因为插入 是红色的会产生冲突。如果根节点两边的子节点都是红色，两个叶子节点变成黑色，根节点变成红色，然后再将根节点变成黑色。 上面的图中描述了红黑树中三种典型的变换，其实前两种变换这正是AVL Tree中的两种典型的变换。 04 几个问题 4.1 为什么要进行旋转？ 由于P和X节点都为红色节点这破环了红节点下面的节点必须为黑色节点的规则。 4.2 新加入的节点总是红色的，这是为什么呢？ 因为被插入前的树结构是构建好的，一但我们进行添加黑色的节点，无论添加在哪里都会破坏原有路径上的黑色节点的数量平等关系，所以插入红色节点是正确的选择。 4.3 为什么要进行颜色变换？ 正如第一种旋转新加入的节点X破坏了红黑树的结构不得不进行旋转，后面的就是旋转后的结果，旋转后形成新的结构，此时我们发现两个子节点都是红色的所以执行第三个变换特性，颜色变换，因为如果子节点是红色的那么我们在添加的时候只能添加黑色的节点，然而添加任何黑色叶子节点都会破坏树的第四条性质，所以要对其进行变换。当进行变换后叶子节点是红色的而且我们默认添加的叶子节点是红色的，所以添加到黑色节点后并不会破坏树的第四条结构，所以这种变换很有用。 第二种双变换中在树的内部怎么出现的红色的节点？ 正是由于上面的颜色变换导致新颜色变换后的节点与他的父节点产生了颜色冲突。 与AVL树相比？ 比AVL树相比优点是不用在节点类中保存一个节点高度这个变量，节省了内存。 而且红黑树一般不是以递归方式实现的而是以循环的形式实现。 一般的操作在最坏情形下花费O（logN）时间。 05 好了有了这些基本的概念让我们去看一下HashMap中的代码的实现 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node [] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) // 如果当前的bucket里面已经是红黑树的话，执行红黑树的添加操作 e = ((TreeNode ) p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0;; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD = 8，判断如果当前bucket的位置链表长度大于8的话就将此链表变成红黑树。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 上面的方法通过hash计算插入的项的槽位，如果有是一样的key则根据设置的参数是否执行覆盖，如果相应槽位空的话直接插入，如果对应的槽位有项则判断是红黑树结构还是链表结构的槽位，链表的话则顺着链表寻找如果找到一样的key则根据参数选择覆盖，没有找到则链接在链表最后面，链表项的数目大于8则对其进行树化，如果是红黑树结构则按照树的添加方式添加项。 让我们看一下treeifyBin这个方法。 final void treeifyBin(Node [] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // resize()方法这里不过多介绍，感兴趣的可以去看上面的链接。 resize(); // 通过hash求出bucket的位置。 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode hd = null, tl = null; do { // 将每个节点包装成TreeNode。 TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { // 将所有TreeNode连接在一起此时只是链表结构。 p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 对TreeNode链表进行树化。 hd.treeify(tab); } } 找个方法所做的事情就是将刚才九个项以链表的方式连接在一起，然后通过它构建红黑树。 看代码之前我们先了解一下TreeNode static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } final void treeify(Node [] tab) { // ...... } static TreeNode balanceInsertion(TreeNode root, TreeNode x) { // ...... } static TreeNode rotateLeft(TreeNode root, TreeNode p) { // ...... } static TreeNode rotateRight(TreeNode root, TreeNode p) { // ...... } // ......其余方法省略 } 可以看出出真正的维护红黑树结构的方法并没有在HashMap中，全部都在TreeNode类内部。 我们看一下treeify代码 final void treeify(Node [] tab) { TreeNode root = null; // 以for循环的方式遍历刚才我们创建的链表。 for (TreeNode x = this, next; x != null; x = next) { // next向前推进。 next = (TreeNode ) x.next; x.left = x.right = null; // 为树根节点赋值。 if (root == null) { x.parent = null; x.red = false; root = x; } else { // x即为当前访问链表中的项。 K k = x.key; int h = x.hash; Class kc = null; // 此时红黑树已经有了根节点，上面获取了当前加入红黑树的项的key和hash值进入核心循环。 // 这里从root开始，是以一个自顶向下的方式遍历添加。 // for循环没有控制条件，由代码内break跳出循环。 for (TreeNode p = root;;) { // dir：directory，比较添加项与当前树中访问节点的hash值判断加入项的路径，-1为左子树，+1为右子树。 // ph：parent hash。 int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) 15 else 16 pp.left = l;
7.最后执行层17和18行。 17 l.right = p; 18 p.parent = l;
最终完成两次的旋转。 08 疑问？ 大家可能觉得和刚才接不上其实是这样的，刚才在右旋转前的时候的图像是这个样的。
因为我们传进来的是XPP，所以结合上一次的向左旋转我们在向右旋转的时候看到全图应该是这个样子的。（注：XPPP可能是XPP的左父节点也可能是右父节点这里不影响，而且可以是任意颜色）
现在知道为什么XPPP可以是任意颜色的了吧，因为旋转过后X是黑色的即便XPPP是红色，此时我们又可以对两个红色的子节点进行颜色变换了，变换后X和XPPP有发生了颜色冲突，接着进行旋转直到根。 static TreeNode balanceInsertion(TreeNode root, TreeNode x) { x.red = true; for (TreeNode xp, xpp, xppl, xppr;;) { if ((xp = x.parent) == null) { x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) return root; if (xp == (xppl = xpp.left)) { // 插入位置父节点在祖父节点的左边。 } else { // 插入位置父节点在祖父节点的右边。 } } } 我们值分析了插入位置父节点在祖父节点的左边的情况，并没有分析另外一面的对称情况，其实是一样的因为调用的都是相同的方法。 以上就是在1.8中的HashMap新引进的红黑树树化的过程，与原来的链表相比当同一个bucket上存储很多entry的话树形的查找结构明显要比链表线性的的效率要高。 原文链接：https://juejin.im/post/5d9fbd72e51d45781a677c87 |
