Set 和 List 一样，也继承于 Collection，是集合的一种。和 List 不同的是，Set 内部实现是基于 Map 的，所以 Set取值时不保证数据和存入的时候顺序一致，并且不允许空值，不允许重复值。

Set主要有2个实现方式，一个是 TreeSet，另一个是 HashSet 。

HashSet

HashSet 是 Set 的一个重要实现类，称为哈希集
HashSet 中的元素无序并且不可以重复
HashSet 中只允许一个 null 元素
具有良好的存取和查找性能

就如它的名字一样，HashSet 主要由 HashMap 实现

如果调用HashSet的无参构造函数，那么就会使用默认的HashMap，初始化Size为16，扩张系数为0.75

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

接下来，我们简单的看一下 HashSet 的几个数据执行操作

/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element <tt>e</tt> to this set if
 * this set contains no element <tt>e2</tt> such that
 * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
 * If this set already contains the element, the call leaves the set
 * unchanged and returns <tt>false</tt>.
 *
 * @param e element to be added to this set
 * @return <tt>true</tt> if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

/**
 * Removes the specified element from this set if it is present.
 * More formally, removes an element <tt>e</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
 * if this set contains such an element.  Returns <tt>true</tt> if
 * this set contained the element (or equivalently, if this set
 * changed as a result of the call).  (This set will not contain the
 * element once the call returns.)
 *
 * @param o object to be removed from this set, if present
 * @return <tt>true</tt> if the set contained the specified element
 */
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

/**
 * Removes all of the elements from this set.
 * The set will be empty after this call returns.
 */
public void clear() {
    map.clear();
}

/**
 * Returns <tt>true</tt> if this set contains no elements.
 *
 * @return <tt>true</tt> if this set contains no elements
 */
public boolean isEmpty() {
    return map.isEmpty();
}

/**
 * Returns the number of elements in this set (its cardinality).
 *
 * @return the number of elements in this set (its cardinality)
 */
public int size() {
    return map.size();
}

/**
 * Returns an iterator over the elements in this set.  The elements
 * are returned in no particular order.
 *
 * @return an Iterator over the elements in this set
 * @see ConcurrentModificationException
 */
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

可以看出，HashMap 的几个主要数据执行操作都是间接的调用了内部的 HashMap 的数据操作

HashSet 的值是 HashMap 的 key

HashMap 的 value 是写死的 PRESENT

所以遍历 HashSet 的值，也就是遍历 HashMap 的 KeyEntry

HashSet 如何检查重复

HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不同）是按照哈希值来存的所以取数据也是按照哈希值取得。

HashSet 会通过元素的 hashcode（）和 equals 方法进行判断元素是否重复。

当你试图把对象加入 HashSet 时，HashSet 会使用对象的 hashCode 来判断对象加入的位置。同时也会与其他已经加入的对象的 hashCode 进行比较，如果没有相等的 hashCode，HashSet 就会假设对象没有重复出现。

简单一句话，如果对象的hashCode值是不同的，那么HashSet会认为对象是不可能相等的。

因此我们自定义类的时候需要重写 hashCode，来确保对象具有相同的 hashCode 值。

如果元素(对象)的 hashCode 值相同,是不是就无法存入 HashSet 中了? 当然不是，HashSet 会继续用 equals 进行比较，如果 equals 为 true ，那么 HashSet 认为新加入的对象重复了，所以加入失败；如果 equals 为 false 那么HashSet 认为新加入的对象没有重复，新元素可以存入。

总结

元素的哈希值是通过元素的 hashcode 方法来获取的，HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法，如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。

哈希值相同 equals 为 false 的元素是怎么存储呢？就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。

import java.util.Objects;

public class Student {
    private Integer stuNum;
    private String stuName;
    private Integer stuAge;

    public Student(Integer stuNum, String stuName, Integer stuAge) {
        this.stuNum = stuNum;
        this.stuName = stuName;
        this.stuAge = stuAge;
    }

    public Integer getStuNum() {
        return stuNum;
    }

    public void setStuNum(Integer stuNum) {
        this.stuNum = stuNum;
    }

    public String getStuName() {
        return stuName;
    }

