Java Set 集合：HashSet、LinkedHashSet 与 TreeSet 核心解析

Set是一类元素无序（不保证顺序），不可重复、不可索引的集合，Set接口继承与Collection接口。
注：某些Set的实现类是有序，比如LinkedHashSet。

Collection有List和Set两种类型的集合，分别有不同的特点，在开发过程中根据实际应用场景，选择对应类型的集合进行使用。

1. List：有序、可重复、可索引的集合，有基于数组数据结构的实现类ArrayList和基于双向链表的实现类LinkedList。如果集合需要存储可以重复的元素，必须选择List。在此基础上，根据集合的索引查询频率、插入和删除元素频率等场景实际情况，评估选择ArryList或者LinkedList。
2. Set：无序、不可重复、不可索引的集合，有基于哈希表+链表+红黑树数据结构的实现类HashSet、基于HashSet+顺序指向链表的实现类LinkedHashSet、基于红黑树数据结构的实现类TreeSet。如果集合需要元素去重，则使用Set。在此基础上，根据是否要求保留数据插入顺序、数据是否有序排列、数据增删查改效率，选择使用HashSet、LinkedHashSet或者TreeSet。

HashSet

HashSet在JDK8之前采用可扩容数组+链表的数据结构进行实现，在JDK8之后，采用可扩容数组+链表+红黑树的数据结构进行实现。

HashSet是基于哈希表的逻辑进行存储数据，因此依赖于hashCode()方法。去重判断则依赖于equals()方法。因此，HashSet存储自定义对象，需要在类中重写hashCode()和equals()方法。这是因为Object类中的equals()方法默认使用对象内存地址进行判断，也就是说只有同一个对象才返回true，而一般情况是两个相同类的对象的属性值相同即表示“相等”。而Object类中的hashCode()是基于内存地址进行计算，同样需要修改为基于属性值进行计算。IDEA提供一键生成自定义类的重写hashCode()和equals()方法的操作。

HashSet对象的元素插入流程如下：

1. 调用hashCode()方法，计算元素对象的哈希值。
2. 用对象的哈希值，和HashSet对象的存储元素的数组长度，计算三数组存储的索引。
3. 判断数组索引中是否有元素（是否指向null）,如果没有，则存储元素（指向该元素），完成插入操作。
4. 若该数组索引中有元素，则遍历链表（可能是链表、也可能是红黑树），调用equals()方法与已存储的元素金进行逐一比较。若有相同的，则表示元素重复，停止插入操作。若没有重复的，则插入到链表尾部。

LinkedHashSet

LinkedHashSet是继承于HashSet的实现类，与HashSet区别在于，LinkedHashSet是有序的。

相比于HashSet，LinkedHashSet中存储元素的Node节点，额外增加了两个引用，一个是指向上一个存储元素的Node节点，另外一个指向下一个存储元素的Node节点，也就是形成了串起插入顺序的双向链表。

用一个例子对比，LinkedHashSet有序，而HashSet无序：

publicclassApp{publicstaticvoidmain(String[] args){// 创建3个Student对象 Student s1 =newStudent("小王",18);Student s2 =newStudent("小李",19);Student s3 =newStudent("小张",20);// 创建一个HashSet,按顺序逐一添加3个Student对象：小王、小李、小张 HashSet<Student> hs =newHashSet<>(); hs.add(s1); hs.add(s2); hs.add(s3);for(Student s : hs){System.out.println(s);}// 迭代打印顺序，与添加顺序不同System.out.println("------------------------------------------------");// 创建一个LinkedHashSet,按顺序逐一添加3个Student对象：小王、小李、小张 LinkedHashSet<Student> lhs =newLinkedHashSet<>(); lhs.add(s1); lhs.add(s2); lhs.add(s3);for(Student s : lhs){System.out.println(s);}// 迭代打印顺序，与添加顺序相同}}

Student{name='小王', age=18} Student{name='小张', age=20} Student{name='小李', age=19} ------------------------------------------------ Student{name='小王', age=18} Student{name='小李', age=19} Student{name='小张', age=20} 进程已结束，退出代码为 0

TreeSet

TreeSet是底层用红黑树作为数据结构的Set实现类。众所周知，红黑树是二叉搜索平衡树，因此TreeSet的增删查改的效率都很高，并且TreeSet存储的元素是有序的。

树这一数据结构要求存储的元素需要能够比较，因此TreeSet存储的对象也需要支持比较。

在Java中，自定义类要支持比较，需要实现一个Comparable的接口，并重写compareTo方法。

publicclassApp2{publicstaticvoidmain(String[] args){// 创建5个Student对象 Student s1 =newStudent("xiaoWang",18);Student s2 =newStudent("xiaoaLi",18);// 与上一个对象年龄相同，名字不同 Student s3 =newStudent("xiaoaLi",20);// 与上一个对象年龄不同，名字相同 Student s4 =newStudent("xiaoaLi",20);// 与上一个对象年龄相同，名字相同 Student s5 =newStudent("liHua",17);// 创建一个TreeSet，按顺序逐一添加5个Student对象 TreeSet<Student> ts =newTreeSet<>(); ts.add(s1); ts.add(s2); ts.add(s3); ts.add(s4);// 添加重复对象  ts.add(s5);for(Student s : ts){// 遍历集合,打印出的对象按照compareTo()方法定义的比较规则排序 System.out.println(s);}}}

终端结果，TreeSet遍历打印出的结果，是按照按照CpomareTo()方法定义的比较规则排序。

Student{name='liHua', age=17}Student{name='xiaoWang', age=18}Student{name='xiaoaLi', age=18}Student{name='xiaoaLi', age=20} 进程已结束，退出代码为 0

存储的Student类实现Comparable接口，重写compareTo方法定义对象之间比较的规则。

publicclassStudentimplementsComparable<Student>{// 其他代码// ...@OverridepublicintcompareTo(Student o){/* 比较规则：若年龄不相同，则年龄大的更大 若年龄相同，则名字字符串大的更大 否则（年龄和名字相同），则两者相等 */if(this.age != o.age){returnthis.age - o.age;}else{returnthis.name.compareTo(o.name);}}}

有些情况，我们需要使用第三方的类（比如String类）进行比较，我们没办法修改第三方类让它实现Comparable接口，重写compareTo方法。

因此，Java还提供了一种在创建 TreeSet 时，传入一个 Comparator 比较器对象的方法。比如：

// 使用Comparator按姓名长度排序TreeSet<Student> ts =newTreeSet<>(newComparator<Student>(){@Overridepublicintcompare(Student s1,Student s2){return s1.getName().length()- s2.getName().length();}});