深入浅出的分析 Set集合

2023-02-27

元素 new add

 01.摘要“关于Set接口，在实际开发中，其实很少用到，但是如果你出去面试，它可能依然是一个绕不开的话题。言归正传，废话咱们也不多说了，相信使用过Set集合类的朋友都知道，Set集合的特点主要有：元素不重复、存储无序的特点。啥意思呢?你可以理解为，向一个瓶子里面扔东西，这些东西没有记号是

01. 摘要

“关于 Set 接口，在实际开发中，其实很少用到，但是如果你出去面试，它可能依然是一个绕不开的话题。

言归正传，废话咱们也不多说了，相信使用过 Set 集合类的朋友都知道，Set集合的特点主要有：元素不重复、存储无序的特点。

啥意思呢?你可以理解为，向一个瓶子里面扔东西，这些东西没有记号是第几个放进去的，但是有一点就是这个瓶子里面不会有重样的东西。

细细思考，你会发现， Set 集合的这些特性正处于 List 集合和 Map 集合之间，为什么这么说呢?之前的集合文章中，咱们了解到，List 集合的特点就是存取有序，本质是一个有序数组，每个元素依次按照顺序存储;Map 集合主要用于存放键值对，虽然底层也是用数组存放，但是元素在数组中的下标是通过哈希算法计算出来的，数组下标无序。

而 Set 集合，在元素存储方面，注重独立无二的特性，如果某个元素在集合中已经存在，不会存储重复的元素，同时，集合存储的是元素，不像 Map 集合那样存储的是键值对。

具体的分析，咱们慢慢道来，打开 Set 集合，主要实现类有 HashSet、LinkedHashSet 、TreeSet 、EnumSet( RegularEnumSet、JumboEnumSet )等等，总结 Set 接口实现类，图如下：

由图中的继承关系，可以知道，Set 接口主要实现类有 AbstractSet、HashSet、LinkedHashSet 、TreeSet 、EnumSet( RegularEnumSet、JumboEnumSet )，其中 AbstractSet、EnumSet 属于抽象类，EnumSet 是在 jdk1.5 中新增的，不同的是 EnumSet 集合元素必须是枚举类型。

HashSet 是一个输入输出无序的集合，集合中的元素基于 HashMap 的 key 实现，元素不可重复;
LinkedHashSet 是一个输入输出有序的集合，集合中的元素基于 LinkedHashMap 的 key 实现，元素也不可重复;
TreeSet 是一个排序的集合，集合中的元素基于 TreeMap 的 key 实现，同样元素不可重复;
EnumSet 是一个与枚举类型一起使用的专用 Set 集合，其中 RegularEnumSet 和 JumboEnumSet 不能单独实例化，只能由 EnumSet 来生成，同样元素不可重复;

下面咱们来对各个主要实现类进行一一分析!

02. HashSet

HashSet 是一个输入输出无序的集合，底层基于 HashMap 来实现，HashSet 利用 HashMap 中的key元素来存放元素，这一点我们可以从源码上看出来，阅读源码如下：

