Java集合系列(三)：HashSet、LinkedHashSet、TreeSet的使用方法及区别
本篇博客主要讲解Set接口的三个实现类HashSet、LinkedHashSet、TreeSet的使用方法以及三者之间的区别。
注意：本文中代码使用的JDK版本为1.8.0_191
1. HashSet使用
HashSet是Set接口最常用的实现类，底层数据结构是哈希表，HashSet不保证元素的顺序但保证元素必须唯一。
private transient HashMap<E,Object> map;HashSet类的代码声明如下所示：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
......
}1.1 添加元素
使用HashSet添加元素的使用方法如下所示：
HashSet<String> platformSet = new HashSet<>();
// 添加元素
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));
System.out.println(platformSet.add("微信公众号"));
// 添加重复元素,不会添加成功,因为Set不允许重复元素
// 不过代码不会报错,而是返回false,即添加失败
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));以上代码运行的输出结果是：
true
true
true
false
false
调试代码也会发现platformSet只有3个元素：
值得注意的是，platformSet.add(3, "个人博客");这句代码会出现编译错误，因为Set集合添加元素只有1个方法，并不像上篇博客中讲解的List接口一样提供了2个重载。
1.2 获取元素
和List接口不一样的是，Set类接口并没有获取元素的方法。
1.3 获取集合元素个数
获取HashSet元素个数的使用方法如下所示：
System.out.println("platformSet的元素个数为：" + platformSet.size());1.4 删除元素
值得注意的是，使用HashSet删除元素也只有1个方法，并不像使用ArrayList删除元素有2个重载：
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}使用方法如下所示：
// 删除不存在的元素"个人博客",返回false
System.out.println(platformSet.remove("个人博客"));
// 删除存在的元素 "微信公众号",返回true
System.out.println(platformSet.remove("微信公众号"));1.5 修改元素
和List接口不一样的是，Set类接口并没有修改元素的方法。
1.6 判断集合是否为空
判断HashSet是否为空的使用方法如下所示：
System.out.println("isEmpty:" + platformSet.isEmpty());1.7 遍历元素(面试常问)
遍历HashSet的元素主要有以下2种方式：
- 迭代器遍历
- foreach循环
使用方法如下所示：
System.out.println("使用Iterator遍历：");
Iterator<String> platformIterator = platformSet.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("使用foreach遍历：");
for (String platform : platformSet) {
System.out.println(platform);
}1.8 清空集合
清空ArrayList中所有元素的使用方法如下所示：
platformSet.clear();1.9 完整示例代码
上面讲解的几点，完整代码如下所示：
package collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class SetTest {
public static void main(String[] args) {
Set<String> platformSet = new HashSet<>();
// 添加元素
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));
System.out.println(platformSet.add("微信公众号"));
// 添加重复元素,不会添加成功,因为Set不允许重复元素
// 不过代码不会报错,而是返回false,即添加失败
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));
System.out.println("platformSet的元素个数为：" + platformSet.size());
// 删除不存在的元素"个人博客",返回false
System.out.println(platformSet.remove("个人博客"));
// 删除存在的元素 "微信公众号",返回true
System.out.println(platformSet.remove("微信公众号"));
System.out.println("platformSet的元素个数为：" + platformSet.size());
System.out.println("isEmpty:" + platformSet.isEmpty());
System.out.println("使用Iterator遍历：");
Iterator<String> platformIterator = platformSet.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("使用foreach遍历：");
for (String platform : platformSet) {
System.out.println(platform);
}
System.out.println();
platformSet.clear();
System.out.println("isEmpty:" + platformSet.isEmpty());
}
}输出结果为：
true
true
true
false
false
platformSet的元素个数为：3
false
true
platformSet的元素个数为：2
isEmpty:false
使用Iterator遍历：
博客园
掘金
使用foreach遍历：
博客园
掘金
isEmpty:true
2. LinkedHashSet使用
LinkedHashSet也是Set接口的实现类，底层数据结构是链表和哈希表，哈希表用来保证元素唯一，链表用来保证元素的插入顺序，即FIFO(First Input First Output 先进先出)。
LinkedHashSet类的代码声明如下所示：
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
{
}从以上代码也能看出，LinkedHashSet类继承了HashSet类。
LinkedHashSet类的使用方法和HashSet基本一样，只需修改下声明处的代码即可：
Set<String> platformSet = new LinkedHashSet<>();3. TreeSet使用
TreeSet也是Set接口的实现类，底层数据结构是红黑树，TreeSet不仅保证元素的唯一性，也保证元素的顺序。
TreeSet类的代码声明如下所示：
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
}TreeSet类的使用方法和HashSet基本一样，只需修改下声明处的代码即可：
Set<String> platformSet = new TreeSet<>();4. HashSet、LinkedHashSet、TreeSet的区别(面试常问)
HashSet、LinkedHashSet、TreeSet是实现Set接口的3个实现类，其中：
HashSet只是通用的存储数据的集合，
LinkedHashSet的主要功能用于保证FIFO(先进先出)即有序的集合，
TreeSet的主要功能用于排序(自然排序或者比较器排序)
4.1 相同点
1)HashSet、LinkedHashSet、TreeSet都实现了Set接口
2)三者都保证了元素的唯一性，即不允许元素重复
3)三者都不是线程安全的
可以使用Collections.synchronizedSet()方法来保证线程安全
4.2 不同点
4.2.1 排序
HashSet不保证元素的顺序
LinkHashSet保证FIFO即按插入顺序排序
TreeSet保证元素的顺序，支持自定义排序规则
空口无凭，上代码看效果：
HashSet<String> hashSet = new HashSet<>();
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
TreeSet<String> treeSet = new TreeSet<>();
String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
hashSet.add(letter);
linkedHashSet.add(letter);
treeSet.add(letter);
}
System.out.println("HashSet(我不保证顺序):" + hashSet);
System.out.println("LinkedHashSet(我保证元素插入时的顺序):" + linkedHashSet);
System.out.println("TreeSet(我按排序规则保证元素的顺序):" + treeSet);上面代码的输出结果为：
HashSet(我不保证顺序):[A, B, C, D, E]
LinkedHashSet(我保证元素插入时的顺序):[B, A, D, C, E]
TreeSet(我按排序规则保证元素的顺序):[A, B, C, D, E]
4.2.2 null值
HashSet，LinkedHashSet允许添加null值，TreeSet不允许添加null值，添加null时会抛出java.lang.NullPointerException异常。
Set<String> platformSet = new TreeSet<>();
platformSet.add(null);运行上面的代码，报错信息如下所示：
4.2.3 性能
理论情况下，添加相同数量的元素， HashSet最快，其次是LinkedHashSet，TreeSet最慢（因为内部要排序）。
然后我们通过一个示例来验证下，首先新建Employee类，自定义排序规则：
package collection;
public class Employee implements Comparable<Employee> {
private Integer employeeNo;
public Employee(Integer employeeNo) {
this.employeeNo = employeeNo;
}
public Integer getEmployeeNo() {
return employeeNo;
}
public void setEmployeeNo(Integer employeeNo) {
this.employeeNo = employeeNo;
}
@Override
public int compareTo(Employee o) {
return this.employeeNo - o.employeeNo;
}
}然后添加如下验证代码，分别往HashSet，LinkedHashSet，TreeSet中添加10000个元素：
Random random = new Random();
HashSet<Employee> hashSet = new HashSet<>();
LinkedHashSet<Employee> linkedHashSet = new LinkedHashSet<>();
TreeSet<Employee> treeSet = new TreeSet<>();
int maxNo = 10000;
long startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
hashSet.add(new Employee(randomNo));
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet耗时: " + duration);
startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
linkedHashSet.add(new Employee(randomNo));
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet:耗时 " + duration);
startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
treeSet.add(new Employee(randomNo));
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet耗时: " + duration);第1次运行，输出结果：
HashSet耗时: 6203357
LinkedHashSet:耗时 5246129
TreeSet耗时: 7813460
第2次运行，输出结果：
HashSet耗时: 9726115
LinkedHashSet:耗时 5521640
TreeSet耗时: 6884474
第3次运行，输出结果：
HashSet耗时: 7263940
LinkedHashSet:耗时 6156487
TreeSet耗时: 8554666
第4次运行，输出结果：
HashSet耗时: 6140263
LinkedHashSet:耗时 4643429
TreeSet耗时: 7804146
第5次运行，输出结果：
HashSet耗时: 7913810
LinkedHashSet:耗时 5847025
TreeSet耗时: 8511402
从5次运行的耗时可以看出，TreeSet是最耗时的，不过LinkedHashSet的耗时每次都比HashSet少，
这就和上面说的HashSet最快矛盾了，所以这里留个疑问：HashSet和LinkedHashSet哪个更快？
大家怎么看待这个问题，欢迎留言。
5. TreeSet的两种排序方式(面试常问)
先回顾下上面使用TreeSet排序的代码：
TreeSet<String> treeSet = new TreeSet<>();
String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
treeSet.add(letter);
}
System.out.println("TreeSet(我按排序规则保证元素的顺序):" + treeSet);我们插入元素的顺序是"B", "A", "D", "C", "E"，但是输出元素的顺序是"A", "B", "C", "D", "E"，证明TreeSet已经按照内部规则排过序了。
那如果TreeSet中放入的元素类型是我们自定义的引用类型，它的排序规则是什么样的呢？
带着这个疑问，我们新建个Student类如下：
package collection;
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
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;
}
}然后添加如下验证代码：
TreeSet<Student> studentTreeSet = new TreeSet<>();
Student student1 = new Student("zhangsan", 20);
Student student2 = new Student("lisi", 22);
Student student3 = new Student("wangwu", 24);
Student student4 = new Student("zhaoliu", 26);
Student student5 = new Student("zhangsan", 22);
studentTreeSet.add(student1);
studentTreeSet.add(student2);
studentTreeSet.add(student3);
studentTreeSet.add(student4);
studentTreeSet.add(student5);
for (Student student : studentTreeSet) {
System.out.println("name:" + student.getName() + ",age:" + student.getAge());
}满心欢喜的运行代码想看下效果，结果却发现报如下错误：
为什么会这样呢？
这是因为我们并没有给Student类定义任何排序规则，TreeSet说我也不知道咋排序，还是甩锅抛出异常吧，哈哈。
怎么解决呢？有以下两种方式：
- 自然排序
- 比较器排序
5.1 自然排序
自然排序的实现方式是让Student类实现接口Comparable，并重写该接口的方法compareTo，该方法会定义排序规则。
使用IDEA的快捷键生成的compareTo方法默认是这样的：
@Override
public int compareTo(Student o) {
return 0;
}这个方法会在执行add()方法添加元素时执行，以便确定元素的位置。
如果返回0，代表两个元素相同，只会保留第一个元素
如果返回值大于0，代表这个元素要排在参数中指定元素o的后面
如果返回值小于0，代表这个元素要排在参数中指定元素o的前面
因此如果对compareTo()方法不做任何修改，直接运行之前的验证代码，会发现集合中只有1个元素：
name:zhangsan,age:20
然后修改下compareTo()方法的逻辑为：
@Override
public int compareTo(Student o) {
// 排序规则描述如下
// 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
// 如果姓名的长度相同，按字典顺序比较String
// 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面
int orderByNameLength = this.name.length() - o.name.length();
int orderByName = orderByNameLength == 0 ? this.name.compareTo(o.name) : orderByNameLength;
int orderByAge = orderByName == 0 ? this.age - o.age : orderByName;
return orderByAge;
}再次运行之前的验证代码，输出结果如下所示：
name:lisi,age:22
name:wangwu,age:24
name:zhaoliu,age:26
name:zhangsan,age:20
name:zhangsan,age:22
5.2 比较器排序
比较器排序的实现方式是新建一个比较器类，继承接口Comparator，重写接口中的Compare()方法。
注意：使用此种方式Student类不需要实现接口Comparable，更不需要重写该接口的方法compareTo。
package collection;
import java.util.Comparator;
public class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
// 排序规则描述如下
// 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
// 如果姓名的长度相同，按字典顺序比较String
// 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面
int orderByNameLength = o1.getName().length() - o2.getName().length();
int orderByName = orderByNameLength == 0 ? o1.getName().compareTo(o2.getName()) : orderByNameLength;
int orderByAge = orderByName == 0 ? o1.getAge() - o2.getAge() : orderByName;
return orderByAge;
}
}然后修改下验证代码中声明studentTreeSet的代码即可：
TreeSet<Student> studentTreeSet = new TreeSet<>(new StudentComparator());输出结果和使用自然排序的输出结果完全一样。
6. 源码及参考
Java集合中List,Set以及Map等集合体系详解(史上最全)
7. 最后
打个小广告，欢迎扫码关注微信公众号：「申城异乡人」，定期分享Java技术干货，让我们一起进步。
相关文章