深入浅出的分析 Set集合
- 2019 年 11 月 26 日
- 笔记
原文链接：https://blog.csdn.net/javageektech/article/details/103077788
01. 摘要
Set集合的特点主要有：元素不重复、存储无序的特点。
打开 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 HashSetextends AbstractSetimplements Set, Cloneable, java.io.Serializable{
// HashMap 变量 private transient HashMap<E,Object> map;
/**HashSet 初始化*/ public HashSet() { //默认实例化一个 HashMap map = new HashMap<>(); } }
add方法
打开HashSet的add()方法，源码如下：
public boolean add(E e) {//向 HashMap 中添加元素return map.put(e, PRESENT)==null;}
其中变量PRESENT，是一个非空对象，源码部分如下：private static final Object PRESENT = new Object();
可以分析出，当进行add()的时候，等价于HashMap map = new HashMap<>();map.put(e, new Object());//e 表示要添加的元素
在之前的集合文章中，咱们了解到 HashMap 在添加元素的时候 ，通过equals()和hashCode()方法来判断传入的key是否相同，如果相同，那么 HashMap 认为添加的是同一个元素，反之，则不是。
从源码分析上可以看出，HashSet 正是使用了 HashMap 的这一特性，实现存储元素下标无序、元素不会重复的特点。
remove方法
HashSet 的删除方法，同样如此，也是基于 HashMap 的底层实现，源码如下：
public boolean remove(Object o) {//调用HashMap 的remove方法，移除元素return map.remove(o)==PRESENT;}
查询方法
HashSet 没有像 List、Map 那样提供 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {Set hashSet = new HashSet();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 ","); } }
输出结果：HashSet初始容量大小：0HashSet容量大小：4
null,1,2,3,
null,1,2,3,
需要注意的是，HashSet 允许添加为null的元素。
03. LinkedHashSet
LinkedHashSet 是一个输入输出有序的集合，继承自 HashSet，但是底层基于 LinkedHashMap 来实现。
如果你之前了解过 LinkedHashMap，那么你一定知道，它也继承自 HashMap，唯一有区别的是，LinkedHashMap 底层数据结构基于循环链表实现，并且数组指定了头部和尾部，虽然数组的下标存储无序，但是却可以通过数组的头部和尾部，加上循环链表，依次可以查询到元素存储的过程，从而做到输入输出有序的特点。
如果还不了解 LinkedHashMap 的实现过程，可以参阅集合系列中关于 LinkedHashMap 的实现过程文章。
阅读 LinkedHashSet 的源码，类定义如下：
public class LinkedHashSetextends HashSetimplements Set, Cloneable, java.io.Serializable {
public LinkedHashSet() { //调用 HashSet 的方法 super(16, .75f, true); } }
查询源码，super调用的方法，源码如下：
HashSet(int initialCapacity, float loadFactor, boolean dummy) {//初始化一个 LinkedHashMapmap = new LinkedHashMap<>(initialCapacity, loadFactor);}
add方法
LinkedHshSet没有重写add方法，而是直接调用HashSet的add()方法，因为map的实现类是LinkedHashMap，所以此处是向LinkedHashMap中添加元素，当进行add()的时候，等价于HashMap map = new LinkedHashMap<>();map.put(e, new Object());//e 表示要添加的元素
remove方法
LinkedHashSet也没有重写remove方法，而是直接调用HashSet的删除方法，因为LinkedHashMap没有重写remove方法，所以调用的也是HashMap的remove方法，源码如下：
public boolean remove(Object o) {//调用HashMap 的remove方法，移除元素return map.remove(o)==PRESENT;}
查询方法
同样的，LinkedHashSet 没有提供 get 方法，使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {Set linkedHashSet = new LinkedHashSet();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 ","); } }
输出结果：linkedHashSet初始容量大小：0linkedHashSet容量大小：4
1,2,3,null,
1,2,3,null,可见，LinkedHashSet 与 HashSet 相比，LinkedHashSet 输入输出有序。
04. TreeSet
TreeSet 是一个排序的集合，实现了NavigableSet、SortedSet、Set接口，底层基于 TreeMap 来实现。TreeSet 利用 TreeMap 中的key元素来存放元素，这一点我们也可以从源码上看出来，阅读源码，类定义如下：
public class TreeSet extends AbstractSetimplements NavigableSet, 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; } }
new TreeSet<>()对象实例化的时候，表达的意思，可以简化为如下：NavigableMap m = new TreeMap();
因为TreeMap实现了NavigableMap接口，所以没啥问题。
public class TreeMapextends AbstractMapimplements NavigableMap, Cloneable, java.io.Serializable{……}
add方法
打开TreeSet的add()方法，源码如下：
public boolean add(E e) {//向 TreeMap 中添加元素return m.put(e, PRESENT)==null;}
其中变量PRESENT，也是是一个非空对象，源码部分如下：private static final Object PRESENT = new Object();
可以分析出，当进行add()的时候，等价于TreeMap map = new TreeMap<>();map.put(e, new Object());//e 表示要添加的元素
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(new Comparator() {@Overridepublic 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=a, 2=b, 3=c, 4=d}自定义 排序结果:{4=d, 3=c, 2=b, 1=a}
相信使用过TreeMap的朋友，一定知道TreeMap会自动将key按照一定规则进行排序，TreeSet正是使用了TreeMap这种特性，来实现添加的元素集合，在输出的时候，其结果是已经排序好的。
如果您没看过源码TreeMap的实现过程，可以参阅集合系列文章中TreeMap的实现过程介绍，或者阅读 jdk 源码。
remove方法
TreeSet 的删除方法，同样如此，也是基于 TreeMap 的底层实现，源码如下：
public boolean remove(Object o) {//调用TreeMap 的remove方法，移除元素return m.remove(o)==PRESENT;}
查询方法
TreeSet 没有重写 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {Set 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 ","); } }
输出结果：treeSet初始容量大小：0treeSet容量大小：5
1,3,4,5,8,
1,3,4,5,8,
自定义排序
使用自定义排序，有 2 种方法，第一种在需要添加的元素类，实现Comparable接口，重写compareTo方法来实现对元素进行比较，实现自定义排序。
方法一
/**
- 创建实体类Person实现Comparable接口 */ public class Person implements Comparable{ 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; } }
创建一个Person实体类，实现Comparable接口，重写compareTo方法，通过变量age实现自定义排序 测试方法如下：
public static void main(String[] args) {Set 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() ","); } }
输出结果：treeSet初始容量大小：0treeSet容量大小：5按照年龄从小到大，自定义排序结果：李二:17,李一:18,李三:19,李五:20,李四:21,
方法二
第二种方法是在TreeSet初始化阶段，Person不用实现Comparable接口，将Comparator接口以内部类的形式作为参数，初始化进去，方法如下：
public static void main(String[] args) {//自定义排序Set treeSet = new TreeSet<>(new Comparator(){@Overridepublic 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() ","); } }
输出结果：treeSet初始容量大小：0treeSet容量大小：5按照年龄从小到大，自定义排序结果：李二:17,李一:18,李三:19,李五:20,李四:21,需要注意的是，TreeSet不能添加为空的元素，否则会报空指针错误！
05. EnumSet
EnumSet 是一个与枚举类型一起使用的专用 Set 集合，继承自AbstractSet抽象类。与 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必须是Enum的类型，并且所有元素都必须来自同一个枚举类型，EnumSet 定义源码如下：
public abstract class EnumSet> extends AbstractSetimplements Cloneable, java.io.Serializable {……}
EnumSet是一个虚类，不能直接通过实例化来获取对象，只能通过它提供的静态方法来返回EnumSet实现类的实例。
EnumSet的实现类有两个，分别是RegularEnumSet、JumboEnumSet两个类，两个实现类都继承自EnumSet。
EnumSet会根据枚举类型中元素的个数，来决定是返回哪一个实现类，当 EnumSet元素中的元素个数小于或者等于64，就会返回RegularEnumSet实例；当EnumSet元素个数大于64，就会返回JumboEnumSet实例。
我们来看看当元素个数小于等于64的时候，使用RegularEnumSet的类，源码如下：
class RegularEnumSet> extends EnumSet {
/**元素为long型*/ private long elements = 0L;
/**添加元素*/ public boolean add(E e) { typeCheck(e);
long oldElements = elements; //二进制运算，获取元素 elements |= (1L << ((Enum<?>)e).ordinal()); return elements != oldElements; } } RegularEnumSet 通过二进制运算得到结果，直接使用long来存放元素。
我们再来看看当元素个数大于64的时候，使用JumboEnumSet的类，源码如下：
class JumboEnumSet> extends EnumSet {
/**元素为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; } } JumboEnumSet 也是通过二进制运算得到结果，使用long来存放元素，但是它是使用数组来存放元素。
二者相比，RegularEnumSet 效率比 JumboEnumSet 高些，因为操作步骤少，大多数情况下返回的是 RegularEnumSet，只有当枚举元素个数超过 64 的时候，会使用 JumboEnumSet。
添加元素：//新建一个EnumEntity的枚举类型，定义2个参数public enum EnumEntity {WOMAN,MAN;}
创建一个空的 EnumSet：//创建一个 EnumSet，内容为空EnumSet noneSet = EnumSet.noneOf(EnumEntity.class);System.out.println(noneSet);输出结果：[]
创建一个 EnumSet，并将枚举类型的元素全部添加进去：//创建一个 EnumSet，将EnumEntity 元素内容添加到EnumSet中EnumSet allSet = EnumSet.allOf(EnumEntity.class);System.out.println(allSet);
输出结果：[WOMAN, MAN]
创建一个 EnumSet，添加指定的枚举元素：//创建一个 EnumSet，添加 WOMAN 到 EnumSet 中EnumSet customSet = EnumSet.of(EnumEntity.WOMAN);System.out.println(customSet);
查询元素EnumSet与HashSet、LinkedHashSet、TreeSet一样，通过迭代器或者 for 循环来遍历元素，方法如下：
EnumSet allSet = EnumSet.allOf(EnumEntity.class);for (EnumEntity enumEntity : allSet) {System.out.print(enumEntity ",");}
输出结果：WOMAN,MAN,
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。
07. 参考
1、JDK1.7&JDK1.8 源码
2、程序园 – java集合－EnumMap与EnumSet
