3分钟让你明白：HashMap之红黑树树化过程

 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<K, V>[] tab; 
 Node<K, V> 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<K, V> 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<K, V>) 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; 
 } 

（编辑：ASP站长网）