源码阅读(27)：Java中主要的Set结构——LinkedHashSet、TreeSet等结构

傷城~ 2023-07-10 12:58 28阅读 0赞

（接上文《[源码阅读(26)：Java中主要的Set结构——HashSet][26_Java_Set_HashSet]》）

# 1、概述 #

和HashSet类似，Java中另外两个主要的Set集合结构也做了这样依赖结构，既是LinkedHashSet集合继承了HashSet，并实际应用HashSet集合中构造函数，完成实例化；TreeSet集合内部结构依赖于TreeMap集合，也就是说TreeSet内部数据结构同样是红黑树。

# 2、LinkedHashSet集合 #

LinkedHashSet集合的主要继承体系的示意图已经在上文中给出，这里就不再进行赘述了。LinkedHashSet集合的代码非常简单基本上可以说是java集合框架中（Java Collections Framework ）代码最简单的几个类之一——整个类加注释一共不到200行。它之所以那么简单是因为它的功能全部依靠LinkedHashMap容器进行工作，且没有提供除此之外额外的特殊功能。

## 2.1、LinkedHashSet集合的构造函数 ##

首先我们介绍LinkedHashSet集合的构造函数，相关代码片段如下所示

public class LinkedHashSet<E>
        extends HashSet<E>
        implements Set<E>, Cloneable, java.io.Serializable {
        
      // ......
      
      // 可以看到LinkedHashSet集合中所有的构造函数都调用了父类HashSet中
      // HashSet(int initialCapacity, float loadFactor, boolean dummy) 
      // 这个构造函数，这个构造函数也涉及到我们上文中的一个未解决的疑问。
      public LinkedHashSet(int initialCapacity, float loadFactor) {
        
        super(initialCapacity, loadFactor, true);
      }
      
      // 这些构造函数的作用都不在赘述，initialCapacity代表初始化容量
      // loadFactor代表负载因子
      public LinkedHashSet(int initialCapacity) {
        
        super(initialCapacity, .75f, true);
      }
      
      // 初始化容量16，负载因子0.75
      public LinkedHashSet() {
        
        super(16, .75f, true);
      }
    
      public LinkedHashSet(Collection<? extends E> c) {
        
        // 将LinkedHashSet集合的初始化容量设定为当前参照集合“c”的大小的两倍
        // 如果前者小于11，那么设定初始化容量为11
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
      }
      
      // ......
    }

从以上构造函数的代码片段我们可以知道，要了解LinkedHashSet集合的各种构造函数，只需要了解其父类HashSet中的HashSet(int initialCapacity, float loadFactor, boolean dummy)构造函数，为了便于介绍，我们这里再给出相关代码片段：

public class HashSet<E>
      extends AbstractSet<E>
      implements Set<E>, Cloneable, java.io.Serializable {
        
      
      // ......
      HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
      }
      // ......
    }

*  该构造函数一共有三个参数，最后一个参数“dummy”中文含义是“虚假的”，而且从代码中我们也可以看出这个参数实际上并没有被使用。这是因为在HashSet集合的构造函数中，已经存在了HashSet(int initialCapacity, float loadFactor)这个构造函数，且后者实例化了一个HashMap容器。为了区别开来，实例化LinkedHashMap容器的构造函数才定义了三个参数。
 *  为什么LinkedHashSet集合并没有像HashSet集合那样直接依赖LinkedHashMap容器，而是选择继承HashSet集合后，再在HashSet集合内部通过一个“包保护”特性的构造函数进行LinkedHashMap容器的初始化呢？这主要是为了充分利用HashMap容器和LinkedHashMap容器的继承关系，以及HashSet集合中已经封装的方法。

// LinkedHashSet是HashSet的子类
    public class HashSet<E>
      extends AbstractSet<E>
      implements Set<E>, Cloneable, java.io.Serializable {
        
      
      // 当使用以下构造时，LinkedHashSet内部依赖的Map实现就会变成LinkedHashMap
      // 而由于map属性本身的访问安全性使用private关键字进行修饰
      // 所以LinkedHashSet不能直接为map赋值，只能在HashSet中描述一个构造函数，然后再在LinkedHashSet中进行引用
      private transient HashMap<E,Object> map;  
     
      HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
      }
    }

## 2.2、LinkedHashSet集合的主要方法 ##

由于LinkedHashSet继承了HashSet集合，且由此沿用了LinkedHashMap容器的所有特性（如果读不懂这句话，说明上一小节没有看明白，还需要重温一下）。所以LinkedHashSet集合无需额外实现任何其他的方法——因为LinkedHashMap容器已经完成了所有需要完成的功能。

