Java集合系列(三):HashSet、LinkedHashSet、TreeSet的使用方法及区别

3,670 阅读10分钟

本篇博客主要讲解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种方式:

  1. 迭代器遍历
  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 清空集合

清空HashSet中所有元素的使用方法如下所示:

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说我也不知道咋排序,还是甩锅抛出异常吧,哈哈。

怎么解决呢?有以下两种方式:

  1. 自然排序
  2. 比较器排序

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等集合体系详解(史上最全)