欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ConcurrentHashMap源码笔记

程序员文章站 2022-04-05 10:01:42
...
CAP原则又称CAP定理,指的是在一个分布式系统中,Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可得兼。
ConcurrentHashMap在线程安全的基础上提供了更好的写并发能力,但同时降低了对读一致性的要求。

1、接口和父类

ConcurrentHashMap源码笔记

ConcurrentHashMap扩展了AbstractMap类, 实现了ConcurrentMap接口和Serializable接口。

2、定义的常量和变量

 

     //最大是的可容量 
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    
     
     //默认的初始容量 最大值是MAXIMUM_CAPACITY = 1 << 30
    private static final int DEFAULT_CAPACITY = 16;

    
    //数组最大的长度
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    
     /**
	 *并发度,即同时更新ConcurrentHashMap且不产生锁竞争的最大线程数,也就是分段锁的个数,
	 *默认为16.一经指定,便不可改变。如果元素增加导致扩容,也不会增加segment的数量,
	 *只会增加segment中数组链表的容量的大小。
	 **/
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    
      
     //负载因子
    private static final float LOAD_FACTOR = 0.75f;

    
      
     //链表转换为红黑树过程就是一个红黑树增加节点的过程。在put过程中,
	 //如果发现链表结构中的元素超过了TREEIFY_THRESHOLD(默认为8),则会把链表转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;

    
      
     //红黑树转链表的阀值,当链表长度<=6时转为链表(扩容时)
    static final int UNTREEIFY_THRESHOLD = 6;

    
      
      
	//哈希表的最小树形化容量,当哈希表中的容量大于这个值时,表中的桶才能进行树形化
	//否则桶内元素太多时会扩容,而不是树形化,为了避免进行扩容、树形化选择的冲突,这个值不能小
    static final int MIN_TREEIFY_CAPACITY = 64;

    
     
      
	// 扩容操作中,transfer这个步骤是允许多线程的,这个常量表示一个线程执行transfer时,最少要对连续的16个hash桶进行transfer
	//     (不足16就按16算,多控制下正负号就行)
	// 也就是单线程执行transfer时的最小任务量,单位为一个hash桶,这就是线程的transfer的步进(stride)
	// 最小值是DEFAULT_CAPACITY,不使用太小的值,避免太小的值引起transfer时线程竞争过多,如果计算出来的值小于此值,就使用此值
	// 正常步骤中会根据CPU核心数目来算出实际的,一个核心允许8个线程并发执行扩容操作的transfer步骤,这个8是个经验值,不能调整的
	// 因为transfer操作不是IO操作,也不是死循环那种100%的CPU计算,CPU计算率中等,1核心允许8个线程并发完成扩容,理想情况下也算是比较合理的值
	// 一段代码的IO操作越多,1核心对应的线程就要相应设置多点,CPU计算越多,1核心对应的线程就要相应设置少一些
	// 表明:默认的容量是16,也就是默认构造的实例,第一次扩容实际上是单线程执行的,看上去是可以多线程并发(方法允许多个线程进入),
	//     但是实际上其余的线程都会被一些if判断拦截掉,不会真正去执行扩容
    private static final int MIN_TRANSFER_STRIDE = 16;

    
     //控制的bit数  暂时不甚明白
    private static int RESIZE_STAMP_BITS = 16;

    
     // The maximum number of threads that can help resize.
      //Must fit in 32 - RESIZE_STAMP_BITS bits.
     
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

    
      //The bit shift for recording size stamp in sizeCtl.
     
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

//01111111_11111111_11111111_11111111
static final int HASH_BITS = 0x7fffffff;

3、put方法

key和value都不能为空。