当然有个例外，就是LinkedHashSet集合中被覆盖的spliterator()方法，该方法在JDK 1.8+版本中被定义，用来返回一个可分割容器的（并行）迭代器。相关知识我们会在后文中进行说明。

# 3、TreeSet集合 #

TreeSet集合是一个基于红黑树的有序集合，它内部功能依赖于TreeMap容器进行工作（后者的工作原理可参见文章《[源码阅读(21)：Java中其它主要的Map结构——TreeMap容器（1）][21_Java_Map_TreeMap_1]》） 。TreeSet的主要继承体系如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]  
TreeSet集合充分利用了TreeMap容器中Key键特性，实现了TreeSet集合中没有“相同”的元素，以及它基于红黑树工作的特定。以下是TreeSet集合的简单实用示例：

// ......
    // 请注意实例代码中，向TreeSet集合放入了java.lang.String类的实例
    // java.lang.String类实现了Comparable接口，所以集合中各元素的比较操作将使用
     // String.compareTo(String anotherString)方法进行比较
     TreeSet<String> treeSet = new TreeSet<>();
     treeSet.add("b");
     treeSet.add("d");
     treeSet.add("a");
     treeSet.add("c");
     treeSet.add("1");
     treeSet.add("3");
     treeSet.add("5");
     treeSet.add("4");
     treeSet.add("2");
     
     // 进行遍历
     Iterator<String> itr = treeSet.iterator();
     while(itr.hasNext()) {
        
       String item = itr.next();
       System.out.println(String.format("item = %s" , item));
     }
     
     // ========以上代码的输出结果为
     /*
      * item = 1
      * item = 2
      * item = 3
      * item = 4
      * item = 5
      * item = a
      * item = b
      * item = c
      * item = d
      * */
    // ....

## 3.1、TreeSet集合的构造函数 ##

这里先我们介绍TreeSet集合的构造函数，相关代码片段如下所示：

public class TreeSet<E> extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable, java.io.Serializable {
        
      
      // ......
      /**
       * 这是TreeSet集合中依赖的Map结构，看似是一个抽象的NavigableMap
       * 实则根据后续的代码分析就可以知道，它是一个TreeMap容器
       * The backing map.
       */
      private transient NavigableMap<E,Object> m;
      
      // ......
      /**
       * 这个构造函数的访问安全设定为“包保户”级别，外部调用者无法直接使用
       * 该构造函数接受一个NavigableMap对象，NavigableMap是大多数Map容器的父级接口，它将成为TreeSet集合内部所依赖的Map容器结构。
       * Constructs a set backed by the specified navigable map.
       */
      TreeSet(NavigableMap<E,Object> m) {
        
        this.m = m;
      }
    
      // 默认的TreeSet集合构造函数，其内部将TreeSet集合依赖的Map容器初始化为TreeMap。
      public TreeSet() {
        
        this(new TreeMap<E,Object>());
      }
    
      // 该构造函数将允许传入一个比较器，并为内部的TreeMap容器导入这个比较器
      public TreeSet(Comparator<? super E> comparator) {
        
        this(new TreeMap<>(comparator));
      }
    
      // 该构造函数允许传入一个其他种类的结合，并在内部完成TreeMap容器的初始化后
      // 将传入集合（c）的元素存入TreeSet容器中
      public TreeSet(Collection<? extends E> c) {
        
        this();
        addAll(c);
      }
    
      // 该构造函数类似于上一个构造函数，不同的是它允许传入的是一个支持有序排列的Set集合
      public TreeSet(SortedSet<E> s) {
        
        this(s.comparator());
        addAll(s);
      }
      // ......
    }

## 3.2、TreeSet集合中的主要方法 ##

### 3.2.1、那些直接封装的方法 ###

由于TreeSet集合的内部依赖了TreeMap容器工作，所以在前者提供的大部分方法中直接调用了TreeMap的对应方法（以NavigableMap抽象类的对象实例进行表达），我们首先来看看：

public class TreeSet<E> extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable, java.io.Serializable {
        
      
      /**
       * The backing map.
       */
      private transient NavigableMap<E,Object> m;
      
      // Dummy value to associate with an Object in the backing Map
      private static final Object PRESENT = new Object();  
    
      // ......
      // 向TreeSet集合中添加一个元素
      // 实际上就是调用了TreeMap的put方法，其中的value参数采用了一个常量PRESENT
      public boolean add(E e) {
        
        return m.put(e, PRESENT)==null;
      }
      
