3分钟让你大白：HashMap之红黑树树化进程

上面的要领通过hash计较插入的项的槽位，假若有是一样的key则按照配置的参数是否执行包围，假如响应槽位空的话直接插入，假如对应的槽位有项则判定是红黑树布局照旧链表布局的槽位，链表的话则顺着链表探求假如找到一样的key则按照参数选择包围，没有找到则链接在链表最后头，链表项的数量大于8则对其举办树化，假如是红黑树布局则凭证树的添加方法添加项。

让我们看一下treeifyBin这个要领。

final void treeifyBin(Node<K, V>[] tab, int hash) 
 { 
 int n, index; 
 Node<K, V> e; 
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
 // resize()要领这里不外多先容，感乐趣的可以去看上面的链接。 
 resize(); 
 // 通过hash求出bucket的位置。 
 else if ((e = tab[index = (n - 1) & hash]) != null) 
 { 
 TreeNode<K, V> hd = null, tl = null; 
 do 
 { 
 // 将每个节点包装成TreeNode。 
 TreeNode<K, V> 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<K, V> extends LinkedHashMap.Entry<K, V> 
 { 
 TreeNode<K, V> parent; // red-black tree links 
 TreeNode<K, V> left; 
 TreeNode<K, V> right; 
 TreeNode<K, V> prev; // needed to unlink next upon deletion 
 boolean red; 
 TreeNode(int hash, K key, V val, Node<K, V> next) 
 { 
 super(hash, key, val, next); 
 } 
  
 final void treeify(Node<K,V>[] tab) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) 
 { 
 // ...... 
 } 
  
 // ......别的要领省略 
 } 

可以看出出真正的维护红黑树布局的要领并没有在HashMap中，所有都在TreeNode类内部。

（编辑：湖南网）

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