Java提高——常见Java集合实现细节（2）

你的名字 2022-05-27 09:45 140阅读 0赞

##### TreeMap和TreeSet #####

HashSet的底层依赖于HashMap的实现。

TreeSet底层采用一个NavigableMap来保存TreeSet集合的元素。实际上由于NavigableMap只是一个接口，因此底层依然使用TreeMap来包含Set集合中的所有元素。

TreeSet源码：

public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable
    {
        /** * 使用NavigableMap的key来保存Set集合的元素 */ private transient NavigableMap<E,Object> m;
    
        // 使用一个PRENSENT作为Map集合的所有value
        private static final Object PRESENT = new Object();
    
        /** * 包含访问权限的构造器，以指定NavigableMap对象创建Set集合 */ TreeSet(NavigableMap<E,Object> m) {
            this.m = m;
        }
    
        /** * 以自然排序的方式创建一个新的TreeMap，根据该TreeSet创建一个TreeSet * 根据该TreeMap的key来保存Set集合的元素 */ public TreeSet() {//①
            this(new TreeMap<E,Object>());
        }
    
        /** * 以定制排序的方式创建一个新的TreeMap，根据该TreeSet创建一个TreeSet * 使用该TreeMap的key保存Set集合的元素  */ public TreeSet(Comparator<? super E> comparator) {//②
            this(new TreeMap<>(comparator));
        }
    
     public TreeSet(Collection<? extends E> c) {
         //调用①号构造器创建一个TreeSet，底层以TreeMap保存集合元素
         this();
         //向TreeSet中添加Collection集合c里的所有元素
        addAll(c);
        }
    
       public TreeSet(SortedSet<E> s) {
         //以②号构造器创建一个TreeSet，底层以TreeMap保存集合元素
         this(s.comparator());
         //向TreeSet中添加SortedSet集合s中的所有s元素
        addAll(s);
        }
    
        /** * 下面的实现都是直接调用TreeMap的方法来提供实现 */ public Iterator<E> iterator() {
            return m.navigableKeySet().iterator();
        }
     public Iterator<E> descendingIterator() {
            return m.descendingKeySet().iterator();
        }
     public NavigableSet<E> descendingSet() {
            return new TreeSet<>(m.descendingMap());
        }
     public int size() {
            return m.size();
        }
    
       public boolean isEmpty() {
            return m.isEmpty();
        }
     public boolean contains(Object o) {
            return m.containsKey(o);
        }
     public boolean add(E e) {
            return m.put(e, PRESENT)==null;
        }
     public boolean remove(Object o) {
            return m.remove(o)==PRESENT;
        }
     public void clear() {
            m.clear();
        }
     public  boolean addAll(Collection<? extends E> c) {
            // Use linear-time version if applicable
            if (m.size()==0 && c.size() > 0 &&
                c instanceof SortedSet &&
                m instanceof TreeMap) {
           //把c强制转换为SortedSet集合
           SortedSet<? extends E> set = (SortedSet<? extends E>) c;
           //把m集合强制转化为TreeMap集合
          TreeMap<E,Object> map = (TreeMap<E, Object>) m;
                Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
                Comparator<? super E> mc = map.comparator();
           //如果cc和mc两个Comparator相等
           if (cc==mc || (cc != null && cc.equals(mc))) {
                    map.addAllForTreeSet(set, PRESENT);
                    return true;
                }
            }
        //直接调用父类的addAll方法来实现
        return super.addAll(c);
        }

从源码来看，TreeSet的大部分方法都是直接调用TreeMap的方法来实现的。

对于TreeMap而言，它采用一种被称为“红黑树”的排序二叉树来保存Map中的每个Entry——每个Entry被当作“红黑树”的一个结点。

通过这种方式，TreeMap中的所有key总是由小到大的排列。

![70][]

TreeMap的put方法源码：该方法实现了将Entry放入TreeMap的Entry链，并保证该Entry链处于有序状态。

public V put(K key, V value) {
       //先以t保存链表的root结点
       Entry<K,V> t = root;
       //如果t==null，则表明是一个空链表，即该TreeMap里没有任何Entry
       if (t == null) {
            compare(key, key); // type (and possibly null) check
        //将新的key-value创建一个Entry，并将该Entry作为root
            root = new Entry<>(key, value, null);
            //设置map集合的size为1，代表包含一个Entry
        size = 1;
         //记录修改次数
        modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
       //如果cpr不为null，即表明采用定制排序
       if (cpr != null) {
            do {
           //使用parent上次循环后的t所引用的Entry
           parent = t;
           //拿新插入的key和t的key进行比较
           cmp = cpr.compare(key, t.key);
           //如果新插入的key小于t的key，t等于t的左边结点
           if (cmp < 0)
                    t = t.left;
           //如果新插入的key大于t的key，t等于t的右边结点
           else if (cmp > 0)
                    t = t.right;
                else
            //如果两个key相等，新value覆盖原来的value，并返回原来的value
             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所引用的Entry
           parent = t;
           //拿新插入的key和t的key进行比较
           cmp = k.compareTo(t.key);
           //如果新插入的key小于t的key，t等于t的左边结点
           if (cmp < 0)
                    t = t.left;
            //如果新插入的key大于t的key，t等于t的右边节点
           else if (cmp > 0)
                    t = t.right;
                else
            //如果两个key相等，新的value覆盖原有的value，并返回原有的value
             return t.setValue(value);
            } while (t != null);
        }
       //将新插入的节点作为parent的子节点
       Entry<K,V> e = new Entry<>(key, value, parent);
       //如果新插入的key小于parent的key，则e作为parent的左子节点
       if (cmp < 0)
            parent.left = e;
       //如果新插入的key大于parent的key，则e作为parent的右子节点
       else
            parent.right = e;
       //修复红黑树
      fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

“排序二叉树”：每当程序希望添加新的节点时，总时从树的更节点开始比较，即将根节点当成当前节点。如果新增节点大于当前节点且当前节点的右子节点存在，则以右子节点作为当前节点;如果新增节点小于当前节点且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则新增节点覆盖当前节点，并结束循环——直到找到某个节点的左、右子节点不存在，将新节点添加为该节点的子节点。

TreeMap根据key取出value时：

public V get(Object key) {
       //根据key取出对应的Entry
       Entry<K,V> p = getEntry(key);
         //返回该Entry所包含的value
       return (p==null ? null : p.value);
    }

final Entry<K,V> getEntry(Object key) {
        //如果comparator不为null，表明程序采用定制排序
        if (comparator != null)
         //调用getEntryUsingComparator方法取出对应的key
         return getEntryUsingComparator(key);
       //如果key形参的值为null，抛出NullPointerException异常
       if (key == null)
            throw new NullPointerException();
       //将key强制转为Comparable实例
       Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;//从树的根节点开始
        while (p != null) {
         //拿key同当前节点的key进行比较
         int cmp = k.compareTo(p.key);
            if (cmp < 0)//如果key小于当前节点的key，向“左子树”搜索
                p = p.left;
            else if (cmp > 0)//如果key大于当前节点的key，向“右子树”搜索
                p = p.right;
         //如果即不大于也不小于，就找到了目标Entry
           else
                return p;
        }
        return null;
    }

TreeMap中comparator != null，即表明该TreeMap采用了定制排序。在采用定制排序的方式下，TreeMap采用了getEntryUsingComparator方法来根据key获取Entry，源代码如下：

final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;
       //获取TreeMap的comparator
       Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;//从根节点开始
            while (p != null) {
           //拿key与当前节点的key进行比较
           int cmp = cpr.compare(k, p.key);
                if (cmp < 0)//如果key小于当前节点的key，向“左子树”搜索
                    p = p.left;
                else if (cmp > 0)//如果key大于当前节点的key，向“右子树”搜索
                    p = p.right;
                else//如果不大不小就是找到了目标Entry
                    return p;
            }
        }
        return null;
    }

getEntry和getEntryUsingComparator的实现思路是完全类似的，只是前者对自然排序的TreeMap获取有效，后者对定制排序的TreeMap有效。

TreeMap本质上就是一颗“红黑树“，而TreeMap的每个Entry就是该红黑树的一个节点。

[70]: /images/20220527/70fcda0e03a745988931c75e0257bdef.png

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java基础汇总（十九）——Java集合细节

一、初始容量（ArrayList） ArrayList每次新增一个元素，就会检测ArrayList的当前容量是否已经到达临界点，如果到达临界点则会扩容1.5倍 A

港控/mmm°/ 2024年04月03日 09:36/ 0 赞/ 54 阅读

相关 java提高篇集合

集合 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

「爱情、让人受尽委屈。」/ 2023年10月10日 10:01/ 0 赞/ 15 阅读

相关 java集合提高

来源：chenssy 链接：cnblogs.com/chenssy/p/3495238.html 出处： [http://www.cnblogs.com/chenssy/]

忘是亡心i/ 2022年09月25日 02:22/ 0 赞/ 98 阅读

相关 Java提高（三）集合

引用：http://blog.csdn.net/chenssy/article/details/17732841 在编写java程序中，我们最常用的除了八种基本数据类型，S

灰太狼/ 2022年05月31日 00:09/ 0 赞/ 147 阅读

相关 Java提高——常见Java集合实现细节（3）

Map和List map的values方法 map集合是一个关联数组，它包含两组值：一组是key组成的集合，因为map集合的key不允许重复，且map不会保存

向右看齐/ 2022年05月27日 09:59/ 0 赞/ 104 阅读

相关 Java提高——常见Java集合实现细节（2）

TreeMap和TreeSet HashSet的底层依赖于HashMap的实现。 TreeSet底层采用一个NavigableMap来保存TreeSet集合的元素。实际

你的名字/ 2022年05月27日 09:45/ 0 赞/ 141 阅读

相关 Java提高——常见Java集合实现细节（1）

![70][] 集合关

╰半夏微凉°/ 2022年05月27日 06:53/ 0 赞/ 126 阅读

相关 Java面试常见问题——Java 中常见集合

Java 中常见集合集合这方面的考察相当多，这部分是面试中必考的知识点。 01. 说说常见的集合有哪些吧？答： Map 接口和 Collection 接口

た入场券/ 2022年05月22日 06:54/ 0 赞/ 210 阅读

相关 Java集合--Queue(Java中实现2)

Java集合–Queue(Java中实现2) 1.1 Deque源码（基于JDK1.7.0\_45）本票中，我们来看看Deque源码，在Queue基础上，又增加了

布满荆棘的人生/ 2022年03月16日 10:44/ 0 赞/ 145 阅读

相关 Java语法细节（2）

1、逻辑运算符 &和&&，|和||的区别 &&：和&的结果是一样的，但运算过程有区别 &&：只要左边结果为假，就不再执行右边的，结果为假 & ：无论左边的运算结果是什

今天药忘吃喽~/ 2022年01月11日 01:23/ 0 赞/ 167 阅读