    public void setStuName(String stuName) {
        this.stuName = stuName;
    }

    public Integer getStuAge() {
        return stuAge;
    }

    public void setStuAge(Integer stuAge) {
        this.stuAge = stuAge;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println(this + "---equals---" + o);
        if (o instanceof Student){
            Student s = (Student) o;
            return this.stuName.equals(s.stuName) && this.stuAge.equals(s.stuAge);
        }else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        System.out.println("hashCode is :"+ this.stuName);
        return this.stuName.hashCode() + stuNum * 4;
    }

    @Override
    public String toString() {
        return "Student{" +
                "stuNum=" + stuNum +
                ", stuName='" + stuName + '\'' +
                ", stuAge=" + stuAge +
                '}';
    }
}

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Main{
    public static void main(String[] args) {
        Set set = new HashSet();
        Student s1 = new Student(0001,"Jack",18);
        Student s2 = new Student(0002,"Mike",20);
        Student s3 = new Student(0003,"Lucy",19);
        Student s4 = new Student(0003,"Lucy",19);
        Student s5 = new Student(0003,"Lucy",20);
        Student s6 = new Student(0004,"Lucy",20);
        set.add(s1);
        set.add(s2);
        set.add(s3);
        set.add(s4);
        set.add(s5);
        set.add(s6);

        Iterator it = set.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }
}

运行结果

hashCode is :Jack
hashCode is :Mike
hashCode is :Lucy
hashCode is :Lucy
Student{stuNum=3, stuName=’Lucy’, stuAge=19}—equals—Student{stuNum=3, stuName=’Lucy’, stuAge=19}
hashCode is :Lucy
Student{stuNum=3, stuName=’Lucy’, stuAge=20}—equals—Student{stuNum=3, stuName=’Lucy’, stuAge=19}
hashCode is :Lucy
Student{stuNum=1, stuName=’Jack’, stuAge=18}
Student{stuNum=2, stuName=’Mike’, stuAge=20}
Student{stuNum=4, stuName=’Lucy’, stuAge=20}
Student{stuNum=3, stuName=’Lucy’, stuAge=19}
Student{stuNum=3, stuName=’Lucy’, stuAge=20}

重写后的 hashCode 的判断依据是this.stuName.hashCode() + stuNum * 4

重写后的 equals 中的判断依据是this.stuName.equals(s.stuName) && this.stuAge.equals(s.stuAge);

这里我们可以看到，因为 s3 和 s4 的 hashCode 相同，所以，会用 equals 进行比较，而 s3 和 s4 的 equals 也相同，那么 HashSet 认为新加入的对象重复了，所以加入失败。

而在判断 s3 和 s5 时， s3 和 s5 的 hashCode 相同，而 equals 不同，HashSet 认为新加入的对象没有重复，新元素可以存入。

s3 和 s6 比较的时候 hashCode 不同，直接判断是不同的对象，认为没有重复，可以存入。

LinkedHashSet

继承自 HashSet，只是实现了几个构造方法，并且这几个构造方法都是直接使用了父类的构造方法。

LinkedHashSet 所使用的父类构造方法：

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet 其他的构造方法（这里只举出一个）：

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and default load factor (0.75).
 *
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

只有在 HashSet 的这个构造方法中，把 map 实例化 LinkedHashMap，而其他的构造方法则是把 map 实例化为HashMap 。所以 LinkedHashSet 的实现是通过 LinkedHashMap 实现的。

注意：无论是 HashSet 还是 LinkedHashSet，它们本质上是一个值（Value）为同一 Object（即是源码中的PRESENT）的 Map。

LinkedHashSet 集合同样是根据元素的 hashCode 值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet 将会以元素的添加顺序访问集合的元素。

LinkedHashSet 在迭代访问 Set 中的全部元素时，性能比 HashSet 好，但是插入时性能稍微逊色于 HashSet。

TreeSet

TreeSet 和 HashMap 的处理方式相似，这里就不重复展开，区别的地方在于，TreeSet 是基于 TreeMap 实现的，TreeSet 是有序的。

我们先来看这么一段代码

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class Main{
    public static void main(String[] args) {
        Set set = new TreeSet();
        set.add("cccc");
        set.add("dddd");
        set.add("aaaa");
        set.add("bbbb");
        Iterator it = set.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }
}