      // 清理TreeSet集合中的所有元素
      // 实际上就是调用了TreeMap的clear方法
      public void clear() {
        
        m.clear();
      }
      
      // 清理TreeSet集合中的指定元素
      // 实际上就是调用了TreeMap的remove方法
      public boolean remove(Object o) {
        
        return m.remove(o)==PRESENT;
      }
      
      // 该方法在TreeSet集合中，基于指定的fromElement元素和指定的toElement元素寻找一个子集
      // 如果找到了这个子集，则构造一个新的TreeSet集合进行返回。
      // 其中fromInclusive参数表示返回的子集是否包括起始元素；toInclusive参数表示返回的子集是否包括结束元素
      public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement,   boolean toInclusive) {
        
        return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement,   toInclusive));
      }
      
      // 该方法在TreeSet集合中，从集合的第一个元素开始，基于指定的toElement元素截止，寻找一个子集
      // inclusive参数代表子集是否包括了指定的元素
      public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        
        return new TreeSet<>(m.headMap(toElement, inclusive));
      }
      
      // 以及诸如这样的返回TreeSet集合当前第一个元素的方法
      public E first() {
        
        return m.firstKey();
      }
      // ......
    }

### 3.2.2、那些被修改的方法 ###

在TreeSet集合中，还有一部分原由TreeMap提供的，但是由TreeSet集合进行了“调整”的方法，例如：

public class TreeSet<E> extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable, java.io.Serializable {
        
    
      // ......
      public  boolean addAll(Collection<? extends E> c) {
        
        // Use linear-time version if applicable
        // 如果当前传入的集合有元素，并且当前传入的集合是一个实现了SortedSet接口的有序集合
        if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) {
        
          SortedSet<? extends E> set = (SortedSet<? extends E>) c;
          TreeMap<E,Object> map = (TreeMap<E, Object>) m;
          Comparator<?> cc = set.comparator();
          Comparator<? super E> mc = map.comparator();
          // 且当前TreeSet集合的对比器和传入的集合c使用的对比器“相同”
          // 请注意这个“相同”的定义，除了可以是两者的内存地址相等，还可以是通过equals方法得到了true的返回值
          // 在这些条件都满足的情况下，就是用TreeMap的addAllForTreeSet方法进行元素添加
          if (cc==mc || (cc != null && cc.equals(mc))) {
        
            map.addAllForTreeSet(set, PRESENT);
            return true;
          }
        }
        
        // 否则进行集合“c”中的元素一个一个的添加操作
        return super.addAll(c);
      }
      // ......
    
    }

### 3.2.3、TreeSet集合的序列化方法 ###

和java集合框架中大多数集合/容器的序列化思路一样，为了尽可能保证不进行多余的序列化/反序列化处理，TreeSet集合也重新定义了序列化/反序列化处理过程，代码片段如下所示：

public class TreeSet<E> extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable, java.io.Serializable {
        
      
      // ......
      // 该方法定义了TreeSet的序列化过程
      private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
        
        // Write out any hidden stuff
        // 这个方法之前介绍过，既是将对象中各种普通属性（没有标识transient关键字）进行序列化
        s.defaultWriteObject();
        // 将TreeSet集合中使用的TreeMap对象的比较器进行序列化
        // Write out Comparator
        s.writeObject(m.comparator());
        // Write out size
        // 将当前TreeSet集合的大小（size）属性进行序列化
        s.writeInt(m.size());
        // Write out all elements in the proper order.
        // 将TreeSet集合中的有序元素依次进行序列化
        for (E e : m.keySet())
          s.writeObject(e);
      }
      
      // 该方法定义了TreeSet的反序列化过程
      private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        
        // Read in any hidden stuff
        // 通过该方法，将没有标识transient关键字的普通属性进行反序列化
        s.defaultReadObject();
        // Read in Comparator
        @SuppressWarnings("unchecked")
        // 读取当前的比较器对象，并赋予给这个新的TreeSet集合，
        Comparator<? super E> c = (Comparator<? super E>) s.readObject();
        // Create backing TreeMap
        // 为这个TreeSet集合初始化其内部依赖使用的TreeMap容器
        TreeMap<E,Object> tm = new TreeMap<>(c);
        m = tm;
        // Read in size
        // 读取反序列化前集合的大小值，并基于这个值
        // 通过TreeMap容器中提供的readTreeSet方法，依次进行每个元素的反序列化操作
        int size = s.readInt();
        tm.readTreeSet(size, s, PRESENT);
      }
      // ......
    }