public class HashSet<E> 
    extends AbstractSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable{ 
     
    // HashMap 变量 
    private transient HashMap<E,Object> map; 
     
    /**HashSet 初始化*/ 
    public HashSet() { 
        //默认实例化一个 HashMap 
        map = new HashMap<>(); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.

add方法

打开HashSet的add()方法，源码如下：

public boolean add(E e) { 
    //向 HashMap 中添加元素 
    return map.put(e, PRESENT)==null; 
} 
1.
2.
3.
4.

其中变量PRESENT，是一个非空对象，源码部分如下：

private static final Object PRESENT = new Object(); 
1.

可以分析出，当进行add()的时候，等价于

HashMap map = new HashMap<>(); 
map.put(e, new Object());//e 表示要添加的元素 
1.
2.

在之前的集合文章中，咱们了解到 HashMap 在添加元素的时候，通过equals()和hashCode()方法来判断传入的key是否相同，如果相同，那么 HashMap 认为添加的是同一个元素，反之，则不是。

从源码分析上可以看出，HashSet 正是使用了 HashMap 的这一特性，实现存储元素下标无序、元素不会重复的特点。

remove方法

HashSet 的删除方法，同样如此，也是基于 HashMap 的底层实现，源码如下：

public boolean remove(Object o) { 
    //调用HashMap 的remove方法，移除元素 
    return map.remove(o)==PRESENT; 
} 
1.
2.
3.
4.

查询方法

HashSet 没有像 List、Map 那样提供 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) { 
    Set<String> hashSet = new HashSet<String>(); 
    System.out.println("HashSet初始容量大小："+hashSet.size()); 
    hashSet.add("1"); 
    hashSet.add("2"); 
    hashSet.add("3"); 
    hashSet.add("3"); 
    hashSet.add("2"); 
    hashSet.add(null); 
 
    //相同元素会自动覆盖 
    System.out.println("HashSet容量大小："+hashSet.size()); 
    //迭代器遍历 
    Iterator<String> iterator = hashSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增强for循环 
    for (String str : hashSet) { 
        System.out.print(str + ","); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

输出结果：

HashSet初始容量大小：0 
HashSet容量大小：4 
null,1,2,3, 
=========== 
null,1,2,3, 
1.
2.
3.
4.
5.

需要注意的是，HashSet 允许添加为null的元素。

03. LinkedHashSet

LinkedHashSet 是一个输入输出有序的集合，继承自 HashSet，但是底层基于 LinkedHashMap 来实现。

如果你之前了解过 LinkedHashMap，那么你一定知道，它也继承自 HashMap，唯一有区别的是，LinkedHashMap 底层数据结构基于循环链表实现，并且数组指定了头部和尾部，虽然数组的下标存储无序，但是却可以通过数组的头部和尾部，加上循环链表，依次可以查询到元素存储的过程，从而做到输入输出有序的特点。

如果还不了解 LinkedHashMap 的实现过程，可以参阅集合系列中关于 LinkedHashMap 的实现过程文章。

阅读 LinkedHashSet 的源码，类定义如下：

public class LinkedHashSet<E> 
    extends HashSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable { 
 
    public LinkedHashSet() { 
        //调用 HashSet 的方法 
        super(16, .75f, true); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.

查询源码，super调用的方法，源码如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) { 
    //初始化一个 LinkedHashMap 
    map = new LinkedHashMap<>(initialCapacity, loadFactor); 
} 
1.
2.
3.
4.

add方法

LinkedHashSet没有重写add方法，而是直接调用HashSet的add()方法，因为map的实现类是LinkedHashMap，所以此处是向LinkedHashMap中添加元素，当进行add()的时候，等价于

HashMap map = new LinkedHashMap<>(); 
map.put(e, new Object());//e 表示要添加的元素 
1.
2.

remove方法

LinkedHashSet也没有重写remove方法，而是直接调用HashSet的删除方法，因为LinkedHashMap没有重写remove方法，所以调用的也是HashMap的remove方法，源码如下：

public boolean remove(Object o) { 
    //调用HashMap 的remove方法，移除元素 
    return map.remove(o)==PRESENT; 
} 
1.
2.
3.
4.

查询方法

同样的，LinkedHashSet 没有提供 get 方法，使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) { 
    Set<String> linkedHashSet = new LinkedHashSet<String>(); 
    System.out.println("linkedHashSet初始容量大小："+linkedHashSet.size()); 
    linkedHashSet.add("1"); 
    linkedHashSet.add("2"); 
    linkedHashSet.add("3"); 
    linkedHashSet.add("3"); 
    linkedHashSet.add("2"); 
    linkedHashSet.add(null); 
    linkedHashSet.add(null); 
 
    System.out.println("linkedHashSet容量大小："+linkedHashSet.size()); 
    //迭代器遍历 
    Iterator<String> iterator = linkedHashSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增强for循环 
    for (String str : linkedHashSet) { 
        System.out.print(str + ","); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

输出结果：

linkedHashSet初始容量大小：0 
linkedHashSet容量大小：4 
1,2,3,null, 
=========== 
1,2,3,null, 
1.
2.
3.
4.
5.

可见，LinkedHashSet 与 HashSet 相比，LinkedHashSet 输入输出有序。

04. TreeSet

TreeSet 是一个排序的集合，实现了NavigableSet、SortedSet、Set接口，底层基于 TreeMap 来实现。TreeSet 利用 TreeMap 中的key元素来存放元素，这一点我们也可以从源码上看出来，阅读源码，类定义如下：

public class TreeSet<E> extends AbstractSet<E> 
implements NavigableSet<E>, Cloneable, java.io.Serializable { 
     
    //TreeSet 使用NavigableMap接口作为变量 
    private transient NavigableMap<E,Object> m; 
     
    /**对象初始化*/ 
    public TreeSet() { 
        //默认实例化一个 TreeMap 对象 
        this(new TreeMap<E,Object>()); 
    } 
     
    //对象初始化调用的方法 
    TreeSet(NavigableMap<E,Object> m) { 
        this.m = m; 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

new TreeSet<>()对象实例化的时候，表达的意思，可以简化为如下：

NavigableMap<E,Object> m = new TreeMap<E,Object>(); 
1.

因为TreeMap实现了NavigableMap接口，所以没啥问题。

public class TreeMap<K,V> 
    extends AbstractMap<K,V> 
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
    ...... 
} 
1.
2.
3.
4.
5.

add方法

打开TreeSet的add()方法，源码如下：

public boolean add(E e) { 
    //向 TreeMap 中添加元素 
    return m.put(e, PRESENT)==null; 
} 
1.
2.
3.
4.

其中变量PRESENT，也是是一个非空对象，源码部分如下：

private static final Object PRESENT = new Object(); 
1.

可以分析出，当进行add()的时候，等价于

TreeMap map = new TreeMap<>(); 
map.put(e, new Object());//e 表示要添加的元素 
1.
2.

TreeMap 类主要功能在于，给添加的集合元素，按照一个的规则进行了排序，默认以自然顺序进行排序，当然也可以自定义排序，比如测试方法如下：

public static void main(String[] args) { 
    Map initMap = new TreeMap(); 
    initMap.put("4", "d"); 
    initMap.put("3", "c"); 
    initMap.put("1", "a"); 
    initMap.put("2", "b"); 
    //默认自然排序，key为升序 
    System.out.println("默认 排序结果:" + initMap.toString()); 
    //自定义排序，在TreeMap初始化阶段传入Comparator 内部对象 
    Map comparatorMap = new TreeMap<String, String>(new Comparator<String>() { 
        @Override 
        public int compare(String o1, String o2){ 
            //根据key比较大小，采用倒叙，以大到小排序 
            return o2.compareTo(o1); 
        } 
    }); 
    comparatorMap.put("4", "d"); 
    comparatorMap.put("3", "c"); 
    comparatorMap.put("1", "a"); 
    comparatorMap.put("2", "b"); 
    System.out.println("自定义 排序结果:" + comparatorMap.toString()); 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

输出结果：

默认 排序结果:{1=a, 2=b, 3=c, 4=d} 
自定义 排序结果:{4=d, 3=c, 2=b, 1=a} 
1.
2.

相信使用过TreeMap的朋友，一定知道TreeMap会自动将key按照一定规则进行排序，TreeSet正是使用了TreeMap这种特性，来实现添加的元素集合，在输出的时候，其结果是已经排序好的。

如果您没看过源码TreeMap的实现过程，可以参阅集合系列文章中TreeMap的实现过程介绍，或者阅读 jdk 源码。

remove方法

TreeSet 的删除方法，同样如此，也是基于 TreeMap 的底层实现，源码如下：

public boolean remove(Object o) { 
        //调用TreeMap 的remove方法，移除元素 
        return m.remove(o)==PRESENT; 
} 
1.
2.
3.
4.

查询方法

TreeSet 没有重写 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：

public static void main(String[] args) { 
    Set<String> treeSet = new TreeSet<>(); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add("1"); 
    treeSet.add("4"); 
    treeSet.add("3"); 
    treeSet.add("8"); 
    treeSet.add("5"); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    //迭代器遍历 
    Iterator<String> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增强for循环 
    for (String str : treeSet) { 
        System.out.print(str + ","); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

输出结果：

treeSet初始容量大小：0 
treeSet容量大小：5 
1,3,4,5,8, 
=========== 
1,3,4,5,8, 
1.
2.
3.
4.
5.

自定义排序

使用自定义排序，有 2 种方法，第一种在需要添加的元素类，实现Comparable接口，重写compareTo方法来实现对元素进行比较，实现自定义排序。

方法一

/** 
  * 创建实体类Person实现Comparable接口 
  */ 
public class Person implements Comparable<Person>{ 
    private int age; 
    private String name; 
    public Person(String name, int age){ 
        this.name = name; 
        this.age = age; 
    } 
    @Override 
    public int compareTo(Person o){ 
        //重写 compareTo 方法，自定义排序算法 
        return this.age-o.age; 
    } 
    @Override 
    public String toString(){ 
        return name+":"+age; 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

创建一个Person实体类，实现Comparable接口，重写compareTo方法，通过变量age实现自定义排序测试方法如下：

public static void main(String[] args) { 
    Set<Person> treeSet = new TreeSet<>(); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add(new Person("李一",18)); 
    treeSet.add(new Person("李二",17)); 
    treeSet.add(new Person("李三",19)); 
    treeSet.add(new Person("李四",21)); 
    treeSet.add(new Person("李五",20)); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    System.out.println("按照年龄从小到大，自定义排序结果："); 
    //迭代器遍历 
    Iterator<Person> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        Person person = iterator.next(); 
        System.out.print(person.toString() + ","); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

输出结果：

treeSet初始容量大小：0 
treeSet容量大小：5 
按照年龄从小到大，自定义排序结果： 
李二:17,李一:18,李三:19,李五:20,李四:21, 
1.
2.
3.
4.

方法二

第二种方法是在TreeSet初始化阶段，Person不用实现Comparable接口，将Comparator接口以内部类的形式作为参数，初始化进去，方法如下：

public static void main(String[] args) { 
    //自定义排序 
    Set<Person> treeSet = new TreeSet<>(new Comparator<Person>(){ 
        @Override 
        public int compare(Person o1, Person o2) { 
            if(o1 == null || o2 == null){ 
                //不用比较 
                return 0; 
            } 
            //从小到大进行排序 
            return o1.getAge() - o2.getAge(); 
        } 
    }); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add(new Person("李一",18)); 
    treeSet.add(new Person("李二",17)); 
    treeSet.add(new Person("李三",19)); 
    treeSet.add(new Person("李四",21)); 
    treeSet.add(new Person("李五",20)); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    System.out.println("按照年龄从小到大，自定义排序结果："); 
    //迭代器遍历 
    Iterator<Person> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        Person person = iterator.next(); 
        System.out.print(person.toString() + ","); 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.

输出结果：

treeSet初始容量大小：0 
treeSet容量大小：5 
按照年龄从小到大，自定义排序结果： 
李二:17,李一:18,李三:19,李五:20,李四:21, 
1.
2.
3.
4.

需要注意的是，TreeSet不能添加为空的元素，否则会报空指针错误!

05. EnumSet

EnumSet 是一个与枚举类型一起使用的专用 Set 集合，继承自AbstractSet抽象类。与 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必须是Enum的类型，并且所有元素都必须来自同一个枚举类型，EnumSet 定义源码如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E> 
    implements Cloneable, java.io.Serializable { 
    ...... 
} 
1.
2.
3.
4.

EnumSet是一个虚类，不能直接通过实例化来获取对象，只能通过它提供的静态方法来返回EnumSet实现类的实例。

EnumSet的实现类有两个，分别是RegularEnumSet、JumboEnumSet两个类，两个实现类都继承自EnumSet。

EnumSet会根据枚举类型中元素的个数，来决定是返回哪一个实现类，当 EnumSet元素中的元素个数小于或者等于64，就会返回RegularEnumSet实例;当EnumSet元素个数大于64，就会返回JumboEnumSet实例。

这一点，我们可以从源码中看出，源码如下：

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) { 
    Enum<?>[] universe = getUniverse(elementType); 
    if (universe == null) 
        throw new ClassCastException(elementType + " not an enum"); 
    //当元素个数小于或者等于 64 的时候，返回 RegularEnumSet 
    if (universe.length <= 64) 
        return new RegularEnumSet<>(elementType, universe); 
    else 
        //大于64，返回 JumboEnumSet 
        return new JumboEnumSet<>(elementType, universe); 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

noneOf是EnumSet中一个静态方法，用于判断是返回哪一个实现类。

我们来看看当元素个数小于等于64的时候，使用RegularEnumSet的类，源码如下：

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> { 
 
    /**元素为long型*/ 
    private long elements = 0L; 
 
    /**添加元素*/ 
    public boolean add(E e) { 
        typeCheck(e); 
 
        long oldElements = elements; 
        //二进制运算，获取元素 
        elements |= (1L << ((Enum<?>)e).ordinal()); 
        return elements != oldElements; 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

RegularEnumSet 通过二进制运算得到结果，直接使用long来存放元素。

我们再来看看当元素个数大于64的时候，使用JumboEnumSet的类，源码如下：

class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> { 
 
    /**元素为long型*/ 
    private long elements = 0L; 
 
    /**添加元素*/ 
    public boolean add(E e) { 
        typeCheck(e); 
 
        int eOrdinal = e.ordinal(); 
        int eWordNum = eOrdinal >>> 6; 
 
        long oldElements = elements[eWordNum]; 
        //二进制运算 
        elements[eWordNum] |= (1L << eOrdinal); 
        //使用数组来操作元素 
        boolean result = (elements[eWordNum] != oldElements); 
        if (result) 
            size++; 
        return result; 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

JumboEnumSet 也是通过二进制运算得到结果，使用long来存放元素，但是它是使用数组来存放元素。

二者相比，RegularEnumSet 效率比 JumboEnumSet 高些，因为操作步骤少，大多数情况下返回的是 RegularEnumSet，只有当枚举元素个数超过 64 的时候，会使用 JumboEnumSet。

添加元素

新建一个EnumEntity的枚举类型，定义2个参数。

public enum EnumEntity { 
    WOMAN,MAN; 
} 
1.
2.
3.

创建一个空的 EnumSet!

//创建一个 EnumSet，内容为空 
EnumSet<EnumEntity> noneSet = EnumSet.noneOf(EnumEntity.class); 
System.out.println(noneSet); 
1.
2.
3.

输出结果：

[] 
1.

创建一个 EnumSet，并将枚举类型的元素全部添加进去!

//创建一个 EnumSet，将EnumEntity 元素内容添加到EnumSet中 
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class); 
System.out.println(allSet); 
1.
2.
3.

输出结果：

[WOMAN, MAN] 
1.

创建一个 EnumSet，添加指定的枚举元素!

//创建一个 EnumSet，添加 WOMAN 到 EnumSet 中 
EnumSet<EnumEntity> customSet = EnumSet.of(EnumEntity.WOMAN); 
System.out.println(customSet); 
1.
2.
3.

查询元素

EnumSet与HashSet、LinkedHashSet、TreeSet一样，通过迭代器或者 for 循环来遍历元素，方法如下：

EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class); 
for (EnumEntity enumEntity : allSet) { 
    System.out.print(enumEntity + ","); 
} 
1.
2.
3.
4.

输出结果：

WOMAN,MAN, 
1.

06. 总结

HashSet 是一个输入输出无序的 Set 集合，元素不重复，底层基于 HashMap 的 key 来实现，元素可以为空，如果添加的元素为对象，对象需要重写 equals() 和 hashCode() 方法来约束是否为相同的元素。

LinkedHashSet 是一个输入输出有序的 Set 集合，继承自 HashSet，元素不重复，底层基于 LinkedHashMap 的 key来实现，元素也可以为空，LinkedHashMap 使用循环链表结构来保证输入输出有序。

TreeSet 是一个排序的 Set 集合，元素不可重复，底层基于 TreeMap 的 key来实现，元素不可以为空，默认按照自然排序来存放元素，也可以使用 Comparable 和 Comparator 接口来比较大小，实现自定义排序。

EnumSet 是一个与枚举类型搭配使用的专用 Set 集合，在 jdk1.5 中加入。EnumSet 是一个虚类，有2个实现类 RegularEnumSet、JumboEnumSet，不能显式的实例化改类，EnumSet 会动态决定使用哪一个实现类，当元素个数小于等于64的时候，使用 RegularEnumSet;大于 64的时候，使用JumboEnumSet类，EnumSet 其内部使用位向量实现，拥有极高的时间和空间性能，如果元素是枚举类型，推荐使用 EnumSet。