运行结果

aaaa
bbbb
cccc
dddd

既然 TreeSet 可以自然排序,那么 TreeSet 必定是有排序规则的。

让存入的元素自定义比较规则
给 TreeSet 指定排序规则

方式一：元素自身具备比较性

元素自身具备比较性，需要元素实现 Comparable 接口，重写 compareTo 方法，也就是让元素自身具备比较性，这种方式叫做元素的自然排序也叫做默认排序。

方式二：容器具备比较性

当元素自身不具备比较性，或者自身具备的比较性不是所需要的。那么此时可以让容器自身具备。需要定义一个类实现接口 Comparator，重写 compare 方法，并将该接口的子类实例对象作为参数传递给 TreeMap 集合的构造方法。

注意：

当 Comparable 比较方式和 Comparator 比较方式同时存在时，以 Comparator 的比较方式为主
在重写 compareTo 或者 compare 方法时，必须要明确比较的主要条件相等时要比较次要条件

假设姓名和年龄一致的人为相同的人，如果想要对人按照年龄的大小来排序，如果年龄相同的人，需要如何处理？不能直接 return 0，因为可能姓名不同（年龄相同姓名不同的人是不同的人）。此时就需要进行次要条件判断（需要判断姓名），只有姓名和年龄同时相等的才可以返回 0。

通过return 0来判断唯一性

为什么使用TreeSet存入字符串,字符串默认输出是按升序排列的？

因为字符串实现了 Comparable 接口。字符串重写了该接口的 compareTo 方法,所以 String 对象具备了比较性。那么同样道理,我的自定义元素(例如 Person 类，Book 类)想要存入 TreeSet 集合,就需要实现该接口,也就是要让自定义对象具备比较性。

存入 TreeSet 集合中的元素要具备比较性。

比较性要实现 Comparable 接口，重写该接口的 compareTo 方法

TreeSet 属于 Set 集合，该集合的元素是不能重复的，TreeSet 如何保证元素的唯一性？

通过 compareTo 或者 compare 方法中的来保证元素的唯一性。

添加的元素必须要实现 Comparable 接口。当 compareTo() 函数返回值为0时，说明两个对象相等，此时该对象不会添加进来。

让元素自身具备比较性

也就是元素需要实现Comparable接口，覆盖compareTo 方法。这种方式也作为元素的自然排序，也可称为默认排序。年龄按照搜要条件，年龄相同再比姓名。

import java.util.Objects;

public class Student implements Comparable{
    private Integer stuNum;
    private String stuName;
    private Integer stuAge;

    public Student(Integer stuNum, String stuName, Integer stuAge) {
        this.stuNum = stuNum;
        this.stuName = stuName;
        this.stuAge = stuAge;
    }

    public Integer getStuNum() {
        return stuNum;
    }

    public void setStuNum(Integer stuNum) {
        this.stuNum = stuNum;
    }

    public String getStuName() {
        return stuName;
    }

    public void setStuName(String stuName) {
        this.stuName = stuName;
    }

    public Integer getStuAge() {
        return stuAge;
    }

    public void setStuAge(Integer stuAge) {
        this.stuAge = stuAge;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println(this + "---equals---" + o);
        if (o instanceof Student){
            Student s = (Student) o;
            return this.stuName.equals(s.stuName) && this.stuAge.equals(s.stuAge);
        }else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        System.out.println("hashCode is :"+ this.stuName);
        return this.stuName.hashCode() + stuNum * 4;
    }

    @Override
    public String toString() {
        return "Student{" +
                "stuNum=" + stuNum +
                ", stuName='" + stuName + '\'' +
                ", stuAge=" + stuAge +
                '}';
    }

    @Override
    public int compareTo(Object o) {
        Student s = (Student) o;
        System.out.println(this + "compareTo:" + s);
        if (this.stuAge > s.stuAge){
            return 1;
        }
        if (this.stuAge < s.stuAge){
            return -1;
        }
        return this.stuName.compareTo(s.stuName);
    }
}

import java.util.TreeSet;