final V putVal(K key, V value, boolean onlyIfAbsent) {
//如果key或者value
        if (key == null || value == null) throw new NullPointerException();
		//两次hash,减少hash冲突,可以均匀分布
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
			//初始化数组
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)// // 转发节点,此时正在进行扩容
                tab = helpTransfer(tab, f);//帮组扩容
            else {
                V oldVal = null;
                synchronized (f) {
				//如果链表树超过8,则修改链表为红黑树
                    if (tabAt(tab, i) == f) {
					//按照链表操作
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
						//按照红黑树
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
				//链表长度大于8的时候改为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
		// 判断是否需要扩容
        addCount(1L, binCount);
        return null;
    }
	
	
	
	
	
	
	
	
	
	
	
	
	
	//spread(int h)
	static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;//01111111_11111111_11111111_11111111
    }
	
	
	//initTable()
	private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//当前线程 利用CAS 将SIZECTL置为-1
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);////设置一个扩容的阈值
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }
	
	
	
	
	//获得在i位置上的Node节点
	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }
	
	
	//利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
        //在CAS算法中,会比较内存中的值与你指定的这个值是否相等,如果相等才接受你的修改,否则拒绝你的修改
    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }
	
	
	
	
	
	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
		//ForwardingNode是一种临时节点,在扩容进行中才会出现,hash值固定为-1,并且它不存储实际的数据数据。
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)// // 判断下是否能真正帮助此次扩容(这4个条件前面说了,少了的那一个不用前面判断了)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {// // 不满足前面4个条件时,尝试参与此次扩容,把正在执行transfer任务的线程数加1
                    transfer(tab, nextTab);// 去帮助执行transfer任务
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
	
	
	// 返回与扩容有关的一个生成戳rs,每次新的扩容,都有一个不同的n,这个生成戳就是根据n来计算出来的一个数字,n不同,这个数字也不同
	// 另外还得保证 rs << RESIZE_STAMP_SHIFT 必须是负数
	// 这个方法的返回值,当且仅当 RESIZE_STAMP_SIZE = 32时为负数
	static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }
	
	
	
	
	
	//扩容过程
	private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
		//static final int NCPU = Runtime.getRuntime().availableProcessors(); //可用处理器个数
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; 
			// private static final int MIN_TRANSFER_STRIDE = 16;
			// 每个线程所负责转移的数组的区间最少为 MIN_TRANSFER_STRIDE=16,也就是说数组的连续16个位置都是由这个线程来进行转移,
			// 其他线程不允许接触这连续的16个位置,必须发生线程之间大量的内存冲突。换另一个角度来说,每个线程负责连续16个大小区间的数组转移。
        if (nextTab == null) {            // 初始化生成新的扩容数组
            try {
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];  //新创建两倍原数组大小的新数组
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;  //nextTable为类成员变量,只有在扩容的过程中有作用,在其他时刻都是null值。nextTable指向新数组
            transferIndex = n;   //转移后的节点偏移量
        }
        int nextn = nextTab.length;
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;   //遍历
        boolean finishing = false; //保证在提交扩容后的新数组时,原数组中的所有元素都已经被遍历
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)   //bound为数组区间下限值,i为当前转移数组的位置,--i处理转移下一个节点位置,从后往前处理
                    advance = false;  //退出while循环
                else if ((nextIndex = transferIndex) <= 0) {   //表示原数组已经分割完了
                    i = -1;
                    advance = false;  //退出while循环
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,    
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {  //CAS操作修改transferIndex值,代表下一个线程转移原数组的节点的位置
                    bound = nextBound;  //设置当前线程转移原数组区间的下限值
                    i = nextIndex - 1;  //从后往前处理
                    advance = false;  //退出while循环
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {   //扩容完成
                    nextTable = null;   //将nextTable置为null,表示当前扩容过程完成
                    table = nextTab;    //table指向扩容后的新数组
                    sizeCtl = (n << 1) - (n >>> 1);  //将szieCtl设置为正数,设置为原数组的3/2,即新数组的3/4
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)   //因为只有一个线程扩容时sc=resizeStamp(n)+2,所以该if语句是在最后一个线程完成扩容操作时,将finishing置为true,表示正确完成。
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);   //将原数组相应位置直接设置为fwd,表示该位置已经遍历过
            else if ((fh = f.hash) == MOVED)
                advance = true; // 表示该数组位置已经被其他线程处理过了
            else {  //否则需要将原数组位置相应元素复制到新数组上
                synchronized (f) {   //上锁
                    if (tabAt(tab, i) == f) {   //再次核对,防止其他线程对该hash值进行修改
                        Node<K,V> ln, hn;
                        if (fh >= 0) {   //说明该位置存放的是普通节点
                            int runBit = fh & n;  //判断原数组中的节点的hash的 log(n)位为0或者1
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {   
                                ln = lastRun;  //指向链表的最后出现连续log(n)位为0的第一个节点
                                hn = null;
                            }
                            else {     
                                hn = lastRun;   //指向链表的最后出现连续log(n)位为1的第一个节点
                                ln = null;
                            }
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            setTabAt(nextTab, i, ln);   //将hash值的 log(n) 位为0的节点链表复制到新数组对应原来数组的位置
                            setTabAt(nextTab, i + n, hn);  //将Hash值的 log(n) 位为1的节点链表复制到新数组对应原来数组位置+n
                            setTabAt(tab, i, fwd);  //将该数组位置设置为已处理
                            advance = true;
                        }
                        else if (f instanceof TreeBin) {   //说明该数组位置是红黑树根节点
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {   //判断红黑树中节点的hash值的 log(n) 位为0,说明该节点应该存放到新数组中对应原数组的位置
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {    //判断红黑树中节点的hash值的 log(n) 位为1,说明该节点应该存放到新数组中对应原数组位置+n
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            //根据链表中节点的个数和UNTREEIFY_THRESHOLD进行比较,如果小于等于,则不需要将链表转换为红黑树;如果大于,则需要将链表转换为红黑树
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :   
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            setTabAt(nextTab, i, ln);   //复制到新数组中
                            setTabAt(nextTab, i + n, hn);  //复制到新数组中
                            setTabAt(tab, i, fwd);  //将原数组中相应位置为fwd,表示该位置已经被处理过
                            advance = true;  //继续进行遍历
                        }
                    }
                }
            }
        }
    }
	
	
	
	//查询或者添加节点
	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if (p == null) {
                    first = root = new TreeNode<K,V>(h, k, v, null, null);
                    break;
                }
                else if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.findTreeNode(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.findTreeNode(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    TreeNode<K,V> x, f = first;
                    first = x = new TreeNode<K,V>(h, k, v, f, xp);
                    if (f != null)
                        f.prev = x;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    if (!xp.red)
                        x.red = true;
                    else {
                        lockRoot();
                        try {
                            root = balanceInsertion(root, x);
                        } finally {
                            unlockRoot();
                        }
                    }
                    break;
                }
            }
            assert checkInvariants(root);
            return null;
        }
	
	
	
	
	
	
	
	 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                TreeNode<K,V> x) {
        x.red = true;       // 所有节点默认插入为红
        for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {

            // x.parent == null,为跟节点,置黑即可
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            }
            // x 父节点为黑色,或者x 的祖父节点为空,直接插入返回
            else if (!xp.red || (xpp = xp.parent) == null)
                return root;

            /*
             * x 的 父节点为红色
             * ---------------------
             * x 的 父节点 为 其祖父节点的左子节点
             */
            if (xp == (xppl = xpp.left)) {
                /*
                 * x的叔父节点存在,且为红色,颜色交换即可
                 * x的父节点、叔父节点变为黑色,祖父节点变为红色
                 */
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                    /*
                     * x 为 其父节点的右子节点,则为内侧插入
                     * 则先左旋,然后右旋
                     */
                    if (x == xp.right) {
                        // 左旋
                        root = rotateLeft(root, x = xp);
                        // 左旋之后x则会变成xp的父节点
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }

                    /**
                     * 这里有两部分。
                     * 第一部分:x 原本就是其父节点的左子节点,则为外侧插入,右旋即可
                     * 第二部分:内侧插入后,先进行左旋,然后右旋
                     */
                    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);
                        }
                    }
                }
            }
        }
    }
	

