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

上面的方法通过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类内部。

（编辑：ASP站长网）