导语：HashMap TreeNode红黑树代码跟踪

1、验证红黑树生成代码

import java.util.HashMap;import java.util.Map;public class HashMain {    public static void main(String[] args) {        int count = 0;        for (int i=65 ; ; i+= 128){            if( count ++ < 20 ){                System.out.print( i + );            }else{                break;            }        }        HashMap<Integer,Integer> map = new HashMap();        map.put( 65 , 65 );        map.put( 193 , 193 );        map.put( 321 , 321 );        map.put( 449 , 449 );        map.put( 577 , 577 );        map.put( 705 , 705 );        map.put( 833 , 833 );        map.put( 961 , 961 );        insert(map);      //断点打在这里 ==》debug        map.put( 1089 , 1089 );    }//因为红黑树生成条件map的size必须大于64,所以我们需要将属性进行填充    private static void insert(Map<Integer,Integer> map){        int counter = 0 ;        for ( int i=0 ;  ; i++ ) {            int keyVal = 100 + i ;            if( keyVal % 16 != 1 ){                if( counter++ >87 ){                    break;                }                map.put( keyVal , keyVal );            }        }    }}

2、进入put方法

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;  //n =128 if ((tab = table) == null || (n = tab.length) == 0)     //...     // p = Node(65,65)     if ((p = tab[i = (n - 1) & hash]) == null)     Node<K,V> e; K k;    //进行遍历，将链表通过尾插法 p.next = newNode 放入最后      for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        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;                }}

3、链表红黑树转换逻辑

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();  //进入到这个位置，e=Node(65,65)节点    else if ((e = tab[index = (n - 1) & hash]) != null) {        TreeNode<K,V> hd = null, tl = null;        do {          //TreeNode(65,65)            //TreeNode(193,193)           //TreeNode(321,321)            TreeNode<K,V> p = replacementTreeNode(e, null);            if (tl == null)              //TreeNode(65,65)                hd = p;            else {              //TreeNode(193,193) . prev =  TreeNode(65,65)               //TreeNode(321,321) . prev = TreeNode(193,193)                 p.prev = tl;//TreeNode(65,65).next = TreeNode(193,193)              // TreeNode(193,193).next = TreeNode(321,321)                tl.next = p;            }          //tl迁移如下：          //TreeNode(65,65)          //TreeNode(193,193)            tl = p;          //Node(193,193)          //Node(321,321)        } while ((e = e.next) != null);            //将红黑树放入到数组的对应下标 65        if ((tab[index] = hd) != null)            hd.treeify(tab);    }}TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {  //初始化TreeNode  p为Node(65,65)节点，next为null        return new TreeNode<>(p.hash, p.key, p.value, next);    }//TreeNode 继承自LinkedHashMap.Entrystatic 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);        }  //省略...}//static class Entry<K,V> extends HashMap.Node<K,V> {        Entry<K,V> before, after;  //此处为        Entry(int hash, K key, V value, Node<K,V> next) {            super(hash, key, value, next);        }    }

4、红黑树状态标记

final void treeify(Node<K,V>[] tab) {    TreeNode<K,V> root = null;    for (TreeNode<K,V> x = this, next; x != null; x = next) {        next = (TreeNode<K,V>)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<K,V> 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<K,V> 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);}

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小葵创作整理编辑！