1. 全栈程序员必看首页

HashMap之TreeNode

全栈程序员-站长 • • 未分类 • 阅读 1

HashMap之TreeNodeHashMap 之 TreeNode 简述在分析 HashMap 之前先说一下内部类 TreeNode TreeNode 类是一颗红黑树的各种操作 当然 TreeNode 不只是简单的红黑树操作 还有与 HashMap 业务相关的代码先看一下类的继承关系 Entry 是一个接口 主要有一些让子类去实现的 get set 方法 Node 是一个单向链表最后就是 TreeNode 红黑树了先看一下简单的 Node 单向链表

HashMap之TreeNode

先看一下简单的Node单向链表，然后再看复杂一点的TreeNode

static class Node 
  
    implements Map.Entry 
   
     { final int hash; final K key; V value; Node 
    
      next; Node(int hash, K key, V value, Node 
     
       next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry 
       e = (Map.Entry 
      )o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

很简单，一个Node相当于链表的一个节点，next属性对应着下一个节点

  1. 每个节点或是红色，或是黑色的
  2. 跟节点是黑色的
  3. 每个叶节点（NIL）是黑色的
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的
  5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数码的黑节点
    如图
    这里写图片描述
    叶节点（NIL）不包含任何数据，只是一个标记，没有实际意义


下面通过红黑树的插入、删除、查找、左旋、右旋进一步了解TreeNode

先看一下构造

TreeNode(int hash, K key, V val, Node 
  
    next) { super(hash, key, val, next); }

可以看到调用了父类的构造方法，也就是说，TreeNode是红黑树的同时也是一个单项链表

  • 使P成为根节点并变成黑色满足性质2
  • G成为P的右节点
  • P的右节点成为G的左节点
static 
  
    TreeNode 
   
     rotateRight(TreeNode 
    
      root, TreeNode 
     
       p) { TreeNode 
      
        l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; } 
       
      
     
    
  
 final TreeNode 
  
    find(int h, Object k, Class 
    kc) { TreeNode 
   
     p = this; do { int ph, dir;K pk; TreeNode 
    
      pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; }

分3点来说find方法

1.find方法根据当前节点的hash与参数的h比较，如果大于pl赋值给p，如果小于pr赋值给p，相等的情况通过当前节点的key与参数的key比较，不相等在通过equals方法比较。

2.接下来在判断如果pl等于null把br赋值给p，pr等于null的话吧pl赋值给p，都不等于空的话在根据key实现的Comparable比较。comparableClassFor方法是获取k的运行时类型，compareComparables方法先判断，key与运行时kc是同类型，在通过调用k和kc实现的Comparable接口的compareTo进行比较

static int compareComparables(Class 
   kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); }

3.以上这些条件如果都不满足，那右节点通过递归比较找到则返回，找不到，把左节点赋值给p，进入下次循环在比较

final TreeNode 
  
    putTreeVal(HashMap 
   
     map, Node 
    
      [] tab, int h, K k, V v) { Class 
      kc = null; boolean searched = false; TreeNode 
     
       root = (parent != null) ? root() : this; 
      
     
    
  
final TreeNode 
  
    root() { for (TreeNode 
   
     r = this, p; ; ) { if ((p = r.parent) == null) return r; r = p; } }

就剩下一个for循环了

for (TreeNode 
  
    p = root;;) { int dir, ph; K pk; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode 
   
     q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } 
    
  
static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; } 
TreeNode 
  
    xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node 
   
     xpn = xp.next; TreeNode 
    
      x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode 
     
       )xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null; } 
      
     
    
  
TreeNode 
  
    newTreeNode(int hash, K key, V value, Node 
   
     next) { return new TreeNode<>(hash, key, value, next); }

没什么特别的就是创建一个TreeNode

 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)) { if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }

好了，现在在来看moveRootToFront方法

static 
  
    void moveRootToFront(Node 
   
     [] tab, TreeNode 
    
      root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; TreeNode 
     
       first = (TreeNode 
      
        )tab[index]; if (root != first) { Node 
       
         rn; tab[index] = root; TreeNode 
        
          rp = root.prev; if ((rn = root.next) != null) ((TreeNode 
         
           )rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } assert checkInvariants(root); } }

上面解释了tab参数，第5行取出经过balanceInsertion摧残之后的根节点，第6行判断如果与摧残之前的节点不同，通过7-17的代码调整链表顺序

