Set分析
一、Set的实现类：
Set接口：无序的、不可重复的元素
实现类：
HashSet：是Set的主要实现类，数据结构哈希表，底层使用了HashMap;LinkedHashSet：是HashSet的子类，底层使用了LinkedHashMap，在HashSet的哈希表数据结构基础之上，增加了一个双向链表用来记录元素添加的顺序，能按照添加顺序遍历输出。需要频繁遍历的话效率可能高于HashSet;TreeSet：基于TreeMap实现,底层实现是红黑树（二叉树的一种）,自然排序和定制排序;
使用场景:
HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。
image.png
二、HashSet
1、概述
HashSet也是一个使用频率非常高的一个集合容器，最大的特点是存储的元素是没有重复的，而且是无序的，那么对于HashSet是如何判断原始是否重复、底层又是怎么实现的，你了解吗?
2、 HashSet介绍
HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
1、HashSet 基于 HashMap 来实现的;
2、集合中的元素不重复;
3、允许有null值;
4、是无序的，即不会记录插入的顺序
5、不是线程安全的
3、使用案例
@Test
public void test1() {
Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a");
set.add("c");
// 添加了4个元素，size = 3
System.out.println(set.size());
System.out.println(set);
}
运行结果：
02b0d01246995d63f833d05488a89ee2.png
小结： 说明重复的元素不会被添加到集合中。
4、实现原理
HashSet的实现原理是基于HashMap实现的，关键是要了解HashMap的实现原理，我们下文主要从源码说明HashSet的确是走的HashMap的逻辑。
5、如何判断元素是否是一致
HashSet最大的特点是集合中的元素不重复，那它是根据什么判断是否重复，或者是同一个元素呢？大致逻辑如下：
当你把对象加入到HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode值，HashSet会假设对象没有重复出现，但是如果发现有相同hashcode值的对象，这时会调用equals()方法来来检查hashcode相等的对象是否真的相同，如果两者相同，HashSet就不会加入操作成功。
6、源码解析
主要看下add方法
// HashSet的add方法
public boolean add(E e) {
// 调用map的put方法
return map.put(e, PRESENT)==null;
}
定义了一个HashMap的属性，如下
fee5d56b10224ddc7c34ec14e04b8a0f.png
所以说明HashSet的底层实现就是HashMap，只不过只关注map的key部分。
7、总结
HashSet是一个很有用的容器，最大的特点是集合中的元素都是不重复的，底层实现是基于HashMap，所以关键是要了解HashMap的实现机制。
三、LinkedHashSet
LinkedHashSet是一个基于LinkedHashMap实现的有序去重集合列表。
- LinkedHashSet中的元素没有重复
- LinkedHashSet中的元素有顺序，维护了添加顺序
- LInkedHashSet可以存储null值
- LinkedHashSet是一个线程不安全的容器
1、验证LinkedHashSet的顺序性
@Test
public void test1() {
Set<Integer> set = new LinkedHashSet<>();
set.add(5);
set.add(4);
set.add(5);
set.add(3);
set.add(1);
set.add(9);
//正顺序遍历
System.out.print("遍历：");
set.forEach(item -> {
System.out.print(item + " ");
});
}
运行结果：
05904c3b9a526e42ea459c88ba4e37aa.png
2、验证LinkedHashSet存储null值
@Test
public void test2() {
Set<Integer> set = new LinkedHashSet<>();
set.add(null);
set.add(5);
System.out.println(set);
}
运行结果：
3aa7fb1375248847c20fffb2fa5a0cca.png
3、 底层有序性实现机制
LinkedHashSet底层是一个 LinkedHashMap，底层维护了一个数组+双向链表。它根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序, 这使得元素看起来是以插入顺序保存的。
94e1c17fe6fc0242d836bdcbaf89d4cb.png
本文主要从源码角度看下LinkedhashSet确实是依赖于LinkedHashMap,具体的逻辑还是要关注LinkedHashMap的实现。
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}
- LinkedHashSet继承于HashSet,它的源码很少，只有几个构造函数，基本上都是调用父类HashSet的构造函数。
- 查看父类的构造函数，它是一个非public的构造函数，创建了一个LinkedHashMap, 所以说是依赖于LinkedHashMap实现的。
1f0f653739d136e4670cdbbf5dfb6252.png
LinkedHashSet主要适用于对于元素的添加顺序读取有要求的场景，比如FIFO这样的场景。
四、TreeSet
- TreeSet是一个有序的集合，基于TreeMap实现，支持两种排序方式：自然排序和定制排序。
- TreeSet是非同步的，线程不安全的。
1、TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
2、和 HashSet 不同的是，TreeSet 可以实现从头或从尾进行遍历，这时是 TreeSet 定义接口，让 TreeMap 去实现的。
3、向树集添加空值TreeSet根据其自然顺序向其中添加元素。这将使用compareTo(或compare)方法在内部将元素相互比较。如果尝试使用这些方法之一比较具有空值的任何对象，则将引发NullPointerException。
1、实现Comparator接口，重写compare方法
import java.util.*;
class Student{
private int id;
private String name;
private int age;
public Student(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", age=" + age +
'}';
}
}
class MyComparator implements Comparator{
@Override
public int compare(Object o1, Object o2) {
Student s1 = (Student) o1;
Student s2 = (Student) o2;
return s1.getAge() - s2.getAge();
}
}
public class Main {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet(new MyComparator());
treeSet.add(new Student(1, "tom", 23));
treeSet.add(new Student(2, "Jerry", 20));
treeSet.add(new Student(3, "Jack", 17));
treeSet.add(new Student(4, "Marry", 54));
treeSet.add(new Student(5, "Baby", 8));
Iterator iterator = treeSet.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
5856339ab023492fbce9f953312d7b20.png
2、实现Comparable接口，覆写compareTo()方法
import java.util.*;
class Student implements Comparable{
private int id;
private String name;
private int age;
public Student(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public int compareTo(Object o) {
if(!(o instanceof Student)){
throw new RuntimeException("对象有问题");
}
Student s = (Student) o;
if(this.age > s.age){
return -1;
}else{
return 1;
}
}
}
public class Main {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add(new Student(1, "tom", 23));
treeSet.add(new Student(2, "Jerry", 20));
treeSet.add(new Student(3, "Jack", 17));
treeSet.add(new Student(4, "Marry", 54));
treeSet.add(new Student(5, "Baby", 8));
Iterator iterator = treeSet.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
3、TreeSet总结
- TreeSet实际上是TreeMap实现的，所以底层结构也是红黑树。TreeSet不需要重写hashCode()和euqals()方法，因为它去重是依靠比较器来去重，因为结构是红黑树，所以每次插入都会遍历比较来寻找节点插入位置，如果发现某个节点的值是一样的那就会直接覆盖。
- 当我们构造TreeSet时；若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。
- TreeSet是非线程安全的。
- TreeSet实现java.io.Serializable的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。
五、总结
（1）HashSet
- 不能保证元素的排列顺序，顺序有可能发生变化
- 不是同步的，非线程安全
- 集合元素可以是null，但只能放入一个null
- 当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。
- 简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等
- 注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算hashCode的值。
（2）LinkedHashSet
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
- LinkedHashSet中不能有相同元素，可以有一个Null元素，元素严格按照放入的顺序排列。
- LinkedHashSet底层数据结构由哈希表和链表组成，链表保证了元素的有序即存储和取出一致，哈希表保证了元素的唯一性。
- LinkedHashSet添加、删除操作时间复杂度都是O(1)。
（3）TreeSet
- TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。
- TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
- TreeSet是中不能有相同元素，不可以有Null元素，根据元素的自然顺序进行排序。
- TreeSet底层的数据结构是红黑树(一种自平衡二叉查找树)
- 添加、删除操作时间复杂度都是O(log(n))
hashset参考：https://blog.csdn.net/ch98000/article/details/126557209
