【Java】集合（二）Set

灰太狼 2024-02-18 09:46 43阅读 0赞

#### 1.Set接口基本介绍 ####

*  无序:存取顺序不一致
 *  不重复:可以去除重复
 *  无索引:没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素

#### 2.Set集合的实现类 ####

*  HashSet:无序、不重复、无索引
 *  LinkedHashSet: 有序、不重复、无索引
 *  TreeSet: 可排序、不重复、无索引

####    3.Set接口中的常用方法 ####

> 1)add:添加单个元素
> 
> 2)remove:删除指定元素
> 
> 3)contains:查找元素是否存在
> 
> 4) size:获取元素个数
> 
> 5)isEmpty:判断是否为空
> 
> 6)clear:清空
> 
> 7)addAll添加多个元素
> 
> 8) containsAll:查找多个元素是否都存在
> 
> 9) removeAll: 删除多个元素

#### 4.HashSet ####

HashSet的全面说明

> 1）`HashSet` 的实现是依赖于`HashMap`的，HashSet 的值都是存储在HashMap中的。
> 
> 2）可以存放null值，但是只能有一个
> 
> 3）不保证元素是有序的，取决于hash后，再确定索引的结果
> 
> 4）不能重复对象

HsahSet底层原理

> 1）HashSet 底层是数组+链表+红黑树
> 
> 2）添加一个元素时，先得到哈希值值-会转成-> 索引值（int index=(数组长度-1)&哈希值）
> 
> 3）找到存储数据表table，看这个索引位置是否已经存放的有元素
> 
> 4）如果没有，直接加入
> 
> 5）如果有 ， 调用 equals 比较，如果相同，就放弃添加，如果不相同，则添加到最后在
> 
> 6）Java8中,如果一条链表的元素个数到达 TREEIFY THRESHOLD(默认是 8)，并且table的大小 >=MIN TREEIFY CAPACITY(默认64），就会进行树化(红黑树)

![709e3eeff16e489486f5ad73c1e15d56.png][]

HashSet的扩容机制

> 1）HashSet底层是HashMap,第一次添加时，table 数组扩容到 16，临界值(threshold)是 16\*加载因子loadFactor)是0.75 = 12
> 
> 2）如果table 数组使用到了临界值 12,就会扩容到 16 \* 2 = 32,新的临界值就是32\*0.75 = 24,依次类推
> 
> 3）在Java8中,如果一条链表的元素个数到达 TREEIFY THRESHOLD(默认是 8)并且table的大小 >=MIN TREEIFY CAPACITY(默认64)就会进行树化(红黑树),否则仍然采用数组扩容机制

5.LinkedHashSet

LinkedHashSet的全面说明

> 1）LinkedHashSet是HashSet的子类
> 
> 2）LinkedHashSet底层是一个LinkedHashMap,底层维护了一个 数组+双向链表
> 
> 3）LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
> 
> 4）LinkedHashSet不允许重复元素

LinkedHashSet的底层机制

> 1)在LinkedHastSet 中维护了一个hash表和双向链表( LinkedHashSet 有 head 和 tail )
> 
> 2)每一个节点有 pre 和 next 属性,这样可以形成双向链表
> 
> 3)在添加一个元素时，先求hash值，在求索引，确定该元素在hashtable的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加\[原则和hashset一样\])
> 
> tail.next = newElement // 简单指定  
> newElement.pre = tail
> 
> tail = newEelment;  
> 4)这样的话，我们遍历LinkedHashSet 也能确保插入顺序和遍历顺序一致

#### 6.TreeSet ####

TreeSet集合的特点

*  可排序、不重复、无索引
 *  底层基于红黑树实现排序，增删改查性能较好

TreeSet集合的自定义排序规则  
TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。  
方式一  
让自定义的类(如学生类)实现Comparable接口，重写里面的compareTo方法来指定比较规则。  
方式二  
通过调用TreeSet集合有参数构造器，可以设置Comparator对象 (比较器对象，用于指定比较规则）  
public TreeSet(Comparator<? super E> comparator)  
两种方式中，排序规则:  
根据compareTo方法的返回值进行指定元素位置如

如果返回值为负数，表示当前存入的元素是较小值，存左边

如果返回值为0，表示当前存入的元素相等 ，不存

如果返回值为正数，表示当前存入的元素是较大值，存右边  
  
注意: 如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序

#### 7.说一下 HashSet、LinkedHashSet 和 TreeSet 三者的异同？ ####

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。他们的不同点：

*  HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同：

1.  HashSet 的底层数据结构是哈希表（基于 HashMap 实现）
2.  LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO
3.  TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序

*  底层数据结构不同又导致这三者的应用场景不同：

1.  HashSet 用于不需要保证元素插入和取出顺序的场景
2.  LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景
3.  TreeSet 用于支持对元素自定义排序规则的场景

[709e3eeff16e489486f5ad73c1e15d56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/de2a9a713fa64fce9271a7f0c81f4f33.png