ConcurrentHashMap 转换红黑树过程

系统管理员 2023-01-01 03:43 188阅读 0赞

## ConcurrentHashMap 转换红黑树过程 ##

### 开始转换控制条件 1 ###

> 某个节点的链表长度大于等于 8

if (binCount >= TREEIFY_THRESHOLD)

### 开始转换控制条件 2 ###

> 如果数组长度小于64 就会扩容，否则转换成红黑树

if ((n = tab.length) < MIN_TREEIFY_CAPACITY)

### 开始转换 ###

/** * hd记录原来链表的一个节点 */
            ConcurrentHashMap.TreeNode<K,V> hd = null;
            /** * tl 记录上一个链表节点 */
            ConcurrentHashMap.TreeNode<K,V> tl = null;
            /** * 遍历节点下的链表 */
            for (ConcurrentHashMap.Node<K,V> e = b; e != null; e = e.next) { 
                /** * 初始化一个TreeNode 对象 */
                ConcurrentHashMap.TreeNode<K,V> p =
                        new ConcurrentHashMap.TreeNode<K,V>(e.hash, e.key, e.val,
                                null, null);
                /** * 如果TreeNode的子节点是空 */
                if ((p.prev = tl) == null)
                    hd = p;
                else
                /** * 将上一个节点的子节点指向当前节点 */
                    tl.next = p;
                tl = p;
            }

> 这个就看不明白了

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { 
            U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
        }

TreeBin(TreeNode<K,V> b) { 
                super(TREEBIN, null, null, null);
                this.first = b;
                TreeNode<K,V> r = null;
                for (TreeNode<K,V> x = b, next; x != null; x = next) { 
                    next = (TreeNode<K,V>)x.next;
                    x.left = x.right = null;
                    if (r == null) { 
                        x.parent = null;
                        /** 第一个节点是黑 */
                        x.red = false;
                        r = x;
                    }
                    else { 
                    //记录当前元素的key
                        K k = x.key;
                        //当前元素的 hash值
                        int h = x.hash;
                        Class<?> kc = null;
                        for (TreeNode<K,V> p = r;;) { 
                            int dir, ph;
                            //pk 上一个节点的key 
                            K pk = p.key;
                            /* 上一个节点的hash 和当前节点的hash值比较大小 */
                            if ((ph = p.hash) > h)
                                dir = -1;//上一个节点的hash值大 dir 为负数
                            else if (ph < h)
                                dir = 1;//上一个节点的hash值小 dir 为正数
                            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;//上一个节点的hash值大 那么x 当前节点放到上一个节点的左侧
                                else
                                    xp.right = x;//上一个节点的hash值小 那么x 当前节点放到上一个节点的右侧
                                    // 翻转 后续待看
                                r = balanceInsertion(r, x);
                                break;
                            }
                        }
                    }
                }
                this.root = r;
                assert checkInvariants(root);
            }

### 重写 equals 和hashCode 方法 尽量走进 转换红黑二叉树逻辑 ###

public static class Stringover { 
            private String name;
            private int hash;
            Stringover(){ 
    
            }
            Stringover(String name){ 
                this.name=name;
            }
            @Override
            public boolean equals(Object anObject) { 
                return false;
            }
            @Override
            public int hashCode() { 
                int h = 121212;    
                return h;
            }
        }

### 测试方法 ###

public static void main(String[] args) { 
            ConcurrentHashMap<Stringover,String> requestMap= new ConcurrentHashMap<Stringover,String>(64);
            for (int i=0;i<100;i++){ 
                Stringover key=new Stringover("heshan"+String.valueOf(i));
                System.out.println(key);
                requestMap.put(key, "heshan"+String.valueOf(i));
            }
    }