4、get方法

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

5、replace方法、remove方法

	public V remove(Object key) {
        return replaceNode(key, null, null);
    }
	
	
    final V replaceNode(Object key, V value, Object cv) {
        int hash = spread(key.hashCode());
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                boolean validated = false;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            validated = true;
                            for (Node<K,V> e = f, pred = null;;) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
						//红黑树
                        else if (f instanceof TreeBin) {
                            validated = true;
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> r, p;
                            if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                                V pv = p.val;
                                if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                    oldVal = pv;
                                    if (value != null)
                                        p.val = value;
                                    else if (t.removeTreeNode(p))
                                        setTabAt(tab, i, untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                if (validated) {
                    if (oldVal != null) {
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }	
	
	
	
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }	
	
	
	
	final boolean removeTreeNode(TreeNode<K,V> p) {
            TreeNode<K,V> next = (TreeNode<K,V>)p.next;
            TreeNode<K,V> pred = p.prev;  // 取消链接遍历指针
            TreeNode<K,V> r, rl;
            if (pred == null)
                first = next;
            else
                pred.next = next;
            if (next != null)
                next.prev = pred;
            if (first == null) {
                root = null;
                return true;
            }
            if ((r = root) == null || r.right == null || // too small
                (rl = r.left) == null || rl.left == null)
                return true;
            lockRoot();
			//红黑树的旋转和重新着色
            try {
                TreeNode<K,V> replacement;
                TreeNode<K,V> pl = p.left;
                TreeNode<K,V> pr = p.right;
                if (pl != null && pr != null) {
                    TreeNode<K,V> 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<K,V> sr = s.right;
                    TreeNode<K,V> pp = p.parent;
                    if (s == pr) { // p was s's direct parent
                        p.parent = s;
                        s.right = p;
                    }
                    else {
                        TreeNode<K,V> 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)
                        r = s;
                    else if (p == pp.left)
                        pp.left = s;
                    else
                        pp.right = s;
                    if (sr != null)
                        replacement = sr;
                    else
                        replacement = p;
                }
                else if (pl != null)
                    replacement = pl;
                else if (pr != null)
                    replacement = pr;
                else
                    replacement = p;
                if (replacement != p) {
                    TreeNode<K,V> pp = replacement.parent = p.parent;
                    if (pp == null)
                        r = replacement;
                    else if (p == pp.left)
                        pp.left = replacement;
                    else
                        pp.right = replacement;
                    p.left = p.right = p.parent = null;
                }

                root = (p.red) ? r : balanceDeletion(r, replacement);

                if (p == replacement) {  // detach pointers
                    TreeNode<K,V> pp;
                    if ((pp = p.parent) != null) {
                        if (p == pp.left)
                            pp.left = null;
                        else if (p == pp.right)
                            pp.right = null;
                        p.parent = null;
                    }
                }
            } finally {
                unlockRoot();
            }
            assert checkInvariants(root);
            return false;
        }
	
	

 

 

相关标签: JDK