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; 
 } 

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!