精华内容
下载资源
问答
  • } } 二、TreeMap实现原理 1、TreeMap的基本概念: TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap...

    一、红黑树介绍

    1、R-B Tree概念

    红黑树(Red Black Tree简称R-B Tree 是一种自平衡二叉查找树,它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

    红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。

    除了具备该特性之外,红黑树还包括许多额外的信息。

    2、红黑树5个特性

    (1) 每个节点或者是黑色,或者是红色。

    (2) 根节点是黑色。

    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]

    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。

    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    关于它的特性,需要注意的是:

    第一,特性(3)中的叶子节点,是只为空(NILnull)的节点。

    第二,特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

    要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

    3、红黑树的操作

    红黑树的基本操作是添加删除旋转。在对红黑树进行添加或删除后,会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
    旋转包括两种:左旋 右旋

    3.1 左旋

    左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

    TreeMap中左旋代码如下:

    //Rotate Left
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
    		//1.将B子树与x(p)链接
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            //2.将y(r)与x(p)的父树链接
            r.parent = p.parent;
            if (p.parent == null) //根节点
                root = r;
            else if (p.parent.left == p)  // x(p)原为左支树
                p.parent.left = r;
            else
                p.parent.right = r;     // x(p)原为左支树
            //3.将y(r)与x(p)链接
            r.left = p;
            p.parent = r;
        }
    }
    

    3.2 右旋

    右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

     

    TreeMap中右旋代码如下:

    //Rotate Right
    private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }
    

    二、TreeMap实现原理

    1、TreeMap的基本概念:

    TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。TreeMap继承AbstractMap,实现NavigableMapCloneableSerializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合, NavigableMap(更多)则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。实现SortedMap,支持遍历时按元素的大小有序遍历。

    该集合最重要的特点就是可排序,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator比较器进行排序,具体取决于使用的构造方法。

    根据上一条,我们要想使用TreeMap存储并排序我们自定义的类(如User类),那么必须自己定义比较机制:一种方式是User类去实现java.lang.Comparable接口,并实现其compareTo()方法。另一种方式是写一个类(如MyCompatator)去实现java.util.Comparator接口,并实现compare()方法,然后将MyCompatator类实例对象作为TreeMap的构造方法参数进行传参(当然也可以使用匿名内部类)。

    TreeMap核心源码的理解,实质上就是对“如何维持红黑树数据结构的特性的理解”。下面的解析,都会以红黑树特性为引子来深入剖析TreeMap源码。

    1、内部成员数据结构

    TreeMap中包含了如下几个重要的属性:

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    	//比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
            private final Comparator<? super K> comparator;
            //红-黑树根节点
            private transient Entry<K,V> root = null;
            //容器大小
            private transient int size = 0;
            //树结构被修改次数
            private transient int modCount = 0;
            //红黑树的节点颜色--红色
            private static final boolean RED = false;
            //红黑树的节点颜色--黑色
            private static final boolean BLACK = true;
            ...
    
    }
    

    TreeMap采用红黑树的数据结构来实现。树节点Entry实现了Map.Entry,采用内部类的方式实现

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key; 
        V value; 
        Entry<K,V> left; 
        Entry<K,V> right; 
        Entry<K,V> parent; 
        boolean color = BLACK; 
    
        // 其他省略 
    } 
    

    节点很简单,存储了父节点,左右子节点,以及红黑颜色,元素的key以及value信息,也就是三查。

    2、构造方法

    // 1,无参构造方法
    public TreeMap() {   
            comparator = null; // 默认比较机制(自然比较)
    }
    
    // 2,自定义比较器的构造方法
    public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
    }
    
    // 3,构造已知Map对象为TreeMap
    public TreeMap(Map<? extends K, ? extends V> m) {  
            comparator = null; // 默认比较机制
            putAll(m);
    }
    
    // 4,构造已知的SortedMap对象为TreeMap
    public TreeMap(SortedMap<K, ? extends V> m) { 
            comparator = m.comparator(); // 使用已知对象的构造器
            try {
                buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
    }
    

    3、get()方法

    get(Object key)方法根据指定的key值返回对应的value,该方法调用了getEntry(Object key)得到相应的entry,然后返回entry.value。因此getEntry()是方法的核心。方法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找,直到找到满足k.compareTo(p.key) == 0entry

    public V get(Object key) {//根据key值查找value
    
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
    }
    
    //根据key值查找元素方法;final方法不允许被子类重写  
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance        
        if (comparator != null)//存在比较器,按比较器进行比较查找            
            return getEntryUsingComparator(key);        
        if (key == null)//key值为null抛空指针异常            
            throw new NullPointerException();
        
        //没有比较强,自然排序比较        
        Comparable<? super K> k = (Comparable<? super K>) key;        
        Entry<K,V> p = root;        
        while (p != null) {
            //从root开始循环查找,一直到叶子节点            
            int cmp = k.compareTo(p.key); //采用key的compareTo方法进行比较            
            if (cmp < 0) //小于继续查找左边                
                p = p.left;            
            else if (cmp > 0) //大于继续查找右边                
                p = p.right;            
            else                
                return p;//等于返回当前元素        
        }        
        return null;    
    }
    

    前面只是集合通用的简单知识,下面才是重点,了解红黑树增加、删除节点的核心算法


    4、put方法

    红黑树在新增节点过程中比较复杂,一般经历三个步骤。第一步: 将红黑树当作一颗二叉查找树,将节点插入。第二步:将插入的节点着色为"红色"。第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。下面会以红黑树特性为基础解析put方法源码,以帮助理解代码的设计。

    4.1 红黑树增加节点的特性

    对于新节点的插入有如下四个关键地方:

    1、插入新节点会对map做一次查找。

    2、插入新节点总是红色节点 。      

    3、如果插入节点的父节点是黑色, 能维持性质 。      

    4、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。      

    红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。

    为什么着色成红色,而不是黑色呢?将插入的节点着色为红色,不会违背"特性(5)"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。

    第二步中,将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?

    对于"特性(1)",显然不会违背了。因为我们已经将它涂成红色了。

    对于"特性(2)",显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。

    对于"特性(3)",显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。

    对于"特性(4)",是有可能违背的!

    那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。

    这里将红黑树的五点规定再贴一遍:

    (1)每个节点都只能是红色或者黑色

    (2)根节点是黑色

    (3)每个叶节点(NIL节点,空节点)是黑色的。

    (4)如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

    (5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    4.2 红黑树增加节点的情况

    假设我们这里有一棵最简单的树,我们规定新增的节点为新、它的父节点为父、父的兄弟节点为叔、父的父节点为祖父。

    1)情况1:无父

    若新插入的节点N没有父节点,则直接当做根据节点插入即可,同时将颜色设置为黑色。

    2)情况2 :黑父

    插入节点后可维持红黑树性质。红黑树插入的新节点肯定为原来的某支的末尾,时颜色为红色,由于根据规则四它会存在两个黑色的叶子节点,值为null,满足规则3和4。同时新增节点为红色,所以通过它的子节点的路径依然会保存着相同的黑色节点数,同样满足规则5。

    3)情况3 红父、红叔

    插入节点后不能维持红黑树性质4,故可能需要进行着色或旋转操作。

    下面假设父亲为左节点进行分析(右节点的情况类似,只是旋转方向相反)。

    根据红黑树的性质5可推得,红叔肯定没有孩子,因为既然可以插入,那父原本也没孩子。插入新节点只破坏了颜色的性质,所以将父、叔节点变黑、祖节点变红。这时由于经过节点父、叔的路径都必须经过G所以在这些路径上面的黑节点数目还是相同的。但是经过上面的处理,可能G节点的父节点也是红色,这个时候我们需要将G节点当做新增节点迭代处理。也就是:进行重新着色再按祖向上继续判断即可。

    4)情况4:红父、黑叔(Null)或缺失、插入左节点

    由于红父没有孩子,根据红黑树的性质5可推得,该情况的黑叔实际只可能为空的NIL节点。插入新节点不仅破坏了颜色的性质,还破坏了平衡,故需要进行重新着色和旋转。此时新节点的左右位置影响具体的旋转方式。

    插入左节点这种情况有可能是由于情况五而产生的,也有可能不是。对于这种情况它违反了规则4,所以我们先将父P、组G节点的颜色进行交换,但这样并不平衡,违反了规则5(黑色节点数相同),所以还需要以祖G节点为中心进行右旋转,在旋转后产生的树中,节点父P是新节点N、祖G的父节点,这样就满足开始时所有的路径经过祖G节点到他们叶子的黑色节点数一样,满足规范5,同时由于颜色相同,也不用再向上迭代。即重新着色并按祖右旋

    5)情况4:红父、黑叔(Null)或缺失、插入右节点

    对于插入位置为右节点这种情况,我们对新增节点N、父节点P进行一次左旋转。这里所产生的结果其实并没有完成,还不是平衡的(违反了规则四),这是我们需要进行情况4的操作。即按父左旋,并指向父继续判断(即接着按情况3处理)

    4.3 put方法源码解析

    put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于getEntry()方法;如果没有找到则会在红黑树中插入新的entry,如果插入之后破坏了红黑树的约束,还需要进行调整(旋转,改变某些节点的颜色)。put算法时间复杂度约为O(log2N),并且其与普通查找二叉树比较,插入的旋转次数很少。

    注意看注释

    public V put(K key, V value) {
        //用t表示二叉树的查找入口,即根节点
        Entry<K,V> t = root;
        //t为null表示一个空树,即TreeMap中没有任何元素,直接插入
        if (t == null) {
            //检查key的类型
      	compare(key, key); // type (and possibly null) check
      	//将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root
     	root = new Entry<>(key, value, null);
      	size = 1;
      	//修改次数 + 1
      	modCount++;
     	return null;
        }
        int cmp; //cmp表示key排序的返回结果
        Entry<K,V> parent; //父节点
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator; //指定的排序算法
        //如果cpr不为空,则采用既定的排序算法进行创建TreeMap集合
        if (cpr != null) {
            do {
      	    parent = t; //parent指向上次循环后的t
      	    //比较新增节点的key和当前节点key的大小
      	    cmp = cpr.compare(key, t.key);
      	    //新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
      	    if (cmp < 0)
      	        t = t.left;
      		//新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
     	    else if (cmp > 0)
     		t = t.right;
     		//两个key值相等,则新值覆盖旧值,并返回新值
      	    else
      		return t.setValue(value);
     	} while (t != null);
        }
        //如果cpr为空,则采用默认的排序算法进行创建TreeMap集合
        else {
            if (key == null) //key值为空抛出异常
      	    throw new NullPointerException();
     	    /* 下面处理过程和上面一样 */
      	    Comparable<? super K> k = (Comparable<? super K>) key;
      	    do {
     	        parent = t;
      		cmp = k.compareTo(t.key);
      		if (cmp < 0)
      		    t = t.left;
      		else if (cmp > 0)
      		    t = t.right;
      		else
      		    return t.setValue(value);
      	    } while (t != null);
      	}
      	//将新增节点当做parent的子节点
      	Entry<K,V> e = new Entry<>(key, value, parent);
     	//如果新增节点的key小于parent的key,则当做左子节点
      	if (cmp < 0)
      		parent.left = e;
      	//如果新增节点的key大于parent的key,则当做右子节点
      	else
      		parent.right = e;
      	/*
     	*上面已经完成了排序二叉树的的构建,将新增节点插入该树中的合适位置
            *下面fixAfterInsertion()方法就是对这棵树进行调整、平衡,具体过程参考上面的4种情况
            */
            fixAfterInsertion(e);
      	//TreeMap元素数量 + 1
            size++;
            //TreeMap容器修改次数 + 1
            modCount++;
            return null;
        }
    }
    
       

    fixAfterInsertion(e),调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下:

    /**
    * 新增节点后的修复操作
    * x 表示新增节点
    */
    private void fixAfterInsertion(Entry<K,V> x) {
       x.color = RED; //新增节点的颜色为红色
       //循环直到x不是根节点,且x的父节点不为红色
       while (x != null && x != root && x.parent.color == RED) {
       	//如果X的父节点(P)是其父节点的父节点(G)的左节点
       	if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        		//获取X的叔节点(U)
      	 	Entry<K,V> y = rightOf(parentOf(parentOf(x)));
      	 	//如果X的叔节点(U) 为红色(情况三)
       		if (colorOf(y) == RED) { 
       			//将X的父节点(P)设置为黑色
       			setColor(parentOf(x), BLACK);
       			//将X的叔节点(U)设置为黑色
       			setColor(y, BLACK);
       			//将X的父节点的父节点(G)设置红色
       			setColor(parentOf(parentOf(x)), RED);
        			x = parentOf(parentOf(x));
       		}
      	        //如果X的叔节点(U为黑色);这里会存在两种情况(情况四、情况五)
       	        else { 
        		//如果X节点为其父节点(P)的右子树,则进行左旋转(情况四)
        		    if (x == rightOf(parentOf(x))) {
       			//将X的父节点作为X
      			x = parentOf(x);
       			//右旋转
       			rotateLeft(x);
       		    }
       		    //(情况五)
       		    //将X的父节点(P)设置为黑色
       		    setColor(parentOf(x), BLACK);
      	 	    //将X的父节点的父节点(G)设置红色
       		    setColor(parentOf(parentOf(x)), RED);
        		    //以X的父节点的父节点(G)为中心右旋转
       		    rotateRight(parentOf(parentOf(x)));
       	        }
           }
           //如果X的父节点(P)是其父节点的父节点(G)的右节点
           else {
       	    //获取X的叔节点(U)
        	    Entry<K,V> y = leftOf(parentOf(parentOf(x)));
        	    //如果X的叔节点(U) 为红色(情况三)
       	    if (colorOf(y) == RED) {
       		//将X的父节点(P)设置为黑色
       		setColor(parentOf(x), BLACK);
       		//将X的叔节点(U)设置为黑色
       		setColor(y, BLACK);
       		//将X的父节点的父节点(G)设置红色
       		setColor(parentOf(parentOf(x)), RED);
       		x = parentOf(parentOf(x));
       	     }
       	    //如果X的叔节点(U为黑色);这里会存在两种情况(情况四、情况五)
      	    else {
       		//如果X节点为其父节点(P)的右子树,则进行左旋转(情况四)
       		if (x == leftOf(parentOf(x))) {
       			//将X的父节点作为X
       			x = parentOf(x);
       			//右旋转
        			rotateRight(x);
       		}
       		//(情况五)
       		//将X的父节点(P)设置为黑色
       		setColor(parentOf(x), BLACK);
       		//将X的父节点的父节点(G)设置红色
       		setColor(parentOf(parentOf(x)), RED);
      	 		//以X的父节点的父节点(G)为中心右旋转
       		rotateLeft(parentOf(parentOf(x)));
       	    }
           }
       }
       //将根节点G强制设置为黑色
       root.color = BLACK;
    }
    

    5、remove()方法

    对于红黑树的增加节点而言,删除显得更加复杂,使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样,同样是找到删除的节点,删除之后调整红黑树。

    5.1 红黑树删除节点的特性

    真正删除的节点并不一定是指定的节点,当其有两个孩子时,会查找下一个节点作为真正的删除点,这里先称为后继节点,由迭代循环方法可知,该节点一定是没有孩子或只有一个孩子。

    ①该节点如果为红色,必然为叶子节点

    ②该节点如果为黑色,只可能有一个红色孩子或无孩子

    这是因为删除节点并不是直接删除,而是被其后继(树种比大于D的最小的那个元素)替代。这是通过走了“弯路”的方式来删除的:找到被删除的节点D的子节点F,用F来替代D,不是直接删除D,因为D被F替代了,直接删除F即可,若F还有子节点就迭代。所以这里就将删除父节点D的事情转变为了删除子节点F的事情,这样处理就将复杂的删除事件简单化了。子节点F的规则是:右分支最左支树,或者 左分支最右边祖树。

    那被删除节点有没有后继节点就会出现不同的删除方式:

    ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。

    ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。

    ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子” (如下图)。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    并且,该节点如果为红色,必然为叶子节点,即无儿子,因为如果该节点的子节点为黑,则必然存在令一个子节点(两个儿子不符合迭代查询的结果),否则违反黑节点数原则(规定5),为红,则违反“颜色”原则(规定4)。上下图对比理解。

    红-黑二叉树删除节点,最大的麻烦是要保持各分支黑色节点数目相等。 因为是删除,所以不用担心存在颜色冲突问题(值的替换)——插入才会引起颜色冲突。

    5.2 红黑树删除节点的情况

    红黑树删除节点同样会分成几种情况,这里是按照待删除节点有几个儿子的情况来进行分类:

    1)情况1:无子节点(红色节点)

    这种情况对该节点直接删除即可,不会影响树的结构。因为该节点为叶子节点它不可能存在子节点-----如子节点为黑,则违反黑节点数原则(规定5),为红,则违反“颜色”原则(规定4)。

    2)情况2:有一个子节点

    这种情况处理也是非常简单的,用子节点替代待删除节点,然后删除子节点即可。

    3)情况3:有两个子节点

    这种情况可能会稍微有点儿复杂。它需要找到一个后继节点N来替代本来该被删除的节点(覆盖值),然后真正删除N(N的删除方法上面已讲到),再完善红黑树的约束,这就牵扯到N的父与兄了。它主要分为四种情况。

    • N的兄弟节点W为红色
    • N的兄弟w是黑色的,且w的俩个孩子都是黑色的。
    • N的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。
    • N的兄弟w是黑色的,且w的右孩子是红色的。

    4)情况3.1:N的兄弟节点W为红色

    此情况红兄必然有两个孩子,删除后同时影响平衡及颜色性质,故需要重新着色及旋转操作。策略改变兄节点W、父节点P的颜色,然后进行一次左旋转。这样处理就可以使得红黑性质得以继续保持。N的新兄弟是旋转之前w的某个孩子,为黑色。这样处理后将情况3.1、转变为3.2、3.3、3.4中的一种。如下:

    5)情况3.2:N的兄弟节点w是黑色的,且w只有一个右孩子

    该情况需要重新着色及旋转

    6)情况3.3:N的兄弟节点w是黑色的,且w只有一个左孩子

    该情况需要重新着色,然后以兄为中心右旋转得出3.2的情况

    5.3 remove()方法源码分析

    remove(Object key)的作用是删除key值对应的entry,该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry,然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束条件,因此有可能要进行调整。

    public V remove(Object key) {
       Entry<K,V> p = getEntry(key);//先找到需要删除的元素
       if (p == null)
       	return null;
       V oldValue = p.value;
       deleteEntry(p);
       return oldValue;
    }

    这里重点放deleteEntry()上,该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整。

    private void deleteEntry(Entry<K,V> p) {

      modCount++; //修改次数 +1

      size--; //元素个数 -1

      /*

      * 被删除节点的左子树和右子树都不为空,那么就用 p节点的中序后继节点代替 p 节点

      * successor(P)方法为寻找P的替代节点。规则是右分支最左边,或者 左分支最右边的节点

      * ---------------------(1)

      */

      if (p.left != null && p.right != null) {

             Entry<K,V> s = successor(p);

                  //仅仅是Key-Value键值对的替换

             p.key = s.key;

             p.value = s.value;
                         //p指向后继节点,后续都是对后继节点s进行操作

             p = s;

      }

     

      //先删除后继节点,replacement为替代节点(后继节点孩子),如果P的左子树存在那么就用左子树替代,否则用右子树替代

      Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        /*

      * 删除节点,分为上面提到的三种情况

      * -----------------------(2)

      */

      //如果替代节点不为空

      if (replacement != null) {

             replacement.parent = p.parent;

             /*

             *replacement来替代P节点

             */

             //若P没有父节点,则跟节点直接变成replacement

             if (p.parent == null)

                    root = replacement;

             //如果P为左节点,则用replacement来替代为左节点

             else if (p == p.parent.left)

                    p.parent.left = replacement;

             //如果P为右节点,则用replacement来替代为右节点

             else

                    p.parent.right = replacement;

        //同时将P节点从这棵树中剔除掉

             p.left = p.right = p.parent = null;

        /*

             * 若P为红色直接删除,红黑树保持平衡

             * 但是若P为黑色,则需要调整红黑树使其保持平衡

              */

             if (p.color == BLACK)

             fixAfterDeletion(replacement);

    } else if (p.parent == null) { //p没有父节点,表示为P根节点,直接删除即可

             root = null;

    } else { //P节点不存在子节点,直接删除即可

             if (p.color == BLACK) //如果P节点的颜色为黑色,对红黑树进行调整

                    fixAfterDeletion(p);

        //删除P节点

             if (p.parent != null) {

                    if (p == p.parent.left)

                    p.parent.left = null;

                    else if (p == p.parent.right)

                    p.parent.right = null;

                    p.parent = null;

             }

      }

    }

    (2)处是删除该节点过程。它主要分为上面提到的三种情况,它与上面的if…else if… else一一对应 。如下:      

    1、有两个儿子。这种情况比较复杂,但还是比较简单。上面提到过用子节点C替代代替待删除节点D,然后删除子节点C即可。      

    2、没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。      

    3、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。

    删除完节点后,就要根据情况来对红黑树进行复杂的调整:fixAfterDeletion()。

    private void fixAfterDeletion(Entry<K,V> x) {

      // 删除节点需要一直迭代,直到 x 不是根节点,且 x 的颜色是黑色

      while (x != root && colorOf(x) == BLACK) {

             if (x == leftOf(parentOf(x))) { //若X节点为左节点

                    //获取其兄弟节点

                    Entry<K,V> sib = rightOf(parentOf(x));

               /*

                    * 如果兄弟节点为红色----(情况3.1)

                    * 策略:改变W、P的颜色,然后进行一次左旋转

                    */

                    if (colorOf(sib) == RED) {

                           setColor(sib, BLACK);

                           setColor(parentOf(x), RED);

                           rotateLeft(parentOf(x));

                           sib = rightOf(parentOf(x));

                    }

               /*

                    * 若兄弟节点的两个子节点都为黑色----(情况3.4)

                    * 策略:将兄弟节点变成红色

                    */

                    if (colorOf(leftOf(sib)) == BLACK &&

                           colorOf(rightOf(sib)) == BLACK) {

                           setColor(sib, RED);

                           x = parentOf(x);

                    }

                    else {

                           /*

                           * 如果兄弟节点只有右子树为黑色----(情况3.2)

                           * 策略:将兄弟节点与其左子树进行颜色互换然后进行右转

                           * 这时情况会转变为3.3

                           */

                           if (colorOf(rightOf(sib)) == BLACK) {

                                  setColor(leftOf(sib), BLACK);

                                  setColor(sib, RED);

                                  rotateRight(sib);

                                  sib = rightOf(parentOf(x));

                           }

                           /*

                           *----情况3.3

                           *策略:交换兄弟节点和父节点的颜色,

                           *同时将兄弟节点右子树设置为黑色,最后左旋转

                           */

                           setColor(sib, colorOf(parentOf(x)));

                           setColor(parentOf(x), BLACK);

                           setColor(rightOf(sib), BLACK);

                           rotateLeft(parentOf(x));

                            x = root;

                    }

             }

        /**

             * X节点为右节点与其为做节点处理过程差不多,这里就不在累述了

             */

             else {

                    Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {

                       setColor(sib, BLACK);

                       setColor(parentOf(x), RED);

                        rotateRight(parentOf(x));

                        sib = leftOf(parentOf(x));

                   }

               if (colorOf(rightOf(sib)) == BLACK &&

        colorOf(leftOf(sib)) == BLACK) {

                         setColor(sib, RED);

                         x = parentOf(x);

                   } else {

                        if (colorOf(leftOf(sib)) == BLACK) {

                        setColor(rightOf(sib), BLACK);

                        setColor(sib, RED);

                        rotateLeft(sib);

                        sib = leftOf(parentOf(x));

                        }

                       setColor(sib, colorOf(parentOf(x)));

                       setColor(parentOf(x), BLACK);

                       setColor(leftOf(sib), BLACK);

                       rotateRight(parentOf(x));

                       x = root;

                  }

               }

           }

        setColor(x, BLACK);

      }

    展开全文
  • TreeMap底层机制

    2021-09-14 09:44:59
    package aggregate.map; import java.util.Comparator; import java.util.TreeMap; public class TreeMap_ { ... TreeMap treeMap = new TreeMap(new Comparator() { @Override public int compa

    TreeMap

    • 构造器把传入的实现了Comparator接口的匿名内部类(对象),传给TreeMap的comparator属性,可以借助匿名内部类重写compare方法,以定义排序方式
    • 如果遍历过程中发现准备添加key和已有key相等,就不添加key,但会替换value
    package aggregate.map;
    
    import java.util.Comparator;
    import java.util.TreeMap;
    
    public class TreeMap_ {
        public static void main(String[] args) {
            TreeMap treeMap = new TreeMap(new Comparator() {
                @Override
                public int compare(Object o1, Object o2) {
                    return ((String) o1).compareTo((String) o2);
                }
            });
    
            treeMap.put("mary","玛丽");
            treeMap.put("jack","杰克");
            treeMap.put("tom","汤姆");
            treeMap.put("mary","玛丽");
    
            System.out.println(treeMap);
    
            /*
                1.构造器,把传入的实现了Comparator接口的匿名内部类(对象),传给TreeMap的comparator属性
                    public TreeMap(Comparator<? super K> comparator) {
                            this.comparator = comparator;
                        }
                2.调用put方法
                2.1 第一次添加,将k-v封装到Entry对象,放入root
                    Entry<K,V> t = root;
                if (t == null) {
                    compare(key, key); // type (and possibly null) check
    
                    root = new Entry<>(key, value, null);
                    size = 1;
                    modCount++;
                    return null;
                }
                2.2 之后添加元素,遍历所有元素,并进行比对
                    Comparator<? super K> cpr = comparator;
                if (cpr != null) {
                    do {    //遍历所有的key
                        parent = t;
                        cmp = cpr.compare(key, t.key);      //动态绑定到我们的匿名内部类compare
                        if (cmp < 0)
                            t = t.left;
                        else if (cmp > 0)
                            t = t.right;
                        else        //如果遍历过程中发现准备添加key和已有key相等,就不添加key,但会替换value
                            return t.setValue(value);
                    } while (t != null);
                }
             */
        }
    }
    
    展开全文
  • treeMap原理及其实现

    千次阅读 2017-11-07 14:08:48
    TreeMap是一个有序的key-value集合,他是...TreeMap实现了navigableMap接口,意味着它支持一系列的导航方法,返回有序的key集合。 TreeMap实现了cloneable接口,意味着它能被克隆。 TreeMap实现了java.io.serializab

    TreeMap是一个有序的key-value集合,他是通过红黑树实现的。
    TreeMap继承于AbstractMap,所以它是一个Map,即一个key-value集合。
    TreeMap实现了navigableMap接口,意味着它支持一系列的导航方法,返回有序的key集合。
    TreeMap实现了cloneable接口,意味着它能被克隆。
    TreeMap实现了java.io.serializable接口,意味着它支持系列化。

    treeMap基于红黑树(Red-Black tree)实现,该映射根据其键的自然顺序进行排序,或者根据映射时提供的comparator进行排序,取决于他的构造方法。TreeMap的基本操作containsKey,get,put和remove的时间复杂度是log(n)

    TreeMap的构造方法

    // 默认构造函数。使用该构造函数,TreeMap中的元素按照自然排序进行排列。
    TreeMap()
    // 创建的TreeMap包含Map
    TreeMap(Map<? extends K, ? extends V> copyFrom)
    // 指定Tree的比较器
    TreeMap(Comparator<? super K> comparator)
    // 创建的TreeSet包含copyFrom
    TreeMap(SortedMap<K, ? extends V> copyFrom)

    TreeMap的数据结构

    public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable

    这里写图片描述

    TreeMap的源码实现

    package java.util;
    
    public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
    
        // 比较器。用来给TreeMap排序
        private final Comparator<? super K> comparator;
    
        // TreeMap是红黑树实现的,root是红黑书的根节点
        private transient Entry<K,V> root = null;
    
        // 红黑树的节点总数
        private transient int size = 0;
    
        // 记录红黑树的修改次数
        private transient int modCount = 0;
    
        // 默认构造函数
        public TreeMap() {
            comparator = null;
        }
    
        // 带比较器的构造函数
        public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }
    
        // 带Map的构造函数,Map会成为TreeMap的子集
        public TreeMap(Map<? extends K, ? extends V> m) {
            comparator = null;
            putAll(m);
        }
    
        // 带SortedMap的构造函数,SortedMap会成为TreeMap的子集
        public TreeMap(SortedMap<K, ? extends V> m) {
            comparator = m.comparator();
            try {
                buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
        }
    
        public int size() {
            return size;
        }
    
        // 返回TreeMap中是否保护“键(key)”
        public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        // 返回TreeMap中是否保护"值(value)"
        public boolean containsValue(Object value) {
            // getFirstEntry() 是返回红黑树的第一个节点
            // successor(e) 是获取节点e的后继节点
            for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
                if (valEquals(value, e.value))
                    return true;
            return false;
        }
    
        // 获取“键(key)”对应的“值(value)”
        public V get(Object key) {
            // 获取“键”为key的节点(p)
            Entry<K,V> p = getEntry(key);
            // 若节点(p)为null,返回null;否则,返回节点对应的值
            return (p==null ? null : p.value);
        }
    
        public Comparator<? super K> comparator() {
            return comparator;
        }
    
        // 获取第一个节点对应的key
        public K firstKey() {
            return key(getFirstEntry());
        }
    
        // 获取最后一个节点对应的key
        public K lastKey() {
            return key(getLastEntry());
        }
    
        // 将map中的全部节点添加到TreeMap中
        public void putAll(Map<? extends K, ? extends V> map) {
            // 获取map的大小
            int mapSize = map.size();
            // 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
            if (size==0 && mapSize!=0 && map instanceof SortedMap) {
                Comparator c = ((SortedMap)map).comparator();
                // 如果TreeMap和map的比较器相等;
                // 则将map的元素全部拷贝到TreeMap中,然后返回!
                if (c == comparator || (c != null && c.equals(comparator))) {
                    ++modCount;
                    try {
                        buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                    } catch (java.io.IOException cannotHappen) {
                    } catch (ClassNotFoundException cannotHappen) {
                    }
                    return;
                }
            }
            // 调用AbstractMap中的putAll();
            // AbstractMap中的putAll()又会调用到TreeMap的put()
            super.putAll(map);
        }
    
        // 获取TreeMap中“键”为key的节点
        final Entry<K,V> getEntry(Object key) {
            // 若“比较器”为null,则通过getEntryUsingComparator()获取“键”为key的节点
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            // 将p设为根节点
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = k.compareTo(p.key);
                // 若“p的key” < key,则p=“p的左孩子”
                if (cmp < 0)
                    p = p.left;
                // 若“p的key” > key,则p=“p的左孩子”
                else if (cmp > 0)
                    p = p.right;
                // 若“p的key” = key,则返回节点p
                else
                    return p;
            }
            return null;
        }
    
        // 获取TreeMap中“键”为key的节点(对应TreeMap的比较器不是null的情况)
        final Entry<K,V> getEntryUsingComparator(Object key) {
            K k = (K) key;
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
                // 将p设为根节点
                Entry<K,V> p = root;
                while (p != null) {
                    int cmp = cpr.compare(k, p.key);
                    // 若“p的key” < key,则p=“p的左孩子”
                    if (cmp < 0)
                        p = p.left;
                    // 若“p的key” > key,则p=“p的左孩子”
                    else if (cmp > 0)
                        p = p.right;
                    // 若“p的key” = key,则返回节点p
                    else
                        return p;
                }
            }
            return null;
        }
    
        // 获取TreeMap中不小于key的最小的节点;
        // 若不存在(即TreeMap中所有节点的键都比key大),就返回null
        final Entry<K,V> getCeilingEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                // 情况一:若“p的key” > key。
                // 若 p 存在左孩子,则设 p=“p的左孩子”;
                // 否则,返回p
                if (cmp < 0) {
                    if (p.left != null)
                        p = p.left;
                    else
                        return p;
                // 情况二:若“p的key” < key。
                } else if (cmp > 0) {
                    // 若 p 存在右孩子,则设 p=“p的右孩子”
                    if (p.right != null) {
                        p = p.right;
                    } else {
                        // 若 p 不存在右孩子,则找出 p 的后继节点,并返回
                        // 注意:这里返回的 “p的后继节点”有2种可能性:第一,null;第二,TreeMap中大于key的最小的节点。
                        //   理解这一点的核心是,getCeilingEntry是从root开始遍历的。
                        //   若getCeilingEntry能走到这一步,那么,它之前“已经遍历过的节点的key”都 > key。
                        //   能理解上面所说的,那么就很容易明白,为什么“p的后继节点”又2种可能性了。
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.right) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                // 情况三:若“p的key” = key。
                } else
                    return p;
            }
            return null;
        }
    
        // 获取TreeMap中不大于key的最大的节点;
        // 若不存在(即TreeMap中所有节点的键都比key小),就返回null
        // getFloorEntry的原理和getCeilingEntry类似,这里不再多说。
        final Entry<K,V> getFloorEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp > 0) {
                    if (p.right != null)
                        p = p.right;
                    else
                        return p;
                } else if (cmp < 0) {
                    if (p.left != null) {
                        p = p.left;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.left) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                } else
                    return p;
    
            }
            return null;
        }
    
        // 获取TreeMap中大于key的最小的节点。
        // 若不存在,就返回null。
        //   请参照getCeilingEntry来对getHigherEntry进行理解。
        final Entry<K,V> getHigherEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp < 0) {
                    if (p.left != null)
                        p = p.left;
                    else
                        return p;
                } else {
                    if (p.right != null) {
                        p = p.right;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.right) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                }
            }
            return null;
        }
    
        // 获取TreeMap中小于key的最大的节点。
        // 若不存在,就返回null。
        //   请参照getCeilingEntry来对getLowerEntry进行理解。
        final Entry<K,V> getLowerEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp > 0) {
                    if (p.right != null)
                        p = p.right;
                    else
                        return p;
                } else {
                    if (p.left != null) {
                        p = p.left;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.left) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                }
            }
            return null;
        }
    
        // 将“key, value”添加到TreeMap中
        // 理解TreeMap的前提是掌握“红黑树”。
        // 若理解“红黑树中添加节点”的算法,则很容易理解put。
        public V put(K key, V value) {
            Entry<K,V> t = root;
            // 若红黑树为空,则插入根节点
            if (t == null) {
            // TBD:
            // 5045147: (coll) Adding null to an empty TreeSet should
            // throw NullPointerException
            //
            // compare(key, key); // type check
                root = new Entry<K,V>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            // split comparator and comparable paths
            Comparator<? super K> cpr = comparator;
            // 在二叉树(红黑树是特殊的二叉树)中,找到(key, value)的插入位置。
            // 红黑树是以key来进行排序的,所以这里以key来进行查找。
            if (cpr != null) {
                do {
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            else {
                if (key == null)
                    throw new NullPointerException();
                Comparable<? super K> k = (Comparable<? super K>) key;
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            // 新建红黑树的节点(e)
            Entry<K,V> e = new Entry<K,V>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            // 红黑树插入节点后,不再是一颗红黑树;
            // 这里通过fixAfterInsertion的处理,来恢复红黑树的特性。
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }
    
        // 删除TreeMap中的键为key的节点,并返回节点的值
        public V remove(Object key) {
            // 找到键为key的节点
            Entry<K,V> p = getEntry(key);
            if (p == null)
                return null;
    
            // 保存节点的值
            V oldValue = p.value;
            // 删除节点
            deleteEntry(p);
            return oldValue;
        }
    
        // 清空红黑树
        public void clear() {
            modCount++;
            size = 0;
            root = null;
        }
    
        // 克隆一个TreeMap,并返回Object对象
        public Object clone() {
            TreeMap<K,V> clone = null;
            try {
                clone = (TreeMap<K,V>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            // Put clone into "virgin" state (except for comparator)
            clone.root = null;
            clone.size = 0;
            clone.modCount = 0;
            clone.entrySet = null;
            clone.navigableKeySet = null;
            clone.descendingMap = null;
    
            // Initialize clone with our mappings
            try {
                clone.buildFromSorted(size, entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
    
            return clone;
        }
    
        // 获取第一个节点(对外接口)。
        public Map.Entry<K,V> firstEntry() {
            return exportEntry(getFirstEntry());
        }
    
        // 获取最后一个节点(对外接口)。
        public Map.Entry<K,V> lastEntry() {
            return exportEntry(getLastEntry());
        }
    
        // 获取第一个节点,并将改节点从TreeMap中删除。
        public Map.Entry<K,V> pollFirstEntry() {
            // 获取第一个节点
            Entry<K,V> p = getFirstEntry();
            Map.Entry<K,V> result = exportEntry(p);
            // 删除第一个节点
            if (p != null)
                deleteEntry(p);
            return result;
        }
    
        // 获取最后一个节点,并将改节点从TreeMap中删除。
        public Map.Entry<K,V> pollLastEntry() {
            // 获取最后一个节点
            Entry<K,V> p = getLastEntry();
            Map.Entry<K,V> result = exportEntry(p);
            // 删除最后一个节点
            if (p != null)
                deleteEntry(p);
            return result;
        }
    
        // 返回小于key的最大的键值对,没有的话返回null
        public Map.Entry<K,V> lowerEntry(K key) {
            return exportEntry(getLowerEntry(key));
        }
    
        // 返回小于key的最大的键值对所对应的KEY,没有的话返回null
        public K lowerKey(K key) {
            return keyOrNull(getLowerEntry(key));
        }
    
        // 返回不大于key的最大的键值对,没有的话返回null
        public Map.Entry<K,V> floorEntry(K key) {
            return exportEntry(getFloorEntry(key));
        }
    
        // 返回不大于key的最大的键值对所对应的KEY,没有的话返回null
        public K floorKey(K key) {
            return keyOrNull(getFloorEntry(key));
        }
    
        // 返回不小于key的最小的键值对,没有的话返回null
        public Map.Entry<K,V> ceilingEntry(K key) {
            return exportEntry(getCeilingEntry(key));
        }
    
        // 返回不小于key的最小的键值对所对应的KEY,没有的话返回null
        public K ceilingKey(K key) {
            return keyOrNull(getCeilingEntry(key));
        }
    
        // 返回大于key的最小的键值对,没有的话返回null
        public Map.Entry<K,V> higherEntry(K key) {
            return exportEntry(getHigherEntry(key));
        }
    
        // 返回大于key的最小的键值对所对应的KEY,没有的话返回null
        public K higherKey(K key) {
            return keyOrNull(getHigherEntry(key));
        }
    
        // TreeMap的红黑树节点对应的集合
        private transient EntrySet entrySet = null;
        // KeySet为KeySet导航类
        private transient KeySet<K> navigableKeySet = null;
        // descendingMap为键值对的倒序“映射”
        private transient NavigableMap<K,V> descendingMap = null;
    
        // 返回TreeMap的“键的集合”
        public Set<K> keySet() {
            return navigableKeySet();
        }
    
        // 获取“可导航”的Key的集合
        // 实际上是返回KeySet类的对象。
        public NavigableSet<K> navigableKeySet() {
            KeySet<K> nks = navigableKeySet;
            return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
        }
    
        // 返回“TreeMap的值对应的集合”
        public Collection<V> values() {
            Collection<V> vs = values;
            return (vs != null) ? vs : (values = new Values());
        }
    
        // 获取TreeMap的Entry的集合,实际上是返回EntrySet类的对象。
        public Set<Map.Entry<K,V>> entrySet() {
            EntrySet es = entrySet;
            return (es != null) ? es : (entrySet = new EntrySet());
        }
    
        // 获取TreeMap的降序Map
        // 实际上是返回DescendingSubMap类的对象
        public NavigableMap<K, V> descendingMap() {
            NavigableMap<K, V> km = descendingMap;
            return (km != null) ? km :
                (descendingMap = new DescendingSubMap(this,
                                                      true, null, true,
                                                      true, null, true));
        }
    
        // 获取TreeMap的子Map
        // 范围是从fromKey 到 toKey;fromInclusive是是否包含fromKey的标记,toInclusive是是否包含toKey的标记
        public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                        K toKey,   boolean toInclusive) {
            return new AscendingSubMap(this,
                                       false, fromKey, fromInclusive,
                                       false, toKey,   toInclusive);
        }
    
        // 获取“Map的头部”
        // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
        public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
            return new AscendingSubMap(this,
                                       true,  null,  true,
                                       false, toKey, inclusive);
        }
    
        // 获取“Map的尾部”。
        // 范围是从 fromKey 到 最后一个节点,inclusive是是否包含fromKey的标记
        public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
            return new AscendingSubMap(this,
                                       false, fromKey, inclusive,
                                       true,  null,    true);
        }
    
        // 获取“子Map”。
        // 范围是从fromKey(包括) 到 toKey(不包括)
        public SortedMap<K,V> subMap(K fromKey, K toKey) {
            return subMap(fromKey, true, toKey, false);
        }
    
        // 获取“Map的头部”。
        // 范围从第一个节点 到 toKey(不包括)
        public SortedMap<K,V> headMap(K toKey) {
            return headMap(toKey, false);
        }
    
        // 获取“Map的尾部”。
        // 范围是从 fromKey(包括) 到 最后一个节点
        public SortedMap<K,V> tailMap(K fromKey) {
            return tailMap(fromKey, true);
        }
    
        // ”TreeMap的值的集合“对应的类,它集成于AbstractCollection
        class Values extends AbstractCollection<V> {
            // 返回迭代器
            public Iterator<V> iterator() {
                return new ValueIterator(getFirstEntry());
            }
    
            // 返回个数
            public int size() {
                return TreeMap.this.size();
            }
    
            // "TreeMap的值的集合"中是否包含"对象o"
            public boolean contains(Object o) {
                return TreeMap.this.containsValue(o);
            }
    
            // 删除"TreeMap的值的集合"中的"对象o"
            public boolean remove(Object o) {
                for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
                    if (valEquals(e.getValue(), o)) {
                        deleteEntry(e);
                        return true;
                    }
                }
                return false;
            }
    
            // 清空删除"TreeMap的值的集合"
            public void clear() {
                TreeMap.this.clear();
            }
        }
    
        // EntrySet是“TreeMap的所有键值对组成的集合”,
        // EntrySet集合的单位是单个“键值对”。
        class EntrySet extends AbstractSet<Map.Entry<K,V>> {
            public Iterator<Map.Entry<K,V>> iterator() {
                return new EntryIterator(getFirstEntry());
            }
    
            // EntrySet中是否包含“键值对Object”
            public boolean contains(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                V value = entry.getValue();
                Entry<K,V> p = getEntry(entry.getKey());
                return p != null && valEquals(p.getValue(), value);
            }
    
            // 删除EntrySet中的“键值对Object”
            public boolean remove(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                V value = entry.getValue();
                Entry<K,V> p = getEntry(entry.getKey());
                if (p != null && valEquals(p.getValue(), value)) {
                    deleteEntry(p);
                    return true;
                }
                return false;
            }
    
            // 返回EntrySet中元素个数
            public int size() {
                return TreeMap.this.size();
            }
    
            // 清空EntrySet
            public void clear() {
                TreeMap.this.clear();
            }
        }
    
        // 返回“TreeMap的KEY组成的迭代器(顺序)”
        Iterator<K> keyIterator() {
            return new KeyIterator(getFirstEntry());
        }
    
        // 返回“TreeMap的KEY组成的迭代器(逆序)”
        Iterator<K> descendingKeyIterator() {
            return new DescendingKeyIterator(getLastEntry());
        }
    
        // KeySet是“TreeMap中所有的KEY组成的集合”
        // KeySet继承于AbstractSet,而且实现了NavigableSet接口。
        static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
            // NavigableMap成员,KeySet是通过NavigableMap实现的
            private final NavigableMap<E, Object> m;
            KeySet(NavigableMap<E,Object> map) { m = map; }
    
            // 升序迭代器
            public Iterator<E> iterator() {
                // 若是TreeMap对象,则调用TreeMap的迭代器keyIterator()
                // 否则,调用TreeMap子类NavigableSubMap的迭代器keyIterator()
                if (m instanceof TreeMap)
                    return ((TreeMap<E,Object>)m).keyIterator();
                else
                    return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
            }
    
            // 降序迭代器
            public Iterator<E> descendingIterator() {
                // 若是TreeMap对象,则调用TreeMap的迭代器descendingKeyIterator()
                // 否则,调用TreeMap子类NavigableSubMap的迭代器descendingKeyIterator()
                if (m instanceof TreeMap)
                    return ((TreeMap<E,Object>)m).descendingKeyIterator();
                else
                    return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
            }
    
            public int size() { return m.size(); }
            public boolean isEmpty() { return m.isEmpty(); }
            public boolean contains(Object o) { return m.containsKey(o); }
            public void clear() { m.clear(); }
            public E lower(E e) { return m.lowerKey(e); }
            public E floor(E e) { return m.floorKey(e); }
            public E ceiling(E e) { return m.ceilingKey(e); }
            public E higher(E e) { return m.higherKey(e); }
            public E first() { return m.firstKey(); }
            public E last() { return m.lastKey(); }
            public Comparator<? super E> comparator() { return m.comparator(); }
            public E pollFirst() {
                Map.Entry<E,Object> e = m.pollFirstEntry();
                return e == null? null : e.getKey();
            }
            public E pollLast() {
                Map.Entry<E,Object> e = m.pollLastEntry();
                return e == null? null : e.getKey();
            }
            public boolean remove(Object o) {
                int oldSize = size();
                m.remove(o);
                return size() != oldSize;
            }
            public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                          E toElement,   boolean toInclusive) {
                return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
                                               toElement,   toInclusive));
            }
            public NavigableSet<E> headSet(E toElement, boolean inclusive) {
                return new TreeSet<E>(m.headMap(toElement, inclusive));
            }
            public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
                return new TreeSet<E>(m.tailMap(fromElement, inclusive));
            }
            public SortedSet<E> subSet(E fromElement, E toElement) {
                return subSet(fromElement, true, toElement, false);
            }
            public SortedSet<E> headSet(E toElement) {
                return headSet(toElement, false);
            }
            public SortedSet<E> tailSet(E fromElement) {
                return tailSet(fromElement, true);
            }
            public NavigableSet<E> descendingSet() {
                return new TreeSet(m.descendingMap());
            }
        }
    
        // 它是TreeMap中的一个抽象迭代器,实现了一些通用的接口。
        abstract class PrivateEntryIterator<T> implements Iterator<T> {
            // 下一个元素
            Entry<K,V> next;
            // 上一次返回元素
            Entry<K,V> lastReturned;
            // 期望的修改次数,用于实现fast-fail机制
            int expectedModCount;
    
            PrivateEntryIterator(Entry<K,V> first) {
                expectedModCount = modCount;
                lastReturned = null;
                next = first;
            }
    
            public final boolean hasNext() {
                return next != null;
            }
    
            // 获取下一个节点
            final Entry<K,V> nextEntry() {
                Entry<K,V> e = next;
                if (e == null)
                    throw new NoSuchElementException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                next = successor(e);
                lastReturned = e;
                return e;
            }
    
            // 获取上一个节点
            final Entry<K,V> prevEntry() {
                Entry<K,V> e = next;
                if (e == null)
                    throw new NoSuchElementException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                next = predecessor(e);
                lastReturned = e;
                return e;
            }
    
            // 删除当前节点
            public void remove() {
                if (lastReturned == null)
                    throw new IllegalStateException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时,要将其赋值给next”。
                // 目的是为了“删除lastReturned节点之后,next节点指向的仍然是下一个节点”。
                //     根据“红黑树”的特性可知:
                //     当被删除节点有两个儿子时。那么,首先把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。
                //     这意味着“当被删除节点有两个儿子时,删除当前节点之后,'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。
                //     而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点;能继续遍历红黑树。
                if (lastReturned.left != null && lastReturned.right != null)
                    next = lastReturned;
                deleteEntry(lastReturned);
                expectedModCount = modCount;
                lastReturned = null;
            }
        }
    
        // TreeMap的Entry对应的迭代器
        final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
            EntryIterator(Entry<K,V> first) {
                super(first);
            }
            public Map.Entry<K,V> next() {
                return nextEntry();
            }
        }
    
        // TreeMap的Value对应的迭代器
        final class ValueIterator extends PrivateEntryIterator<V> {
            ValueIterator(Entry<K,V> first) {
                super(first);
            }
            public V next() {
                return nextEntry().value;
            }
        }
    
        // reeMap的KEY组成的迭代器(顺序)
        final class KeyIterator extends PrivateEntryIterator<K> {
            KeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return nextEntry().key;
            }
        }
    
        // TreeMap的KEY组成的迭代器(逆序)
        final class DescendingKeyIterator extends PrivateEntryIterator<K> {
            DescendingKeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return prevEntry().key;
            }
        }
    
        // 比较两个对象的大小
        final int compare(Object k1, Object k2) {
            return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
                : comparator.compare((K)k1, (K)k2);
        }
    
        // 判断两个对象是否相等
        final static boolean valEquals(Object o1, Object o2) {
            return (o1==null ? o2==null : o1.equals(o2));
        }
    
        // 返回“Key-Value键值对”的一个简单拷贝(AbstractMap.SimpleImmutableEntry<K,V>对象)
        // 可用来读取“键值对”的值
        static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
            return e == null? null :
                new AbstractMap.SimpleImmutableEntry<K,V>(e);
        }
    
        // 若“键值对”不为null,则返回KEY;否则,返回null
        static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
            return e == null? null : e.key;
        }
    
        // 若“键值对”不为null,则返回KEY;否则,抛出异常
        static <K> K key(Entry<K,?> e) {
            if (e==null)
                throw new NoSuchElementException();
            return e.key;
        }
    
        // TreeMap的SubMap,它一个抽象类,实现了公共操作。
        // 它包括了"(升序)AscendingSubMap"和"(降序)DescendingSubMap"两个子类。
        static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
            implements NavigableMap<K,V>, java.io.Serializable {
            // TreeMap的拷贝
            final TreeMap<K,V> m;
            // lo是“子Map范围的最小值”,hi是“子Map范围的最大值”;
            // loInclusive是“是否包含lo的标记”,hiInclusive是“是否包含hi的标记”
            // fromStart是“表示是否从第一个节点开始计算”,
            // toEnd是“表示是否计算到最后一个节点      ”
            final K lo, hi;      
            final boolean fromStart, toEnd;
            final boolean loInclusive, hiInclusive;
    
            // 构造函数
            NavigableSubMap(TreeMap<K,V> m,
                            boolean fromStart, K lo, boolean loInclusive,
                            boolean toEnd,     K hi, boolean hiInclusive) {
                if (!fromStart && !toEnd) {
                    if (m.compare(lo, hi) > 0)
                        throw new IllegalArgumentException("fromKey > toKey");
                } else {
                    if (!fromStart) // type check
                        m.compare(lo, lo);
                    if (!toEnd)
                        m.compare(hi, hi);
                }
    
                this.m = m;
                this.fromStart = fromStart;
                this.lo = lo;
                this.loInclusive = loInclusive;
                this.toEnd = toEnd;
                this.hi = hi;
                this.hiInclusive = hiInclusive;
            }
    
            // 判断key是否太小
            final boolean tooLow(Object key) {
                // 若该SubMap不包括“起始节点”,
                // 并且,“key小于最小键(lo)”或者“key等于最小键(lo),但最小键却没包括在该SubMap内”
                // 则判断key太小。其余情况都不是太小!
                if (!fromStart) {
                    int c = m.compare(key, lo);
                    if (c < 0 || (c == 0 && !loInclusive))
                        return true;
                }
                return false;
            }
    
            // 判断key是否太大
            final boolean tooHigh(Object key) {
                // 若该SubMap不包括“结束节点”,
                // 并且,“key大于最大键(hi)”或者“key等于最大键(hi),但最大键却没包括在该SubMap内”
                // 则判断key太大。其余情况都不是太大!
                if (!toEnd) {
                    int c = m.compare(key, hi);
                    if (c > 0 || (c == 0 && !hiInclusive))
                        return true;
                }
                return false;
            }
    
            // 判断key是否在“lo和hi”开区间范围内
            final boolean inRange(Object key) {
                return !tooLow(key) && !tooHigh(key);
            }
    
            // 判断key是否在封闭区间内
            final boolean inClosedRange(Object key) {
                return (fromStart || m.compare(key, lo) >= 0)
                    && (toEnd || m.compare(hi, key) >= 0);
            }
    
            // 判断key是否在区间内, inclusive是区间开关标志
            final boolean inRange(Object key, boolean inclusive) {
                return inclusive ? inRange(key) : inClosedRange(key);
            }
    
            // 返回最低的Entry
            final TreeMap.Entry<K,V> absLowest() {
            // 若“包含起始节点”,则调用getFirstEntry()返回第一个节点
            // 否则的话,若包括lo,则调用getCeilingEntry(lo)获取大于/等于lo的最小的Entry;
            //           否则,调用getHigherEntry(lo)获取大于lo的最小Entry
            TreeMap.Entry<K,V> e =
                    (fromStart ?  m.getFirstEntry() :
                     (loInclusive ? m.getCeilingEntry(lo) :
                                    m.getHigherEntry(lo)));
                return (e == null || tooHigh(e.key)) ? null : e;
            }
    
            // 返回最高的Entry
            final TreeMap.Entry<K,V> absHighest() {
            // 若“包含结束节点”,则调用getLastEntry()返回最后一个节点
            // 否则的话,若包括hi,则调用getFloorEntry(hi)获取小于/等于hi的最大的Entry;
            //           否则,调用getLowerEntry(hi)获取大于hi的最大Entry
            TreeMap.Entry<K,V> e =
            TreeMap.Entry<K,V> e =
                    (toEnd ?  m.getLastEntry() :
                     (hiInclusive ?  m.getFloorEntry(hi) :
                                     m.getLowerEntry(hi)));
                return (e == null || tooLow(e.key)) ? null : e;
            }
    
            // 返回"大于/等于key的最小的Entry"
            final TreeMap.Entry<K,V> absCeiling(K key) {
                // 只有在“key太小”的情况下,absLowest()返回的Entry才是“大于/等于key的最小Entry”
                // 其它情况下不行。例如,当包含“起始节点”时,absLowest()返回的是最小Entry了!
                if (tooLow(key))
                    return absLowest();
                // 获取“大于/等于key的最小Entry”
            TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
                return (e == null || tooHigh(e.key)) ? null : e;
            }
    
            // 返回"大于key的最小的Entry"
            final TreeMap.Entry<K,V> absHigher(K key) {
                // 只有在“key太小”的情况下,absLowest()返回的Entry才是“大于key的最小Entry”
                // 其它情况下不行。例如,当包含“起始节点”时,absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”!
                if (tooLow(key))
                    return absLowest();
                // 获取“大于key的最小Entry”
            TreeMap.Entry<K,V> e = m.getHigherEntry(key);
                return (e == null || tooHigh(e.key)) ? null : e;
            }
    
            // 返回"小于/等于key的最大的Entry"
            final TreeMap.Entry<K,V> absFloor(K key) {
                // 只有在“key太大”的情况下,(absHighest)返回的Entry才是“小于/等于key的最大Entry”
                // 其它情况下不行。例如,当包含“结束节点”时,absHighest()返回的是最大Entry了!
                if (tooHigh(key))
                    return absHighest();
            // 获取"小于/等于key的最大的Entry"
            TreeMap.Entry<K,V> e = m.getFloorEntry(key);
                return (e == null || tooLow(e.key)) ? null : e;
            }
    
            // 返回"小于key的最大的Entry"
            final TreeMap.Entry<K,V> absLower(K key) {
                // 只有在“key太大”的情况下,(absHighest)返回的Entry才是“小于key的最大Entry”
                // 其它情况下不行。例如,当包含“结束节点”时,absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”!
                if (tooHigh(key))
                    return absHighest();
            // 获取"小于key的最大的Entry"
            TreeMap.Entry<K,V> e = m.getLowerEntry(key);
                return (e == null || tooLow(e.key)) ? null : e;
            }
    
            // 返回“大于最大节点中的最小节点”,不存在的话,返回null
            final TreeMap.Entry<K,V> absHighFence() {
                return (toEnd ? null : (hiInclusive ?
                                        m.getHigherEntry(hi) :
                                        m.getCeilingEntry(hi)));
            }
    
            // 返回“小于最小节点中的最大节点”,不存在的话,返回null
            final TreeMap.Entry<K,V> absLowFence() {
                return (fromStart ? null : (loInclusive ?
                                            m.getLowerEntry(lo) :
                                            m.getFloorEntry(lo)));
            }
    
            // 下面几个abstract方法是需要NavigableSubMap的实现类实现的方法
            abstract TreeMap.Entry<K,V> subLowest();
            abstract TreeMap.Entry<K,V> subHighest();
            abstract TreeMap.Entry<K,V> subCeiling(K key);
            abstract TreeMap.Entry<K,V> subHigher(K key);
            abstract TreeMap.Entry<K,V> subFloor(K key);
            abstract TreeMap.Entry<K,V> subLower(K key);
            // 返回“顺序”的键迭代器
            abstract Iterator<K> keyIterator();
            // 返回“逆序”的键迭代器
            abstract Iterator<K> descendingKeyIterator();
    
            // 返回SubMap是否为空。空的话,返回true,否则返回false
            public boolean isEmpty() {
                return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
            }
    
            // 返回SubMap的大小
            public int size() {
                return (fromStart && toEnd) ? m.size() : entrySet().size();
            }
    
            // 返回SubMap是否包含键key
            public final boolean containsKey(Object key) {
                return inRange(key) && m.containsKey(key);
            }
    
            // 将key-value 插入SubMap中
            public final V put(K key, V value) {
                if (!inRange(key))
                    throw new IllegalArgumentException("key out of range");
                return m.put(key, value);
            }
    
            // 获取key对应值
            public final V get(Object key) {
                return !inRange(key)? null :  m.get(key);
            }
    
            // 删除key对应的键值对
            public final V remove(Object key) {
                return !inRange(key)? null  : m.remove(key);
            }
    
            // 获取“大于/等于key的最小键值对”
            public final Map.Entry<K,V> ceilingEntry(K key) {
                return exportEntry(subCeiling(key));
            }
    
            // 获取“大于/等于key的最小键”
            public final K ceilingKey(K key) {
                return keyOrNull(subCeiling(key));
            }
    
            // 获取“大于key的最小键值对”
            public final Map.Entry<K,V> higherEntry(K key) {
                return exportEntry(subHigher(key));
            }
    
            // 获取“大于key的最小键”
            public final K higherKey(K key) {
                return keyOrNull(subHigher(key));
            }
    
            // 获取“小于/等于key的最大键值对”
            public final Map.Entry<K,V> floorEntry(K key) {
                return exportEntry(subFloor(key));
            }
    
            // 获取“小于/等于key的最大键”
            public final K floorKey(K key) {
                return keyOrNull(subFloor(key));
            }
    
            // 获取“小于key的最大键值对”
            public final Map.Entry<K,V> lowerEntry(K key) {
                return exportEntry(subLower(key));
            }
    
            // 获取“小于key的最大键”
            public final K lowerKey(K key) {
                return keyOrNull(subLower(key));
            }
    
            // 获取"SubMap的第一个键"
            public final K firstKey() {
                return key(subLowest());
            }
    
            // 获取"SubMap的最后一个键"
            public final K lastKey() {
                return key(subHighest());
            }
    
            // 获取"SubMap的第一个键值对"
            public final Map.Entry<K,V> firstEntry() {
                return exportEntry(subLowest());
            }
    
            // 获取"SubMap的最后一个键值对"
            public final Map.Entry<K,V> lastEntry() {
                return exportEntry(subHighest());
            }
    
            // 返回"SubMap的第一个键值对",并从SubMap中删除改键值对
            public final Map.Entry<K,V> pollFirstEntry() {
            TreeMap.Entry<K,V> e = subLowest();
                Map.Entry<K,V> result = exportEntry(e);
                if (e != null)
                    m.deleteEntry(e);
                return result;
            }
    
            // 返回"SubMap的最后一个键值对",并从SubMap中删除改键值对
            public final Map.Entry<K,V> pollLastEntry() {
            TreeMap.Entry<K,V> e = subHighest();
                Map.Entry<K,V> result = exportEntry(e);
                if (e != null)
                    m.deleteEntry(e);
                return result;
            }
    
            // Views
            transient NavigableMap<K,V> descendingMapView = null;
            transient EntrySetView entrySetView = null;
            transient KeySet<K> navigableKeySetView = null;
    
            // 返回NavigableSet对象,实际上返回的是当前对象的"Key集合"。 
            public final NavigableSet<K> navigableKeySet() {
                KeySet<K> nksv = navigableKeySetView;
                return (nksv != null) ? nksv :
                    (navigableKeySetView = new TreeMap.KeySet(this));
            }
    
            // 返回"Key集合"对象
            public final Set<K> keySet() {
                return navigableKeySet();
            }
    
            // 返回“逆序”的Key集合
            public NavigableSet<K> descendingKeySet() {
                return descendingMap().navigableKeySet();
            }
    
            // 排列fromKey(包含) 到 toKey(不包含) 的子map
            public final SortedMap<K,V> subMap(K fromKey, K toKey) {
                return subMap(fromKey, true, toKey, false);
            }
    
            // 返回当前Map的头部(从第一个节点 到 toKey, 不包括toKey)
            public final SortedMap<K,V> headMap(K toKey) {
                return headMap(toKey, false);
            }
    
            // 返回当前Map的尾部[从 fromKey(包括fromKeyKey) 到 最后一个节点]
            public final SortedMap<K,V> tailMap(K fromKey) {
                return tailMap(fromKey, true);
            }
    
            // Map的Entry的集合
            abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
                private transient int size = -1, sizeModCount;
    
                // 获取EntrySet的大小
                public int size() {
                    // 若SubMap是从“开始节点”到“结尾节点”,则SubMap大小就是原TreeMap的大小
                    if (fromStart && toEnd)
                        return m.size();
                    // 若SubMap不是从“开始节点”到“结尾节点”,则调用iterator()遍历EntrySetView中的元素
                    if (size == -1 || sizeModCount != m.modCount) {
                        sizeModCount = m.modCount;
                        size = 0;
                        Iterator i = iterator();
                        while (i.hasNext()) {
                            size++;
                            i.next();
                        }
                    }
                    return size;
                }
    
                // 判断EntrySetView是否为空
                public boolean isEmpty() {
                    TreeMap.Entry<K,V> n = absLowest();
                    return n == null || tooHigh(n.key);
                }
    
                // 判断EntrySetView是否包含Object
                public boolean contains(Object o) {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                    K key = entry.getKey();
                    if (!inRange(key))
                        return false;
                    TreeMap.Entry node = m.getEntry(key);
                    return node != null &&
                        valEquals(node.getValue(), entry.getValue());
                }
    
                // 从EntrySetView中删除Object
                public boolean remove(Object o) {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                    K key = entry.getKey();
                    if (!inRange(key))
                        return false;
                    TreeMap.Entry<K,V> node = m.getEntry(key);
                    if (node!=null && valEquals(node.getValue(),entry.getValue())){
                        m.deleteEntry(node);
                        return true;
                    }
                    return false;
                }
            }
    
            // SubMap的迭代器
            abstract class SubMapIterator<T> implements Iterator<T> {
                // 上一次被返回的Entry
                TreeMap.Entry<K,V> lastReturned;
                // 指向下一个Entry
                TreeMap.Entry<K,V> next;
                // “栅栏key”。根据SubMap是“升序”还是“降序”具有不同的意义
                final K fenceKey;
                int expectedModCount;
    
                // 构造函数
                SubMapIterator(TreeMap.Entry<K,V> first,
                               TreeMap.Entry<K,V> fence) {
                    // 每创建一个SubMapIterator时,保存修改次数
                    // 若后面发现expectedModCount和modCount不相等,则抛出ConcurrentModificationException异常。
                    // 这就是所说的fast-fail机制的原理!
                    expectedModCount = m.modCount;
                    lastReturned = null;
                    next = first;
                    fenceKey = fence == null ? null : fence.key;
                }
    
                // 是否存在下一个Entry
                public final boolean hasNext() {
                    return next != null && next.key != fenceKey;
                }
    
                // 返回下一个Entry
                final TreeMap.Entry<K,V> nextEntry() {
                    TreeMap.Entry<K,V> e = next;
                    if (e == null || e.key == fenceKey)
                        throw new NoSuchElementException();
                    if (m.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    // next指向e的后继节点
                    next = successor(e);
            lastReturned = e;
                    return e;
                }
    
                // 返回上一个Entry
                final TreeMap.Entry<K,V> prevEntry() {
                    TreeMap.Entry<K,V> e = next;
                    if (e == null || e.key == fenceKey)
                        throw new NoSuchElementException();
                    if (m.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    // next指向e的前继节点
                    next = predecessor(e);
            lastReturned = e;
                    return e;
                }
    
                // 删除当前节点(用于“升序的SubMap”)。
                // 删除之后,可以继续升序遍历;红黑树特性没变。
                final void removeAscending() {
                    if (lastReturned == null)
                        throw new IllegalStateException();
                    if (m.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时,要将其赋值给next”。
                    // 目的是为了“删除lastReturned节点之后,next节点指向的仍然是下一个节点”。
                    //     根据“红黑树”的特性可知:
                    //     当被删除节点有两个儿子时。那么,首先把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。
                    //     这意味着“当被删除节点有两个儿子时,删除当前节点之后,'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。
                    //     而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点;能继续遍历红黑树。
                    if (lastReturned.left != null && lastReturned.right != null)
                        next = lastReturned;
                    m.deleteEntry(lastReturned);
                    lastReturned = null;
                    expectedModCount = m.modCount;
                }
    
                // 删除当前节点(用于“降序的SubMap”)。
                // 删除之后,可以继续降序遍历;红黑树特性没变。
                final void removeDescending() {
                    if (lastReturned == null)
                        throw new IllegalStateException();
                    if (m.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    m.deleteEntry(lastReturned);
                    lastReturned = null;
                    expectedModCount = m.modCount;
                }
    
            }
    
            // SubMap的Entry迭代器,它只支持升序操作,继承于SubMapIterator
            final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
                SubMapEntryIterator(TreeMap.Entry<K,V> first,
                                    TreeMap.Entry<K,V> fence) {
                    super(first, fence);
                }
                // 获取下一个节点(升序)
                public Map.Entry<K,V> next() {
                    return nextEntry();
                }
                // 删除当前节点(升序)
                public void remove() {
                    removeAscending();
                }
            }
    
            // SubMap的Key迭代器,它只支持升序操作,继承于SubMapIterator
            final class SubMapKeyIterator extends SubMapIterator<K> {
                SubMapKeyIterator(TreeMap.Entry<K,V> first,
                                  TreeMap.Entry<K,V> fence) {
                    super(first, fence);
                }
                // 获取下一个节点(升序)
                public K next() {
                    return nextEntry().key;
                }
                // 删除当前节点(升序)
                public void remove() {
                    removeAscending();
                }
            }
    
            // 降序SubMap的Entry迭代器,它只支持降序操作,继承于SubMapIterator
            final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
                DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
                                              TreeMap.Entry<K,V> fence) {
                    super(last, fence);
                }
    
                // 获取下一个节点(降序)
                public Map.Entry<K,V> next() {
                    return prevEntry();
                }
                // 删除当前节点(降序)
                public void remove() {
                    removeDescending();
                }
            }
    
            // 降序SubMap的Key迭代器,它只支持降序操作,继承于SubMapIterator
            final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
                DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
                                            TreeMap.Entry<K,V> fence) {
                    super(last, fence);
                }
                // 获取下一个节点(降序)
                public K next() {
                    return prevEntry().key;
                }
                // 删除当前节点(降序)
                public void remove() {
                    removeDescending();
                }
            }
        }
    
    
        // 升序的SubMap,继承于NavigableSubMap
        static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
            private static final long serialVersionUID = 912986545866124060L;
    
            // 构造函数
            AscendingSubMap(TreeMap<K,V> m,
                            boolean fromStart, K lo, boolean loInclusive,
                            boolean toEnd,     K hi, boolean hiInclusive) {
                super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
            }
    
            // 比较器
            public Comparator<? super K> comparator() {
                return m.comparator();
            }
    
            // 获取“子Map”。
            // 范围是从fromKey 到 toKey;fromInclusive是是否包含fromKey的标记,toInclusive是是否包含toKey的标记
            public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                            K toKey,   boolean toInclusive) {
                if (!inRange(fromKey, fromInclusive))
                    throw new IllegalArgumentException("fromKey out of range");
                if (!inRange(toKey, toInclusive))
                    throw new IllegalArgumentException("toKey out of range");
                return new AscendingSubMap(m,
                                           false, fromKey, fromInclusive,
                                           false, toKey,   toInclusive);
            }
    
            // 获取“Map的头部”。
            // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
            public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
                if (!inRange(toKey, inclusive))
                    throw new IllegalArgumentException("toKey out of range");
                return new AscendingSubMap(m,
                                           fromStart, lo,    loInclusive,
                                           false,     toKey, inclusive);
            }
    
            // 获取“Map的尾部”。
            // 范围是从 fromKey 到 最后一个节点,inclusive是是否包含fromKey的标记
            public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
                if (!inRange(fromKey, inclusive))
                    throw new IllegalArgumentException("fromKey out of range");
                return new AscendingSubMap(m,
                                           false, fromKey, inclusive,
                                           toEnd, hi,      hiInclusive);
            }
    
            // 获取对应的降序Map
            public NavigableMap<K,V> descendingMap() {
                NavigableMap<K,V> mv = descendingMapView;
                return (mv != null) ? mv :
                    (descendingMapView =
                     new DescendingSubMap(m,
                                          fromStart, lo, loInclusive,
                                          toEnd,     hi, hiInclusive));
            }
    
            // 返回“升序Key迭代器”
            Iterator<K> keyIterator() {
                return new SubMapKeyIterator(absLowest(), absHighFence());
            }
    
            // 返回“降序Key迭代器”
            Iterator<K> descendingKeyIterator() {
                return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
            }
    
            // “升序EntrySet集合”类
            // 实现了iterator()
            final class AscendingEntrySetView extends EntrySetView {
                public Iterator<Map.Entry<K,V>> iterator() {
                    return new SubMapEntryIterator(absLowest(), absHighFence());
                }
            }
    
            // 返回“升序EntrySet集合”
            public Set<Map.Entry<K,V>> entrySet() {
                EntrySetView es = entrySetView;
                return (es != null) ? es : new AscendingEntrySetView();
            }
    
            TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
            TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
            TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
            TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
            TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
            TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
        }
    
        // 降序的SubMap,继承于NavigableSubMap
        // 相比于升序SubMap,它的实现机制是将“SubMap的比较器反转”!
        static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
            private static final long serialVersionUID = 912986545866120460L;
            DescendingSubMap(TreeMap<K,V> m,
                            boolean fromStart, K lo, boolean loInclusive,
                            boolean toEnd,     K hi, boolean hiInclusive) {
                super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
            }
    
            // 反转的比较器:是将原始比较器反转得到的。
            private final Comparator<? super K> reverseComparator =
                Collections.reverseOrder(m.comparator);
    
            // 获取反转比较器
            public Comparator<? super K> comparator() {
                return reverseComparator;
            }
    
            // 获取“子Map”。
            // 范围是从fromKey 到 toKey;fromInclusive是是否包含fromKey的标记,toInclusive是是否包含toKey的标记
            public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                            K toKey,   boolean toInclusive) {
                if (!inRange(fromKey, fromInclusive))
                    throw new IllegalArgumentException("fromKey out of range");
                if (!inRange(toKey, toInclusive))
                    throw new IllegalArgumentException("toKey out of range");
                return new DescendingSubMap(m,
                                            false, toKey,   toInclusive,
                                            false, fromKey, fromInclusive);
            }
    
            // 获取“Map的头部”。
            // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
            public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
                if (!inRange(toKey, inclusive))
                    throw new IllegalArgumentException("toKey out of range");
                return new DescendingSubMap(m,
                                            false, toKey, inclusive,
                                            toEnd, hi,    hiInclusive);
            }
    
            // 获取“Map的尾部”。
            // 范围是从 fromKey 到 最后一个节点,inclusive是是否包含fromKey的标记
            public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
                if (!inRange(fromKey, inclusive))
                    throw new IllegalArgumentException("fromKey out of range");
                return new DescendingSubMap(m,
                                            fromStart, lo, loInclusive,
                                            false, fromKey, inclusive);
            }
    
            // 获取对应的降序Map
            public NavigableMap<K,V> descendingMap() {
                NavigableMap<K,V> mv = descendingMapView;
                return (mv != null) ? mv :
                    (descendingMapView =
                     new AscendingSubMap(m,
                                         fromStart, lo, loInclusive,
                                         toEnd,     hi, hiInclusive));
            }
    
            // 返回“升序Key迭代器”
            Iterator<K> keyIterator() {
                return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
            }
    
            // 返回“降序Key迭代器”
            Iterator<K> descendingKeyIterator() {
                return new SubMapKeyIterator(absLowest(), absHighFence());
            }
    
            // “降序EntrySet集合”类
            // 实现了iterator()
            final class DescendingEntrySetView extends EntrySetView {
                public Iterator<Map.Entry<K,V>> iterator() {
                    return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
                }
            }
    
            // 返回“降序EntrySet集合”
            public Set<Map.Entry<K,V>> entrySet() {
                EntrySetView es = entrySetView;
                return (es != null) ? es : new DescendingEntrySetView();
            }
    
            TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
            TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
            TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
            TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
            TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
            TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
        }
    
        // SubMap是旧版本的类,新的Java中没有用到。
        private class SubMap extends AbstractMap<K,V>
        implements SortedMap<K,V>, java.io.Serializable {
            private static final long serialVersionUID = -6520786458950516097L;
            private boolean fromStart = false, toEnd = false;
            private K fromKey, toKey;
            private Object readResolve() {
                return new AscendingSubMap(TreeMap.this,
                                           fromStart, fromKey, true,
                                           toEnd, toKey, false);
            }
            public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
            public K lastKey() { throw new InternalError(); }
            public K firstKey() { throw new InternalError(); }
            public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
            public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
            public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
            public Comparator<? super K> comparator() { throw new InternalError(); }
        }
    
    
        // 红黑树的节点颜色--红色
        private static final boolean RED   = false;
        // 红黑树的节点颜色--黑色
        private static final boolean BLACK = true;
    
        // “红黑树的节点”对应的类。
        // 包含了 key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)
        static final class Entry<K,V> implements Map.Entry<K,V> {
            // 键
            K key;
            // 值
            V value;
            // 左孩子
            Entry<K,V> left = null;
            // 右孩子
            Entry<K,V> right = null;
            // 父节点
            Entry<K,V> parent;
            // 当前节点颜色
            boolean color = BLACK;
    
            // 构造函数
            Entry(K key, V value, Entry<K,V> parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
    
            // 返回“键”
            public K getKey() {
                return key;
            }
    
            // 返回“值”
            public V getValue() {
                return value;
            }
    
            // 更新“值”,返回旧的值
            public V setValue(V value) {
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }
    
            // 判断两个节点是否相等的函数,覆盖equals()函数。
            // 若两个节点的“key相等”并且“value相等”,则两个节点相等
            public boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    
                return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
            }
    
            // 覆盖hashCode函数。
            public int hashCode() {
                int keyHash = (key==null ? 0 : key.hashCode());
                int valueHash = (value==null ? 0 : value.hashCode());
                return keyHash ^ valueHash;
            }
    
            // 覆盖toString()函数。
            public String toString() {
                return key + "=" + value;
            }
        }
    
        // 返回“红黑树的第一个节点”
        final Entry<K,V> getFirstEntry() {
            Entry<K,V> p = root;
            if (p != null)
                while (p.left != null)
                    p = p.left;
            return p;
        }
    
        // 返回“红黑树的最后一个节点”
        final Entry<K,V> getLastEntry() {
            Entry<K,V> p = root;
            if (p != null)
                while (p.right != null)
                    p = p.right;
            return p;
        }
    
        // 返回“节点t的后继节点”
        static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
            if (t == null)
                return null;
            else if (t.right != null) {
                Entry<K,V> p = t.right;
                while (p.left != null)
                    p = p.left;
                return p;
            } else {
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }
    
        // 返回“节点t的前继节点”
        static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
            if (t == null)
                return null;
            else if (t.left != null) {
                Entry<K,V> p = t.left;
                while (p.right != null)
                    p = p.right;
                return p;
            } else {
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.left) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }
    
        // 返回“节点p的颜色”
        // 根据“红黑树的特性”可知:空节点颜色是黑色。
        private static <K,V> boolean colorOf(Entry<K,V> p) {
            return (p == null ? BLACK : p.color);
        }
    
        // 返回“节点p的父节点”
        private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
            return (p == null ? null: p.parent);
        }
    
        // 设置“节点p的颜色为c”
        private static <K,V> void setColor(Entry<K,V> p, boolean c) {
            if (p != null)
            p.color = c;
        }
    
        // 设置“节点p的左孩子”
        private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
            return (p == null) ? null: p.left;
        }
    
        // 设置“节点p的右孩子”
        private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
            return (p == null) ? null: p.right;
        }
    
        // 对节点p执行“左旋”操作
        private void rotateLeft(Entry<K,V> p) {
            if (p != null) {
                Entry<K,V> r = p.right;
                p.right = r.left;
                if (r.left != null)
                    r.left.parent = p;
                r.parent = p.parent;
                if (p.parent == null)
                    root = r;
                else if (p.parent.left == p)
                    p.parent.left = r;
                else
                    p.parent.right = r;
                r.left = p;
                p.parent = r;
            }
        }
    
        // 对节点p执行“右旋”操作
        private void rotateRight(Entry<K,V> p) {
            if (p != null) {
                Entry<K,V> l = p.left;
                p.left = l.right;
                if (l.right != null) l.right.parent = p;
                l.parent = p.parent;
                if (p.parent == null)
                    root = l;
                else if (p.parent.right == p)
                    p.parent.right = l;
                else p.parent.left = l;
                l.right = p;
                p.parent = l;
            }
        }
    
        // 插入之后的修正操作。
        // 目的是保证:红黑树插入节点之后,仍然是一颗红黑树
        private void fixAfterInsertion(Entry<K,V> x) {
            x.color = RED;
    
            while (x != null && x != root && x.parent.color == RED) {
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                    Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                    if (colorOf(y) == RED) {
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    } else {
                        if (x == rightOf(parentOf(x))) {
                            x = parentOf(x);
                            rotateLeft(x);
                        }
                        setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateRight(parentOf(parentOf(x)));
                    }
                } else {
                    Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                    if (colorOf(y) == RED) {
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    } else {
                        if (x == leftOf(parentOf(x))) {
                            x = parentOf(x);
                            rotateRight(x);
                        }
                        setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateLeft(parentOf(parentOf(x)));
                    }
                }
            }
            root.color = BLACK;
        }
    
        // 删除“红黑树的节点p”
        private void deleteEntry(Entry<K,V> p) {
            modCount++;
            size--;
    
            // If strictly internal, copy successor's element to p and then make p
            // point to successor.
            if (p.left != null && p.right != null) {
                Entry<K,V> s = successor (p);
                p.key = s.key;
                p.value = s.value;
                p = s;
            } // p has 2 children
    
            // Start fixup at replacement node, if it exists.
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
            if (replacement != null) {
                // Link replacement to parent
                replacement.parent = p.parent;
                if (p.parent == null)
                    root = replacement;
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
                else
                    p.parent.right = replacement;
    
                // Null out links so they are OK to use by fixAfterDeletion.
                p.left = p.right = p.parent = null;
    
                // Fix replacement
                if (p.color == BLACK)
                    fixAfterDeletion(replacement);
            } else if (p.parent == null) { // return if we are the only node.
                root = null;
            } else { //  No children. Use self as phantom replacement and unlink.
                if (p.color == BLACK)
                    fixAfterDeletion(p);
    
                if (p.parent != null) {
                    if (p == p.parent.left)
                        p.parent.left = null;
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }
    
        // 删除之后的修正操作。
        // 目的是保证:红黑树删除节点之后,仍然是一颗红黑树
        private void fixAfterDeletion(Entry<K,V> x) {
            while (x != root && colorOf(x) == BLACK) {
                if (x == leftOf(parentOf(x))) {
                    Entry<K,V> sib = rightOf(parentOf(x));
    
                    if (colorOf(sib) == RED) {
                        setColor(sib, BLACK);
                        setColor(parentOf(x), RED);
                        rotateLeft(parentOf(x));
                        sib = rightOf(parentOf(x));
                    }
    
                    if (colorOf(leftOf(sib))  == BLACK &&
                        colorOf(rightOf(sib)) == BLACK) {
                        setColor(sib, RED);
                        x = parentOf(x);
                    } else {
                        if (colorOf(rightOf(sib)) == BLACK) {
                            setColor(leftOf(sib), BLACK);
                            setColor(sib, RED);
                            rotateRight(sib);
                            sib = rightOf(parentOf(x));
                        }
                        setColor(sib, colorOf(parentOf(x)));
                        setColor(parentOf(x), BLACK);
                        setColor(rightOf(sib), BLACK);
                        rotateLeft(parentOf(x));
                        x = root;
                    }
                } else { // symmetric
                    Entry<K,V> sib = leftOf(parentOf(x));
    
                    if (colorOf(sib) == RED) {
                        setColor(sib, BLACK);
                        setColor(parentOf(x), RED);
                        rotateRight(parentOf(x));
                        sib = leftOf(parentOf(x));
                    }
    
                    if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                        setColor(sib, RED);
                        x = parentOf(x);
                    } else {
                        if (colorOf(leftOf(sib)) == BLACK) {
                            setColor(rightOf(sib), BLACK);
                            setColor(sib, RED);
                            rotateLeft(sib);
                            sib = leftOf(parentOf(x));
                        }
                        setColor(sib, colorOf(parentOf(x)));
                        setColor(parentOf(x), BLACK);
                        setColor(leftOf(sib), BLACK);
                        rotateRight(parentOf(x));
                        x = root;
                    }
                }
            }
    
            setColor(x, BLACK);
        }
    
        private static final long serialVersionUID = 919286545866124006L;
    
        // java.io.Serializable的写入函数
        // 将TreeMap的“容量,所有的Entry”都写入到输出流中
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // Write out the Comparator and any hidden stuff
            s.defaultWriteObject();
    
            // Write out size (number of Mappings)
            s.writeInt(size);
    
            // Write out keys and values (alternating)
            for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
                Map.Entry<K,V> e = i.next();
                s.writeObject(e.getKey());
                s.writeObject(e.getValue());
            }
        }
    
    
        // java.io.Serializable的读取函数:根据写入方式读出
        // 先将TreeMap的“容量、所有的Entry”依次读出
        private void readObject(final java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in the Comparator and any hidden stuff
            s.defaultReadObject();
    
            // Read in size
            int size = s.readInt();
    
            buildFromSorted(size, null, s, null);
        }
    
        // 根据已经一个排好序的map创建一个TreeMap
        private void buildFromSorted(int size, Iterator it,
                     java.io.ObjectInputStream str,
                     V defaultVal)
            throws  java.io.IOException, ClassNotFoundException {
            this.size = size;
            root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                       it, str, defaultVal);
        }
    
        // 根据已经一个排好序的map创建一个TreeMap
        // 将map中的元素逐个添加到TreeMap中,并返回map的中间元素作为根节点。
        private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                             int redLevel,
                             Iterator it,
                             java.io.ObjectInputStream str,
                             V defaultVal)
            throws  java.io.IOException, ClassNotFoundException {
    
            if (hi < lo) return null;
    
    
            // 获取中间元素
            int mid = (lo + hi) / 2;
    
            Entry<K,V> left  = null;
            // 若lo小于mid,则递归调用获取(middel的)左孩子。
            if (lo < mid)
                left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                       it, str, defaultVal);
    
            // 获取middle节点对应的key和value
            K key;
            V value;
            if (it != null) {
                if (defaultVal==null) {
                    Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
                    key = entry.getKey();
                    value = entry.getValue();
                } else {
                    key = (K)it.next();
                    value = defaultVal;
                }
            } else { // use stream
                key = (K) str.readObject();
                value = (defaultVal != null ? defaultVal : (V) str.readObject());
            }
    
            // 创建middle节点
            Entry<K,V> middle =  new Entry<K,V>(key, value, null);
    
            // 若当前节点的深度=红色节点的深度,则将节点着色为红色。
            if (level == redLevel)
                middle.color = RED;
    
            // 设置middle为left的父亲,left为middle的左孩子
            if (left != null) {
                middle.left = left;
                left.parent = middle;
            }
    
            if (mid < hi) {
                // 递归调用获取(middel的)右孩子。
                Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                               it, str, defaultVal);
                // 设置middle为left的父亲,left为middle的左孩子
                middle.right = right;
                right.parent = middle;
            }
    
            return middle;
        }
    
        // 计算节点树为sz的最大深度,也是红色节点的深度值。
        private static int computeRedLevel(int sz) {
            int level = 0;
            for (int m = sz - 1; m >= 0; m = m / 2 - 1)
                level++;
            return level;
        }
    }
    展开全文
  • 转载Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例 一、TreeMap 简单介绍 什么是Map?  在数组中我们通过数组下标来对数组内容进行索引的,而在Map中我们通过对象来对 对象进行索引,用来索引的对象...

    转载 Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例

    一、TreeMap 简单介绍

    什么是Map?

      在数组中我们通过数组下标来对数组内容进行索引的,而在Map中我们通过对象来对 对象进行索引,用来索引的对象叫做key,其对应的对象叫做value。这就是我们平时说的键值对。

    什么是TreeMap?

      TreeMap是一个有序的key-value集合,是非线程安全的,基于红黑树(Red-Black tree)实现。其映射根据键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。其基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

      当自定义比较器时,需要自定义类实现java.lang.Comparable接口,并重写compareTo()方法。

    TreeMap与HashMap的区别:

    • 数据结构不同:
      • HashMap是基于哈希表,由 数组+链表+红黑树 构成。
      • TreeMap是基于红黑树实现。
    • 存储方式不同:
      • HashMap是通过key的hashcode对其内容进行快速查找。
      • TreeMap中所有的元素都保持着某种固定的顺序。
    • 排列顺序:
      • HashMap存储顺序不固定。
      • TreeMap存储顺序固定,可以得到一个有序的结果集。

    二、TreeMap源码分析

     1.TreeMap类继承图:

    TreeMap类定义:

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    • TreeMap<K,V>:TreeMap是以key-value形式存储数据的。
    • extends AbstractMap<K,V>:继承了AbstractMap,大大减少了实现Map接口时需要的工作量。
    • implements NavigableMap<K,V>:实现了SortedMap,支持一系列的导航方法。比如返回有序的key集合。
    • implements Cloneable:表明其可以调用克隆方法clone()来返回实例的field-for-field拷贝。
    • implements Serializable:表明该类是可以序列化的。

    2.类成员变量和静态内部类Entry:

    // 比较器对象
    private final Comparator<? super K> comparator;
    
    // 根节点
    private transient Entry<K,V> root;
    
    // 集合大小
    private transient int size = 0;
    
    // 树结构被修改的次数
    private transient int modCount = 0;

     // 红黑树节点颜色
     private static final boolean RED = false;
     private static final boolean BLACK = true;

    // 静态内部类用来表示节点类型
    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;     //
        V value;   //
        Entry<K,V> left;    // 指向左子树的引用(指针)
        Entry<K,V> right;   // 指向右子树的引用(指针)
        Entry<K,V> parent;  // 指向父节点的引用(指针)
        boolean color = BLACK; 
    }

    关键字transient的作用:

      transient是Java语言的关键字,它被用来表示一个域中不是该对象串行化的一部分。
      Java的 serialization 提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。
    当一个对象被串行化的时候,transient型的变量值 不包括在串行化的表示中,而 非transient型的变量 是被包括进去的。

    3.TreeMap的构造函数:

    // 默认构造函数。使用默认比较器比较key的大小,TreeMap中的元素按照自然排序进行排列。
    public TreeMap() {
       // 默认比较机制 comparator
    = null; } // 带比较器的构造函数 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } // 带Map的构造函数,Map会成为TreeMap的子集 public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } // 带SortedMap的构造函数,SortedMap会成为TreeMap的子集 public TreeMap(SortedMap<K, ? extends V> m) {
       // 使用已知对象的比较器 comparator
    = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }

    putAll(Map<? extends K, ? extends V> map) 方法:

    /**
     * Map中的所有元素添加到TreeMap中
     */
    public void putAll(Map<? extends K, ? extends V> map) {
        int mapSize = map.size();
        // TreeMap的size为0,map的size不为0,并且map是SortedMap的实例
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            // 默认比较器等于map的比较器,或者map的比较器不为null,并且与默认比较器相等
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        // 使用父类putAll()
        super.putAll(map);
    }
    
    /**
     * Map中的所有元素添加到TreeMap中
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        // 遍历map一个一个添加到TreeMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

    buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) 方法:

    /**
     * SortedMap(有序的map)中的所有元素添加到TreeMap中
     */
    private void buildFromSorted(int size, Iterator<?> it,
                                 java.io.ObjectInputStream str,
                                 V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {
        this.size = size;
        root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                               it, str, defaultVal);
    }
    
    /**
     * 将map中的元素逐个添加到TreeMap中,并返回map的中间元素作为根节点
     */
    private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                                             int redLevel,
                                             Iterator<?> it,
                                             java.io.ObjectInputStream str,
                                             V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {
    
        if (hi < lo) return null;
    
        // 获取中间元素
        int mid = (lo + hi) >>> 1;
    
        Entry<K,V> left  = null;
        
        // 若lo小于mid,则递归调用获取(middel的)左孩子。
        if (lo < mid)
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                                   it, str, defaultVal);
    
        // 从Iterator或stream中获取middle节点对应的key和value
        K key;
        V value;
        if (it != null) {
            if (defaultVal==null) {
                Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
                key = (K)entry.getKey();
                value = (V)entry.getValue();
            } else {
                key = (K)it.next();
                value = defaultVal;
            }
        } else { // use stream
            key = (K) str.readObject();
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }
    
        // 创建middle节点
        Entry<K,V> middle =  new Entry<>(key, value, null);
    
        // 若当前节点的深度==红色节点的深度,则将节点着色为红色
        if (level == redLevel)
            middle.color = RED;
    
        // 设置middle为left的父亲,left为middle的左孩子
        if (left != null) {
            middle.left = left;
            left.parent = middle;
        }
    
        if (mid < hi) {
            // 递归调用获取(middel的)右孩子
            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                               it, str, defaultVal);
            // 设置middle为right的父亲,right为middle的右孩子
            middle.right = right;
            right.parent = middle;
        }
    
        return middle;
    }

      添加到红黑树中时,只将level == redLevel的节点设为红色。表示第level级节点,实际上是用buildFromSorted方法转换成红黑树后 的最底端的节点(假设根节点在最上方);只将红黑树最底端的级别 着色为红色,其余都是黑色。

    4.核心方法:

    红黑树相关的方法:

    rotateLeft(Entry<K,V> p) 方法:

    /**
     * 左旋
     */
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            
            Entry<K,V> r = p.right; // 令p节点右孩子为r节点
            p.right = r.left; // 令r节点的左孩子为 p节点的右孩子
            if (r.left != null)
                r.left.parent = p; // 当r节点的左孩子不为null时,令p节点为 r节点的左孩子 的父节点
            r.parent = p.parent; // 令p节点的父节点为 r节点的父节点
            if (p.parent == null)
                root = r; // 当p节点的父节点为null时,令r节点为根节点
            else if (p.parent.left == p)
                p.parent.left = r; // 当p节点的父节点的左孩子为p节点时,令r节点为 p节点的父节点的左孩子
            else
                p.parent.right = r; // 当p节点的父节点的右孩子为p节点时,令r节点为 p节点的父节点的右孩子
            r.left = p; // 令p节点为 r节点的左孩子
            p.parent = r; // 令r节点为 p节点的父节点
        }
    }

    put(K key, V value) 方法:

    /**
     * 插入操作
     */
    public V put(K key, V value) {
        Entry<K,V> t = root; // 获取根节点
        if (t == null) {
            compare(key, key); // 检查key的类型,是否为null
    
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        
        // 获取比较器
        Comparator<? super K> cpr = comparator;
        // 比较器不为null时,即自定义了比较器
        if (cpr != null) {
            // 循环比较插入节点的key与根节点的key的大小,确定插入节点的位置,即找到插入节点的父节点
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value); // 插入节点与根节点的key的大小相同,直接覆盖
            } while (t != null);
        }
        // 比较器为null时,使用默认的比较器
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            // 循环比较插入节点的key与根节点的key的大小,确定插入节点的位置,即找到插入节点的父节点
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 在插入节点的父节点后创建节点
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 插入修正操作,使插入节点后,TreeMap还是红黑树结构
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

    与红黑树有关的方法还有:

    • 右旋-rotateRight(Entry<K,V> p)
    • 插入修正为红黑树-fixAfterInsertion(Entry<K,V> x)
    • 删除-deleteEntry(Entry<K,V> p)
    • 删除修正为红黑树-fixAfterDeletion(Entry<K,V> x)

    都是根据算法翻译成代码,具体可参考这里。

    TreeMap中Entry相关的方法:

      TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 原理类似,以下讲解firstEntry()方法。

    firstEntry() 方法:

    /**
     * 获取第一个节点
     */
    public Map.Entry<K,V> firstEntry() {
        return exportEntry(getFirstEntry());
    }
    
    /**
     * 获取第一个节点
     */
    final Entry<K,V> getFirstEntry() {
        // 获取根节点
        Entry<K,V> p = root; 
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }
    
    /**
     * 获取第一个节点
     */
    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
        // 如果节点为null,创建AbstractMap.SimpleImmutableEntry类型的对象,并返回
        return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
    }
    public static class SimpleImmutableEntry<K,V>
        implements Entry<K,V>, java.io.Serializable
    {
        private static final long serialVersionUID = 7138329143949025153L;
    
        private final K key;
        private final V value;
    
        public SimpleImmutableEntry(K key, V value) {
            this.key   = key;
            this.value = value;
        }
    
        public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
            this.key   = entry.getKey();
            this.value = entry.getValue();
        }
    
        public K getKey() {
            return key;
        }
    
        public V getValue() {
            return value;
        }
    
        public V setValue(V value) {
            throw new UnsupportedOperationException();
        }
    
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return eq(key, e.getKey()) && eq(value, e.getValue());
        }
    
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }
    
        public String toString() {
            return key + "=" + value;
        }
    
    }
    SimpleImmutableEntry 类的实现

      从上面,我们可以看出 firstEntry() 和 getFirstEntry() 都是用于获取第一个节点。但是,firstEntry() 是对外接口; getFirstEntry() 是内部接口。而且,firstEntry() 是通过 getFirstEntry() 来实现的。那为什么外界不能直接调用 getFirstEntry(),而需要多此一举的调用 firstEntry() 呢?

      这么做的目的是:防止用户修改返回的Entry。getFirstEntry()返回的Entry是可以被修改的,但是经过firstEntry()返回的Entry不能被修改,只可以读取Entry的key值和value值。因为exportEntry()方法所在类 SimpleImmutableEntry 的 setValue()方法会抛出 UnsupportedOperationException() 异常。

    TreeMap中key相关方法:

      TreeMap的firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()原理都是类似的,下面以ceilingKey()来进行详细说明。

    ceilingKey(K key) 方法:

    /**
     * 获取大于/等于key的最小节点所对应的key,没有的话返回null
     */
    public K ceilingKey(K key) {
        return keyOrNull(getCeilingEntry(key));
    }
    /**
     * 寻找大于/等于key的最小节点
     */
    final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            // 如果根节点的key大于给定key
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) { // 如果根节点的key小于给定key
                if (p.right != null) {
                    p = p.right;
                } else { // 如果根节点的右孩子为null
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }
    /**
     * 如果节点不为null,返回节点的key值,否则返回null
     */
    static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
        return (e == null) ? null : e.key;
    }

    TreeMap中value()方法:

    value() 方法返回 TreeMap中值的集合:

    /**
     * 通过 new Values() 来实现,返回TreeMap中值的集合
     * Values() 是集合类Value的构造函数
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }
    
    /**
     * 集合类Value
     */
    class Values extends AbstractCollection<V> {
        // 返回迭代器
        public Iterator<V> iterator() {
            // iterator() 通过ValueIterator() 返回迭代器
            return new ValueIterator(getFirstEntry());
        }
        
        // 返回个数
        public int size() {
            return TreeMap.this.size();
        }
    
        // TreeMap的值的集合中 是否包含 对象o
        public boolean contains(Object o) {
            return TreeMap.this.containsValue(o);
        }
    
        // 删除TreeMap的值的集合中的对象o
        public boolean remove(Object o) {
            for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
                if (valEquals(e.getValue(), o)) {
                    deleteEntry(e);
                    return true;
                }
            }
            return false;
        }
    
        // 清空TreeMap的值的集合
        public void clear() {
            TreeMap.this.clear();
        }
    
        public Spliterator<V> spliterator() {
            return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
        }
    }
    
    /**
     * ValueIterator类实现 Iterator接口实现的next()方法
     */
    final class ValueIterator extends PrivateEntryIterator<V> {
            ValueIterator(Entry<K,V> first) {
            super(first);
        }
        public V next() {
            return nextEntry().value;
        }
    }
    /**
     * PrivateEntryIterator类实现 Iterator接口的hasNext()和remove()方法
     * ValueIterator类实现 Iterator接口实现的next()方法
     */
    abstract class PrivateEntryIterator<T> implements Iterator<T> {
        // 下一节点
        Entry<K,V> next;
        // 上一次返回的节点
        Entry<K,V> lastReturned;
        // 修改次数统计数
        int expectedModCount;
    
        PrivateEntryIterator(Entry<K,V> first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }
    
        // 是否存在下一个节点
        public final boolean hasNext() {
            return next != null;
        }
    
        // 返回下一个节点
        final Entry<K,V> nextEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = successor(e);
            lastReturned = e;
            return e;
        }
    
        // 返回上一节点
        final Entry<K,V> prevEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = predecessor(e);
            lastReturned = e;
            return e;
        }
    
        // 删除当前节点
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // deleted entries are replaced by their successors
            if (lastReturned.left != null && lastReturned.right != null)
                next = lastReturned;
            deleteEntry(lastReturned);
            expectedModCount = modCount;
            lastReturned = null;
        }
    }
    PrivateEntryIterator 类

    TreeMap的entrySet()方法:

     entrySet() 方法返回 TreeMap的键值对的集合:

    /**
     * 通过 new EntrySet() 来实现,返回TreeMap的键值对集合
     */
    public Set<Map.Entry<K,V>> entrySet() {
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }
    
    /**
     * EntrySet是TreeMap的所有键值对组成的集合,它的单位是单个键值对
     */
    class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        // 返回迭代器
        public Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator(getFirstEntry());
        }
    
        // EntrySet中是否包含 键值对Object
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
            Object value = entry.getValue();
            Entry<K,V> p = getEntry(entry.getKey());
            return p != null && valEquals(p.getValue(), value);
        }
    
        // 删除EntrySet中的 键值对Object
        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
            Object value = entry.getValue();
            Entry<K,V> p = getEntry(entry.getKey());
            if (p != null && valEquals(p.getValue(), value)) {
                deleteEntry(p);
                return true;
            }
            return false;
        }
    
        // 返回EntrySet中元素个数
        public int size() {
            return TreeMap.this.size();
        }
    
        // 清空EntrySet
        public void clear() {
            TreeMap.this.clear();
        }
    
        public Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
        }
    }
    
    /**
     * EntryIterator类实现 Iterator接口实现的next()方法
     */
    final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
        EntryIterator(Entry<K,V> first) {
            super(first);
        }
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

    TreeMap实现的Cloneable接口:

    TreeMap实现了Cloneable接口,即实现了clone()方法。
    clone()方法的作用很简单,就是克隆一个TreeMap对象并返回。

    /**
     * 克隆一个TreeMap,并返回Object对象
     */
    public Object clone() {
        TreeMap<K,V> clone = null;
        try {
            clone = (TreeMap<K,V>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    
        // Put clone into "virgin" state (except for comparator)
        clone.root = null;
        clone.size = 0;
        clone.modCount = 0;
        clone.entrySet = null;
        clone.navigableKeySet = null;
        clone.descendingMap = null;
    
        // Initialize clone with our mappings
        try {
            clone.buildFromSorted(size, entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    
        return clone;
    }

    TreeMap实现的Serializable接口:

    TreeMap实现java.io.Serializable,分别实现了串行读取和写入功能:

    • 串行写入函数是writeObject(),它的作用是将TreeMap的“容量和所有的Entry”都写入到输出流中。
    • 串行读取函数是readObject(),它的作用是将TreeMap的“容量和所有的Entry”依次读出。

    readObject() 和 writeObject() 正好是一对,通过它们,我能实现TreeMap的串行传输。

    /**
     * java.io.Serializable的写入函数
     * 将TreeMap的 容量和所有的Entry 都写入到输出流中
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out the Comparator and any hidden stuff
        s.defaultWriteObject();
    
        // Write out size (number of Mappings)
        s.writeInt(size);
    
        // Write out keys and values (alternating)
        for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
            Map.Entry<K,V> e = i.next();
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }
    
    /**
     * java.io.Serializable的读取函数:根据写入方式读出
     * 将TreeMap的 容量和所有的Entry 依次读出
     */
    private void readObject(final java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in the Comparator and any hidden stuff
        s.defaultReadObject();
    
        // Read in size
        int size = s.readInt();
    
        buildFromSorted(size, null, s, null);
    }

    三、TreeMap使用例子

    1.TreeMap常用方法使用Demo:

    import java.util.*;
    
    /**
     * @author nana
     * @date 2019/2/23
     */
    public class TreeMapDemo {
    
        public static void main(String[] args) {
            // 测试常用的API
            testTreeMapOrdinaryAPIs();
    
            // 测试TreeMap导航函数
            testNavigableMapAPIs();
    
            // 测试TreeMap的子Map函数
            testSubMapAPIs();
        }
    
        /**
         * 测试常用的API
         */
        private static void testTreeMapOrdinaryAPIs() {
            // 生成随机数
            Random random = new Random();
    
            // 创建TreeMap实例
            TreeMap treeMap = new TreeMap();
            treeMap.put("one", random.nextInt(10));
            treeMap.put("two", random.nextInt(10));
            treeMap.put("three", random.nextInt(10));
    
            System.out.println("TreeMapDemo.testTreeMapOrdinaryAPIs-Begin");
    
            // 打印TreeMap
            System.out.printf("打印treeMap:\n%s\n", treeMap);;
    
            // 通过Iterator遍历key-value
            Iterator iterator = treeMap.entrySet().iterator();
            System.out.println("通过Iterator遍历key-value:");
            while (iterator.hasNext()) {
                Map.Entry entity = (Map.Entry) iterator.next();
                System.out.printf("%s-%s\n", entity.getKey(), entity.getValue());
            }
    
            // TreeMap的键值对个数
            System.out.printf("TreeMap的键值对个数:%s\n", treeMap.size());
    
            // 是否包含key
            System.out.println("是否包含key:");
            System.out.printf("是否包含key:one-%s\n", treeMap.containsKey("one"));
            System.out.printf("是否包含key:four-%s\n", treeMap.containsKey("four"));
    
            // 删除key对应的键值对
            System.out.println("删除key对应的键值对:");
            treeMap.remove("one");
            System.out.printf("删除key为one的键值对后,treeMap为:\n%s\n", treeMap);
    
            // 清空TreeMap的节点
            System.out.println("清空treeMap的节点:");
            treeMap.clear();
            System.out.printf("%s\n", treeMap.isEmpty() ? "treeMap is empty!" : "treeMap is not empty!");
            System.out.printf("%s\n", treeMap == null ? "treeMap is null!" : "treeMap is not null!");
    
            System.out.println("TreeMapDemo.testTreeMapOrdinaryAPIs-End");
        }
    
        /**
         * 测试TreeMap导航函数
         */
        private static void testNavigableMapAPIs() {
            // 创建TreeMap实例,TreeMap是 NavigableMap接口的实现类
            NavigableMap navigableMap = new TreeMap();
            navigableMap.put("aaa",1);
            navigableMap.put("bbb",2);
            navigableMap.put("ccc",3);
            navigableMap.put("ddd",4);
    
            System.out.println("TreeMapDemo.testNavigableMapAPIs-Begin");
    
            // 打印TreeMap
            System.out.printf("打印navigableMap:\n%s\n", navigableMap);
    
            // 获取第一个key和节点
            System.out.printf("First key:%s\tFirst entry:%s\n", navigableMap.firstKey(), navigableMap.firstEntry());
    
            // 获取最后一个key和节点
            System.out.printf("Last key:%s\tLast entry:%s\n", navigableMap.lastKey(), navigableMap.lastEntry());
    
            // 获取小于/等于 key为bbb 最大的key和节点
            System.out.printf("Key floor before bbb:%s\t%s\n", navigableMap.floorKey("bbb"), navigableMap.floorEntry("bbb"));
    
            // 获取小于 key为bbb 最大的key和节点
            System.out.printf("Key lower before bbb:%s\t%s\n", navigableMap.lowerKey("bbb"), navigableMap.lowerEntry("bbb"));
    
            // 获取大于/等于 key为bbb 最大的key和节点
            System.out.printf("Key ceiling after bbb:%s\t%s\n", navigableMap.ceilingKey("bbb"), navigableMap.ceilingEntry("bbb"));
    
            // 获取大于 key为bbb 最大的key和节点
            System.out.printf("Key higher after bbb:%s\t%s\n", navigableMap.higherKey("bbb"), navigableMap.higherEntry("bbb"));
    
            System.out.println("TreeMapDemo.testNavigableMapAPIs-End");
        }
    
        /**
         * 测试TreeMap的子Map函数
         */
        private static void testSubMapAPIs() {
            // 实例化TreeMap对象
            TreeMap treeMap = new TreeMap();
            treeMap.put("a",1);
            treeMap.put("b",2);
            treeMap.put("c",3);
            treeMap.put("d",4);
    
            System.out.println("TreeMapDemo.testSubMapAPIs-Begin");
    
            // 打印TreeMap
            System.out.printf("打印TreeMap:\n%s\n", treeMap);
    
            // 打印 key为c节点 前的节点(默认不包含c节点)
            System.out.printf("打印 key为c节点 前的节点(默认不包含c节点):%s", treeMap.headMap("c"));
    
            System.out.printf("打印 key为c节点 前的节点(包含c节点):%s\n", treeMap.headMap("c", true));
            System.out.printf("打印 key为c节点 前的节点(不包含c节点):%s\n", treeMap.headMap("c", false));
    
            // 打印 key为c节点 后的节点(默认包含c节点)
            System.out.printf("打印 key为c节点 后的节点(默认包含c节点):%s\n", treeMap.tailMap("c"));
    
            System.out.printf("打印 key为c节点 后的节点(包含c节点)%s\n", treeMap.tailMap("c", true));
            System.out.printf("打印 key为c节点 后的节点(不包含c节点)%s\n", treeMap.tailMap("c", false));
    
            // 打印 key为a与c节点 之间的节点(默认不包含c节点)
            System.out.printf("打印 key为a与c节点 之间的节点(默认包含c节点):\n%s\n", treeMap.subMap("a", "c"));
    
            System.out.printf("打印 key为a与c节点 之间的节点(包含a、c节点):\n%s\n", treeMap.subMap("a", true, "c", true));
            System.out.printf("打印 key为a与c节点 之间的节点(包含a节点):\n%s\n", treeMap.subMap("a", true, "c", false));
            System.out.printf("打印 key为a与c节点 之间的节点(包含c节点):\n%s\n", treeMap.subMap("a", false, "c", true));
            System.out.printf("打印 key为a与c节点 之间的节点(不包含a、c节点):\n%s\n", treeMap.subMap("a", false, "c", false));
    
            // 正序打印TreeMap的key
            System.out.printf("正序打印TreeMap的key:\n%s\n", treeMap.navigableKeySet());
            // 倒序打印TreeMap的key
            System.out.printf("倒序打印TreeMap的key:\n%s\n", treeMap.descendingKeySet());
    
            System.out.println("TreeMapDemo.testSubMapAPIs-End");
        }
    }
    TreeMapDemo
    TreeMapDemo.testTreeMapOrdinaryAPIs-Begin
    打印treeMap:
    {one=2, three=5, two=1}
    通过Iterator遍历key-value:
    one-2
    three-5
    two-1
    TreeMap的键值对个数:3
    是否包含key:
    是否包含key:one-true
    是否包含key:four-false
    删除key对应的键值对:
    删除key为one的键值对后,treeMap为:
    {three=5, two=1}
    清空treeMap的节点:
    treeMap is empty!
    treeMap is not null!
    TreeMapDemo.testTreeMapOrdinaryAPIs-End
    TreeMapDemo.testNavigableMapAPIs-Begin
    打印navigableMap:
    {aaa=1, bbb=2, ccc=3, ddd=4}
    First key:aaa    First entry:aaa=1
    Last key:ddd    Last entry:ddd=4
    Key floor before bbb:bbb    bbb=2
    Key lower before bbb:aaa    aaa=1
    Key ceiling after bbb:bbb    bbb=2
    Key higher after bbb:ccc    ccc=3
    TreeMapDemo.testNavigableMapAPIs-End
    TreeMapDemo.testSubMapAPIs-Begin
    打印TreeMap:
    {a=1, b=2, c=3, d=4}
    打印 key为c节点 前的节点(默认不包含c节点):{a=1, b=2}打印 key为c节点 前的节点(包含c节点):{a=1, b=2, c=3}
    打印 key为c节点 前的节点(不包含c节点):{a=1, b=2}
    打印 key为c节点 后的节点(默认包含c节点):{c=3, d=4}
    打印 key为c节点 后的节点(包含c节点){c=3, d=4}
    打印 key为c节点 后的节点(不包含c节点){d=4}
    打印 key为a与c节点 之间的节点(默认包含c节点):
    {a=1, b=2}
    打印 key为a与c节点 之间的节点(包含a、c节点):
    {a=1, b=2, c=3}
    打印 key为a与c节点 之间的节点(包含a节点):
    {a=1, b=2}
    打印 key为a与c节点 之间的节点(包含c节点):
    {b=2, c=3}
    打印 key为a与c节点 之间的节点(不包含a、c节点):
    {b=2}
    正序打印TreeMap的key:
    [a, b, c, d]
    倒序打印TreeMap的key:
    [d, c, b, a]
    TreeMapDemo.testSubMapAPIs-End
    TreeMapDemo 运行结果

    2.TreeMap遍历使用Demo:

    import org.springframework.util.StringUtils;
    
    import java.util.*;
    
    /**
     * @author nana
     * @date 2019/2/23
     */
    public class TreeMapIteratorTest {
    
        public static void main(String[] args) {
            // 创建treeMap对象
            TreeMap treeMap = treeMapTest();
    
            // 通过entrySet()遍历TreeMap的节点
            iteratorTreeMapByEntrySet(treeMap);
            // 通过keySet()遍历TreeMap的节点
            iteratorTreeMapByKeySet(treeMap);
            // 遍历TreeMap的value
            iteratorTreeMapByValue(treeMap);
        }
    
        /**
         * 创建treeMap对象
         * @return
         */
        private static TreeMap treeMapTest() {
            String key = null;
            int keyValue = 0;
            Integer value = null;
            Random random = new Random();
            TreeMap treeMap = new TreeMap();
            int i = 0;
            while (i < 6) {
                // 随机获取[0,50)的整数
                keyValue = random.nextInt(50);
                key = String.valueOf(keyValue);
                value = random.nextInt(10);
                // 添加到treeMap中
                treeMap.put(key, value);
                i++;
            }
            return treeMap;
        }
    
        /**
         * 通过entrySet()遍历TreeMap的节点
         */
        private static void iteratorTreeMapByEntrySet(TreeMap treeMapTest) {
            if (StringUtils.isEmpty(treeMapTest)) {
                return;
            }
            // 遍历TreeMap
            Iterator iterator = treeMapTest.entrySet().iterator();
            System.out.println("通过entrySet()遍历TreeMap的节点:");
            while (iterator.hasNext()) {
                Map.Entry entry = (Map.Entry) iterator.next();
                System.out.printf("%s-%s\t", entry.getKey(), entry.getValue());
            }
        }
    
        /**
         * 通过keySet()遍历TreeMap的节点
         */
        private static void iteratorTreeMapByKeySet(TreeMap treeMapTest) {
            if(StringUtils.isEmpty(treeMapTest)) {
                return;
            }
            String key = null;
            Integer value = null;
            Iterator iterator = treeMapTest.keySet().iterator();
            System.out.println("\n通过keySet()遍历TreeMap的节点:");
            while (iterator.hasNext()) {
                key = (String) iterator.next();
                value = (Integer) treeMapTest.get(key);
                System.out.printf("%s-%s\t", key, value);
            }
        }
    
        /**
         * 遍历TreeMap的value
         */
        private static void iteratorTreeMapByValue(TreeMap treeMapTest) {
            if (treeMapTest == null) {
                return;
            }
            Collection collection = treeMapTest.values();
            Iterator iterator = collection.iterator();
            System.out.println("\n遍历TreeMap的value:");
            while (iterator.hasNext()) {
                System.out.printf("%s\t", iterator.next());
            }
        }
        
    }
    TreeMapIteratorTest
    通过entrySet()遍历TreeMap的节点:
    19-0    2-7    20-1    22-0    34-3    
    通过keySet()遍历TreeMap的节点:
    19-0    2-7    20-1    22-0    34-3    
    遍历TreeMap的value:
    0    7    1    0    3    
    TreeMapIteratorTest 运行结果

    转载于:https://www.cnblogs.com/nananana/p/10426377.html

    展开全文
  • TreeMap的底层实现

    千次阅读 2018-06-04 11:23:12
    TreeMap的基本概念:· TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。该集合最重要的特点就是可排序,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体...
  • 首先简单介绍下,这几种map的应用场景: ...TreeMap 插入数据后,对键值进行排序,内部是通过红黑树实现的; HashTable 与HashMap的功能相同,区别有两点: 1.HashTable是线程安全的,即某一时刻只允许一...
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    待整理: File、递归 字节流、字节缓冲流 编码表、编码方式、转换流、序列化、序列化流、打印流、commons-io 网络编程 网络概述、网络模型 Socket原理机制 UDP TCP/IP 协议、OSI 七层协议、HTTP、HTTP2.0、HTTPS ...
  • 本章节主要分析红黑树的“插入算法”和“获取算法”,也就是put()方法和get()方法的底层实现。 在学习TreeMap的put()方法之前,我们首先应该创建一个叶子节点Entry类,叶子节点Entry是TreeMap的内部类,它有几个重要...
  • java TreeMap详解

    千次阅读 2019-05-23 11:24:31
    TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。 TreeMap继承于AbstractMap,所以它是一个Map,即一个key-value集合。 TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    AIO:Asynchronous IO 是 NIO 的升级,也叫 NIO2,实现了异步非堵塞 IO ,异步 IO 的操作基于事件和回调机制。 17. Files的常用方法都有哪些? Files.exists():检测文件路径是否存在。 Files.createFile():创建...
  • 我们前面知道,Map接口的实现类有HashMap、TreeMap、HashTable、Properties等等实现类。 前面详细分析并且实现过的HashMap就是最常用的了。TreeMap和HashMap对于调用者来说是没有区别的,HashMap效率相比之下比...
  •  TreeMap和TreeSet算是java集合类里面比较有难度的数据结构。和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面...
  • HashMap HashMap 是一个散列表,它存储的内容是键值对(key-...由于Hashtable是个古老的Map实现类(从Hashtable的命名规范就可以看出,t没有大写,并不是我写错了),需要方法比较繁琐,不符合Map接口的规范。但是H...
  • TreeMap的排序

    2020-11-14 12:27:02
    当然,也可以自定义排序规则:要实现Comparator接口。 用法简单,先看下下面的demo public class SortDemo { public static void main(String[] args) { System.out.println("---------------- 默认 排序结果-...
  • TreeMap和TreeSet的深入理解

    千次阅读 2018-04-06 10:28:04
    转载:http://shmilyaw-hotmail-com.iteye.com/blog/1836431简介 TreeMap和TreeSet算是java集合类里面比较有难度的数据结构。和普通的HashMap不一样,...虽然在元素的存取方面TreeMap并不占优,但是它内部的元素...
  • 2020最新Java常见面试题及答案

    万次阅读 多人点赞 2019-10-26 15:53:35
    如何决定使用 HashMap 还是 TreeMap? 23.说一下 HashMap 的实现原理? 24.说一下 HashSet 的实现原理? 25.ArrayList 和 LinkedList 的区别是什么? 26.如何实现数组和 List 之间的转换? 27.ArrayList 和 Vector ...
  • TreeMap 排序

    万次阅读 2018-11-05 10:07:08
    当然,也可以自定义排序规则:要实现Comparator接口。 用法简单,先看下下面的demo public class SortDemo { public static void main(String[] args) { System.out.println("-------...
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。 List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来...
  • TreeMap

    万次阅读 2018-07-29 11:00:05
    TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。该集合最重要的特点就是可排序,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用...
  • 本篇文章来讲述一下基于红黑树实现的Map—TreeMap。之前介绍HashMap时,我们都知道,HashMap键值对之间没有特定的顺序。结合之前讲的红黑树特点,我们也可以猜测到,TreeMap是可以保证键值对之间的顺序的。 ...
  • java面试题2019_java面试题及答案_java面试题库

    千次阅读 多人点赞 2019-05-16 09:31:30
    java中实现多态的机制是什么? 75、 .super.getClass()方法调用? 76、 请写出你最常见到的5个runtime exception? 77、 当一个线程进入一个对象的一个synchronized方法后,其它线程是否可进入此对象的其它方法? ...
  • Java知识体系最强总结(2020版)

    千次阅读 多人点赞 2020-03-07 08:35:51
    本人从事Java开发已多年,平时有...https://blog.csdn.net/ThinkWon/article/details/102574293 5 LinkedList(JDK1.8)源码解析 https://blog.csdn.net/ThinkWon/article/details/102573923 6 TreeMap(JDK1.8)源码解析 ...
  • HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键(HashMap最多只允许一条记录的键为null,允许多条记录的值为null。)。此类不保证映射的顺序,特别是它不保证该...
  • 今天我们要来啃Map体系中的硬骨头了TreeMap。这个名字听着好熟悉,是的我们在介绍HashMap的时候说过,当链表的长度大于8的时候,链表将会被转换为一个TreeNode。TreeNode使用红黑树的方式来组织数据,TreeMap同理。...
  • Java集合之TreeMap详解

    千次阅读 2018-06-15 13:38:50
    简介TreeMap是一个有序的key-value集合,它是通过红黑树实现的。它的每一个元素是一个key-value对,TreeMap类声明如下:public class TreeMap&lt;K,V&gt; extends AbstractMap&lt;K,V&gt; ...
  • TreeMap 排序 字典码排序

    千次阅读 2018-04-02 10:52:22
    一、TreeMapTreeMap 默认排序规则:按照key的字典顺序来排序(升序)当然,也可以自定义排序规则:要实现Comparator接口。用法简单,先看下下面的demopublic class SortDemo { public static void main(String[] ...
  • Java的TreeMap和HashMap的介绍和使用

    千次阅读 2018-02-12 15:04:23
    1. TreeMap的介绍和使用 第1部分 TreeMap介绍 TreeMap 简介 TreeMap 是一个有序的key-value集合,它是通过红黑树实现的...TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合
  • TreeMap源码解析

    2019-08-01 19:39:27
    第一个为默认构造方法,如果使用默认构造方法,要求Map中的键实现Comparabe接口,TreeMap内部进行各种比较时会调用键的Comparable接口中的compareTo方法。 第二个接受一个比较器对象comparator,如果comparator不...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,880
精华内容 10,352
关键字:

treemap实现机制