public class Main{
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
        ts.add( new Student(0001,"Jack",18));
        ts.add( new Student(0002,"Mike",20));
        ts.add( new Student(0003,"Lucy",19));
        ts.add( new Student(0003,"Lucy",19));
        ts.add( new Student(0003,"Lucy",20));
        ts.add( new Student(0004,"Lucy",20));
        System.out.println(ts);
        System.out.println(ts.size());
    }
}

运行结果

Student{stuNum=1, stuName=’Jack’, stuAge=18}compareTo:Student{stuNum=1, stuName=’Jack’, stuAge=18}
Student{stuNum=2, stuName=’Mike’, stuAge=20}compareTo:Student{stuNum=1, stuName=’Jack’, stuAge=18}
Student{stuNum=3, stuName=’Lucy’, stuAge=19}compareTo:Student{stuNum=1, stuName=’Jack’, stuAge=18}
Student{stuNum=3, stuName=’Lucy’, stuAge=19}compareTo:Student{stuNum=2, stuName=’Mike’, stuAge=20}
Student{stuNum=3, stuName=’Lucy’, stuAge=19}compareTo:Student{stuNum=3, stuName=’Lucy’, stuAge=19}
Student{stuNum=3, stuName=’Lucy’, stuAge=20}compareTo:Student{stuNum=3, stuName=’Lucy’, stuAge=19}
Student{stuNum=3, stuName=’Lucy’, stuAge=20}compareTo:Student{stuNum=2, stuName=’Mike’, stuAge=20}
Student{stuNum=4, stuName=’Lucy’, stuAge=20}compareTo:Student{stuNum=3, stuName=’Lucy’, stuAge=19}
Student{stuNum=4, stuName=’Lucy’, stuAge=20}compareTo:Student{stuNum=2, stuName=’Mike’, stuAge=20}
Student{stuNum=4, stuName=’Lucy’, stuAge=20}compareTo:Student{stuNum=3, stuName=’Lucy’, stuAge=20}
[Student{stuNum=1, stuName=’Jack’, stuAge=18}, Student{stuNum=3, stuName=’Lucy’, stuAge=19}, Student{stuNum=3, stuName=’Lucy’, stuAge=20}, Student{stuNum=2, stuName=’Mike’, stuAge=20}]

4

让容器自身具备比较性

当元素自身不具备比较性，或者元素自身具备的比较性不是所需的。那么这时只能让容器自身具备。

定义一个类实现 Comparator 接口，覆盖 compare 方法。并将该接口的子类对象作为参数传递给 TreeSet 集合的构造函数。当 Comparable 比较方式，及 Comparator 比较方式同时存在，以 Comparator 比较方式为主。

public class Book {
    private String name;
    private double price;

    public Book(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

import java.util.Comparator;

public class MyComparator implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        Book b1 = (Book) o1;
        Book b2 = (Book) o2;
        System.out.println(b1 + "compare" + b2);
        if (b1.getPrice() > b2.getPrice()){
            return 1;
        }
        if (b1.getPrice() < b2.getPrice()){
            return -1;
        }
        return b1.getName().compareTo(b2.getName());
    }
}

import java.util.TreeSet;

public class Main{
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(new MyComparator());
        ts.add(new Book("think in java", 100));
        ts.add(new Book("java 核心技术", 75));
        ts.add(new Book("现代操作系统", 50));
        ts.add(new Book("java就业教程", 35));
        ts.add(new Book("think in java", 100));
        ts.add(new Book("ccc in java", 100));
        System.out.println(ts);
    }
}

HashSet、LinkedHashSet 和 TreeSet 的区别

底层存储的数据结构不同

HashSet 底层用的是 HashMap 哈希表结构存储，LinkedHashSet 继承自 HashSet 底层用的是 LinkedHashMap 链表结构存储，而 TreeSet 底层用的是 TreeMap 树结构存储
存储时保证数据唯一性依据不同

HashSet 和 LinkedHashSet 是通过重写 hashCode() 方法和 equals() 方法来保证的，而 HashSet 通过 Compareable 接口的compareTo() 方法来保证的
有序性不一样

HashSet 无序，LinkedHashSet 以元素的插入顺序，TreeSet 有序
线程安全

都不安全