【容器源码篇】Set容器（HashSet，LinkedHashSet，TreeSet的特点）

超、凢脫俗 2024-04-17 06:45 5阅读 0赞

#### 文章目录 ####

*  ⭐容器继承关系
 *   *  🌹Set容器
     *   *  🗒️HashSet源码解析
         *   *  构造方法
             *   *  public HashSet()
                 *  public HashSet(Collection<? extends E> c)
                 *  public HashSet(int initialCapacity, float loadFactor)
                 *  HashSet(int initialCapacity, float loadFactor, boolean dummy)
                 *  public HashSet(int initialCapacity)
             *  常用方法
         *  🗒️LinkedHashSet源码解析
         *   *  构造函数
         *  🗒️TreeSet源码解析
         *   *  构造函数
             *  add方法
             *  addAll方法

![在这里插入图片描述][3befc71d50674a6aa7f40f29a28ce48a.png_pic_center]

## ⭐容器继承关系 ##

![在这里插入图片描述][f266bf60a9394be7996ac003e3d7c328.png]

### 🌹Set容器 ###

Set用于存储不重复元素的集合。Set接口继承自Collection接口，不允许包含重复元素，并且没有指定顺序。常见的Set实现类有HashSet、LinkedHashSet和TreeSet。

#### 🗒️HashSet源码解析 ####

`不允许重复元素`：HashSet不允许存储重复的元素，如果试图向HashSet中添加一个已经存在的元素，那么添加操作将会失败。

`无序性`：HashSet不保证集合中元素的顺序，即元素在集合中没有特定的顺序。具体的遍历顺序取决于元素的哈希码。

基于哈希表：HashSet`内部是通过HashMap来实现的`。HashSet中的元素作为HashMap的key，而value则是一个固定的Object对象。

添加、删除、包含操作的时间复杂度都是O(1)：由于HashSet基于哈希表实现，对于添加、删除和包含操作的时间复杂度都是常数级别的，因此具有很高的性能。

##### 构造方法 #####

###### public HashSet() ######

创建一个空的HashMap，一个空HashMap的默认容量是16，装载因子是0.75  
![在这里插入图片描述][acc6b2f990544d10830ad97da7ef929f.png]

###### public HashSet(Collection<? extends E> c) ######

创建一个包含集合c中所有不重复元素的HashSet集合  
![在这里插入图片描述][be8a1488ddf84535a670a430f08d3b86.png]

###### public HashSet(int initialCapacity, float loadFactor) ######

创建一个具有指定容量和负载因子的HashMap  
![在这里插入图片描述][190d87e06d004cfaa495ed1d386b8bdf.png]

###### HashSet(int initialCapacity, float loadFactor, boolean dummy) ######

创建一个具有指定容量和负载因子的LinkedHashMap，这个包私有构造函数只被LinkedHashSet使用  
![在这里插入图片描述][28d60f882b3b4b39b39259c7d5d69afa.png]

###### public HashSet(int initialCapacity) ######

创建一个具有指定容量的HashMap  
![在这里插入图片描述][2789487e6e254c79b6fd8357ad7aaa31.png]

##### 常用方法 #####

// 返回集合中元素的个数
        public int size() {
        
            return map.size();
        }
    
    	// 返回集合是否为空
        public boolean isEmpty() {
        
            return map.isEmpty();
        }
    	
    	// 返回集合中是否包含指定元素o
        public boolean contains(Object o) {
        
            return map.containsKey(o);
        }
    
    	// 添加指定元素e
    	// 将e作为HashMap的key 常量PRESENT作为所有元素的value
        public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }
    
    	// 移出指定元素o
        public boolean remove(Object o) {
        
            return map.remove(o)==PRESENT;
        }
    
    	// 清空集合中所有元素
        public void clear() {
        
            map.clear();
        }

#### 🗒️LinkedHashSet源码解析 ####

`LinkedHashSet是HashSet的子类`，并且内部使用链表维护元素的插入顺序。下面是LinkedHashSet的一些特点和使用方法：

保持插入顺序：与HashSet不同的是，LinkedHashSet会`按照元素插入的顺序来维护集合中的元素`。遍历LinkedHashSet时可以按照元素插入的顺序进行访问。

基于哈希表和链表：`LinkedHashSet内部既使用哈希表来存储元素，又使用链表来维护元素的插入顺序。`

性能表现：与HashSet相比，LinkedHashSet在添加、删除和包含操作的性能方面略低一些，因为需要同时维护哈希表和链表。

##### 构造函数 #####

![在这里插入图片描述][47e32695addc42658ddd4b03d45f3652.png]

#### 🗒️TreeSet源码解析 ####

有序性：TreeSet会对元素进行排序，并且`可以按照自然顺序或者自定义排序规则来进行排序`。默认情况下，TreeSet会按照元素的自然顺序进行排序，或者在构造函数中传入Comparator对象以自定义排序规则。

不允许null元素：TreeSet不允许添加null元素，因为它使用元素的比较规则来维护顺序，而null无法比较大小。

性能表现：TreeSet的添加、删除和包含操作的时间复杂度为O(log n)，其中n为TreeSet中的元素个数。

##### 构造函数 #####

![在这里插入图片描述][099c8b48c27441fd828a2a2821177d9d.png]

##### add方法 #####

![在这里插入图片描述][913c4290b5084d648df3805cf571920f.png]  
![在这里插入图片描述][6b9b72a5d5c945adbcb9538d86ca70c9.png]

##### addAll方法 #####

![在这里插入图片描述][3b389e483cb34928ab0ff8b7982f19c4.png]  
判断当前集合是否为空且指定集合不为空，并且指定集合为SortedSet类型，当前集合为TreeMap类型。  
如果满足以上条件，则将指定集合`转换`为SortedSet类型，将当前集合`转换`为TreeMap类型。  
比较指定集合的比较器和当前集合的比较器是否相等，如果相等，则使用线性时间版本的添加方式：map.addAllForTreeSet(set, PRESENT)。  
![在这里插入图片描述][889888827bb84ddbb14d179239f82b0c.png]

如果不满足以上条件，则调用父类的addAll方法进行添加操作。

[3befc71d50674a6aa7f40f29a28ce48a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/ce7b2289668e45978caa61c099b5212d.png
[f266bf60a9394be7996ac003e3d7c328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/511f6ff9142848c2b366516ebe31f886.png
[acc6b2f990544d10830ad97da7ef929f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/d3cd9d6859e7444c8476952101a672e5.png
[be8a1488ddf84535a670a430f08d3b86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/834010608d834897866c4a69316fa3ca.png
[190d87e06d004cfaa495ed1d386b8bdf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3cb30422ebcf49db94a4fd621f3b4207.png
[28d60f882b3b4b39b39259c7d5d69afa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/ed6f8bb1e9824b3088545e9ecfdb1d1c.png
[2789487e6e254c79b6fd8357ad7aaa31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/2223e11a86c640f08989cc267dfd2971.png
[47e32695addc42658ddd4b03d45f3652.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/14cf0c8426c64e449e0ce669e50c02fe.png
[099c8b48c27441fd828a2a2821177d9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/a3c0fdbeeee4438080d12b206591c1c5.png
[913c4290b5084d648df3805cf571920f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/7e8ee6b649d3466e841472af8d33a4d6.png
[6b9b72a5d5c945adbcb9538d86ca70c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0d178f6e5d464f20ae7ba7c9d3aa3a29.png
[3b389e483cb34928ab0ff8b7982f19c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/06b51054be31455694974488acb7d80d.png
[889888827bb84ddbb14d179239f82b0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/345f36995d004dcead9abb7aab2708b4.png