# 3、总述 #

总的来说Java提供的多种原生Set集合其实现都非常简单，都是基于对应的Map集合完成其功能。例如TreeSet内部依赖TreeMap进行工作，HashSet集合内部依赖TreeMap进行工作。所以只需要认证理解阅读本专题之前介绍的多种Map容器，就不难理解这些Set集合了。这也是为什么本专题只花费很少的篇幅就介绍了多种Set集合。

截止这篇文章，JDK1.8中主要的List集合、Queue集合、Map键值对结构和Set集合就介绍完了，从下一片文章开始，我们将进入Java线程、并发特点，以及线程安全的集合框架的讲解。

[26_Java_Set_HashSet]: https://blog.csdn.net/yinwenjie/article/details/104506500
[21_Java_Map_TreeMap_1]: https://blog.csdn.net/yinwenjie/article/details/103230856
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200314203554220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ==,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

相关源码阅读(27)：Java中主要的Set结构——LinkedHashSet、TreeSet等结构

（接上文《[源码阅读(26)：Java中主要的Set结构——HashSet][26_Java_Set_HashSet]》） 1、概述和HashSet类似，Java中另

傷城~/ 2023年07月10日 12:58/ 0 赞/ 29 阅读

相关源码阅读(26)：Java中主要的Set结构——HashSet

1、概述在全面理解了HashMap结构后，理解HashSet数据结构也就足够简单了——HashSet内部就是对HashMap数据结构的依赖。HashMap结构的Key就

柔情只为你懂/ 2023年07月08日 09:17/ 0 赞/ 43 阅读

相关源码阅读(25)：Java中主要的Set结构——概述

1、概述从本专题的第15篇文章开始一直到本专题的第24篇文章截止，我们花了大量的篇幅介绍Java中的Map接口以及实现该接口的多个重要容器，其中又以介绍HashMap容

╰+攻爆jí腚メ/ 2023年06月27日 08:48/ 0 赞/ 39 阅读

相关源码阅读(24)：Java中其它主要的Map结构——LinkedHashMap容器（下）

（接上文《[源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）][23_Java_Map_LinkedHashMap]》） 2、Lin

落日映苍穹つ/ 2023年06月23日 14:29/ 0 赞/ 42 阅读

相关源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）

1、概述 LinkedHashMap容器是Java容器框架中从很早的版本就开始提供的（JDK 1.4+），该容器又被这样认为：“LinkedHashMap = HashM

谁借莪１个温暖的怀抱￠/ 2023年06月21日 07:16/ 0 赞/ 88 阅读

相关源码阅读(22)：Java中其它主要的Map结构——TreeMap容器（2）

（接上文《[源码阅读(21)：Java中其它主要的Map结构——TreeMap容器（1）][21_Java_Map_TreeMap_1]》）（注：笔者翻阅了一下网络上的相

男娘i/ 2023年06月18日 06:57/ 0 赞/ 19 阅读

相关源码阅读(21)：Java中其它主要的Map结构——TreeMap容器（1）

(接上文《[源码阅读(20)：Java中主要的Map结构——HashMap容器（下2）][20_Java_Map_HashMap_2]》) 我们通过解读Java自带的各种Ma

小鱼儿/ 2023年06月16日 07:28/ 0 赞/ 37 阅读

相关源码阅读(20)：Java中主要的Map结构——HashMap容器（下2）

（接上文《[源码阅读(19)：Java中主要的Map结构——HashMap容器（下1）][19_Java_Map_HashMap_1]》） 3.4.6、HashMap扩容操

淩亂°似流年/ 2023年06月12日 09:10/ 0 赞/ 34 阅读

相关 IDEA阅读源码查看类图结构

一.前言养成阅读优秀源码的习惯是程序员提升编码能力一个非常有效的方式，优秀的开源框架以及jdk类库的源码都值得阅读和研究。很多人会觉得阅读源码是一个枯燥难懂的过程，但坚

电玩女神/ 2022年04月10日 07:11/ 0 赞/ 482 阅读

相关 Java中主要的List结构

源码阅读(1)：Java中主要的List结构——概述置顶 2019年06月10日 23:44:49 [说好不能打脸][Link 1] 阅读数 629 标签： [java

╰+哭是因爲堅強的太久メ/ 2022年01月15日 02:11/ 0 赞/ 259 阅读