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