删除

 final void removeTreeNode(HashMap 
  
    map, Node 
   
     [] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode 
    
      first = (TreeNode 
     
       )tab[index], root = first, rl; TreeNode 
      
        succ = (TreeNode 
       
         )next, pred = prev; if (pred == null) tab[index] = first = succ; else pred.next = succ; if (succ != null) succ.prev = pred; if (first == null) return; if (root.parent != null) root = root.root(); if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { tab[index] = first.untreeify(map); // too small return; } 
        
       
      
     
    
  
TreeNode 
  
    p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { TreeNode 
   
     s = pr, sl; while ((sl = s.left) != null) // find successor s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode 
    
      sr = s.right; TreeNode 
     
       pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode 
      
        sp = s.parent; if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) != null) pr.parent = s; } p.left = null; if ((p.right = sr) != null) sr.parent = p; if ((s.left = pl) != null) pl.parent = s; if ((s.parent = pp) == null) root = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr != null) replacement = sr; else replacement = p; }

处理完左右节点都不为空的情况，接下来该处理，左节点不为null右节点为null、右节点不为null左节点为null、左右都为null

else if (pl != null) replacement = pl; else if (pr != null) replacement = pr; else replacement = p; 
 if (replacement != p) { TreeNode 
  
    pp = replacement.parent = p.parent; if (pp == null) root = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } TreeNode 
   
     r = p.red ? root : balanceDeletion(root, replacement);

这里删除节点通过判断replacement != p，那么如果replacement == p

if (replacement == p) { // detach TreeNode 
  
    pp = p.parent; p.parent = null; if (pp != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } if (movable) moveRootToFront(tab, r); }

简单：如果replacement现在是跟节点黑加黑，什么也不做。或者当前是红黑色，只需要把当前节点染成黑色，就恢复了红黑树的性质

 static 
  
    TreeNode 
   
     balanceDeletion(TreeNode 
    
      root, TreeNode 
     
       x) { for (TreeNode 
      
        xp, xpl, xpr;;) { if (x == null || x == root) return root; else if ((xp = x.parent) == null) { x.red = false; return x; } else if (x.red) { x.red = false; return root; } else if ((xpl = xp.left) == x) { if ((xpr = xp.right) != null && xpr.red) { xpr.red = false; xp.red = true; root = rotateLeft(root, xp); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr == null) x = xp; else { TreeNode 
       
         sl = xpr.left, sr = xpr.right; if ((sr == null || !sr.red) && (sl == null || !sl.red)) { xpr.red = true; x = xp; } else { if (sr == null || !sr.red) { if (sl != null) sl.red = false; xpr.red = true; root = rotateRight(root, xpr); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr != null) { xpr.red = (xp == null) ? false : xp.red; if ((sr = xpr.right) != null) sr.red = false; } if (xp != null) { xp.red = false; root = rotateLeft(root, xp); } x = root; } } } else { // symmetric

TreeNode与红黑树相关的操作就这些了，旋转、查找、出入、删除。为了满足HashMap重置内部数组大小，还有一个拆分方法。当HashMap需要扩容时候，就会调用拆分方法，把红黑树拆分成两个链表，如果两个链表大于一定的值，那么就还转成红黑树，否则就转换成链表

拆分

 final void split(HashMap 
  
    map, Node 
   
     [] tab, int index, int bit) { TreeNode 
    
      b = this; // Relink into lo and hi lists, preserving order TreeNode 
     
       loHead = null, loTail = null; TreeNode 
      
        hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode 
       
         e = b, next; e != null; e = next) { next = (TreeNode 
        
          )e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } 
         
        
       
      
     
    
  
static final int UNTREEIFY_THRESHOLD = 6; 
 final void treeify(Node 
  
    [] tab) { TreeNode 
   
     root = null; for (TreeNode 
    
      x = this, next; x != null; x = next) { next = (TreeNode 
     
       )x.next; x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class 
       kc = null; for (TreeNode 
      
        p = root;;) { 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) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode 
       
         xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); } 
        
       
      
     
    
  
inal Node 
  
    untreeify(HashMap 
   
     map) { Node 
    
      hd = null, tl = null; for (Node 
     
       q = this; q != null; q = q.next) { Node 
      
        p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; }

到这里TreeNode就说完了，这样下一篇看HashMap分析的时候就会轻松很多了

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/202542.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月19日 下午11:53
下一篇 2026年3月19日 下午11:54


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号