从源码角度解读Java Set接口底层实现原理

2024-01-28 12:22:04 浏览数 (1)

  咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

代码语言：js复制
环境说明：Windows 10   IntelliJ IDEA 2021.3.2   Jdk 1.8

前言

  Set是Java集合框架中的一个接口，它继承了Collection接口，并添加了一些独有的方法。Set可看做是没有重复元素的Collection，它的实现类包括HashSet、TreeSet等。本文将从源码的角度来解读Set接口的底层实现原理。

摘要

  本文将对Java Set接口进行详细的解读，包括Set的概述、源代码解析、应用场景案例、优缺点分析、类代码方法介绍和测试用例等方面。

Set接口

概述

  Set是一个不允许重复元素的集合。它继承了Collection接口，最基本的操作包括添加元素、检查元素是否存在、删除元素等。Set接口的实现类包括HashSet、TreeSet等。HashSet是基于哈希表的实现，TreeSet是基于红黑树的实现。

源代码解析

Set

  Set接口是Java集合框架中的一种接口，它表示一组无序且不重复的元素。Set接口继承自Collection接口，因此它具有Collection接口的所有方法，但是在Set接口中，添加重复元素是不允许的。Set接口有两个主要的实现类：HashSet和TreeSet。其中，HashSet基于哈希表实现，对于非Null元素具有O(1)的插入和查找时间复杂度；而TreeSet基于红黑树实现，对于有序集合的操作具有良好的性能表现。在使用Set接口时，可以通过迭代器遍历元素，也可以使用foreach语句遍历元素。

  如下是部分源码截图：

HashSet

  HashSet基于哈希表实现，它使用了一个称为“hash表”的数组来存储元素。当我们向HashSet中添加元素时，首先会对元素进行哈希，并通过哈希值来确定元素在数组中的位置。如果该位置已经有元素了，就会通过equals方法来判断是否重复，如果重复则不添加，如果不重复则添加到该位置。当然，由于哈希表中可能会存在多个元素都哈希到同一个位置的情况，因此这些元素会被存储在同一个位置上，形成一个链表。在查找元素时，先通过哈希值定位到链表的头部，然后在链表中进行搜索，直到找到匹配的元素或到达链表的末尾。

代码语言：java复制
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
}

  这是一个实现了 HashSet 数据结构的 Java 类。HashSet 继承了 AbstractSet 类，同时实现了 Set 接口和 Cloneable 和 Serializable 接口。

  HashSet 内部使用 HashMap 来存储元素，其中元素作为 key ，一个 static final Object 作为 value，即：

代码语言：java复制
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

  在构造器中，HashSet 实例化了一个空的 HashMap 对象：

代码语言：java复制
public HashSet() {
    map = new HashMap<>();
}

  向 HashSet 中添加元素时，HashSet 调用 HashMap 的 put() 方法。当新元素没有在 HashMap 中存在时，put() 方法返回 null ，此时 HashSet 返回 true，表示添加成功。如果元素已经存在于 HashMap（即已经在 HashSet 中），那么 put() 方法返回已经存在的 Object，此时 HashSet 返回 false，表示添加失败。

代码语言：java复制
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

  判断 HashSet 是否包含指定元素时，HashSet 调用 HashMap 的 containsKey() 方法。如果 HashMap 中包含该元素，则 HashSet 返回 true，否则返回 false。

代码语言：java复制
public boolean contains(Object o) {
    return map.containsKey(o);
}

  从 HashSet 中移除指定元素时，HashSet 调用 HashMap 的 remove() 方法。如果该元素存在于 HashMap 中（即在 HashSet 中），则返回 true，否则返回 false。

代码语言：java复制
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

  如下是部分源码截图：

TreeSet

  TreeSet基于红黑树实现，它是一种自平衡的二叉查找树。每个节点都有一个额外的颜色属性，只能是红色或黑色。红黑树的基本操作包括插入、删除和查找。当我们向TreeSet中添加元素时，它会根据元素的大小来将元素添加到树中的合适位置。对于每个节点，其左子树的所有元素都比该节点的元素小，右子树的所有元素都比该节点的元素大。在删除时，如果要删除的节点有两个子节点，会先在右子树中找到最小元素，然后将该节点的元素替换为最小元素。删除最小元素就是从根节点开始，一直找到最左侧的节点即可。

代码语言：java复制
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
}

  这段代码定义了一个泛型类TreeSet<E>，继承了AbstractSet<E>类，并实现了接口NavigableSet<E>,Cloneable和java.io.Serializable。

  类中的m变量是一个NavigableMap<E,Object>类型的成员变量，TreeSet内部实际上是通过使用TreeMap<E,Object>实现的。

  类中还定义了PRESENT静态常量，用于表示在TreeSet中已经存在的元素。

  TreeSet类中的add方法实现了向集合中添加元素的功能，使用了NavigableMap中的put方法，如果添加的元素在集合中不存在，则返回null，否则返回PRESENT。

  contains方法判断集合中是否包含某个元素。使用了NavigableMap中的containsKey方法。

  remove方法实现删除某个元素的功能，使用NavigableMap中的remove方法，如果删除成功，则返回PRESENT。

  如下是部分源码截图：

应用场景案例

  Set的一个常见应用场景就是去重。由于Set中不允许存在重复元素，因此我们可以利用Set来去除列表中的重复元素，代码如下：

代码演示

代码语言：java复制
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 2, 1));
Set<Integer> set = new HashSet<>(list);
list = new ArrayList<>(set);
System.out.println(list); // output: [1, 2, 3]

代码分析

  根据如上代码，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。

  该代码创建了一个包含重复元素的整型列表list，并使用list初始化了一个整型哈希集合set。然后，通过将set转换回一个新的ArrayList对象，生成一个不带重复元素的整型列表list。最后，输出list的元素。 因此，代码输出应该是1, 2, 3。

优缺点分析

优点

  1. Set接口的实现类可以高效地检查元素是否存在；
  2. Set接口的实现类不允许存在重复元素，可以用来进行去重操作；
  3. HashSet的添加、删除、查找操作时间复杂度为O(1)；TreeSet的添加、删除、查找操作时间复杂度为O(logN)。

缺点

  1. 如果需要有序存储元素，那么需要使用TreeSet，但是由于TreeSet是基于红黑树实现的，因此占用内存空间较大；
  2. HashSet在哈希冲突的情况下，会导致链表长度增加，从而影响查找效率；
  3. HashSet在遍历元素时，元素的顺序不能保证。

类代码方法介绍

HashSet

  1. add(E e)：向集合中添加元素；
  2. clear()：清空集合中所有元素；
  3. contains(Object o)：判断集合中是否存在指定的元素；
  4. isEmpty()：判断集合是否为空；
  5. iterator()：返回一个用于遍历集合的迭代器；
  6. remove(Object o)：从集合中移除指定的元素；
  7. size()：返回集合中元素的数量。

TreeSet

  1. add(E e)：向集合中添加元素；
  2. ceiling(E e)：返回集合中大于等于指定元素的最小元素；
  3. clear()：清空集合中所有元素；
  4. contains(Object o)：判断集合中是否存在指定的元素；
  5. descendingIterator()：返回一个逆序遍历集合的迭代器；
  6. first()：返回集合中的第一个元素；
  7. headSet(E toElement, boolean inclusive)：返回集合中小于指定元素的子集；
  8. isEmpty()：判断集合是否为空；
  9. iterator()：返回一个用于遍历集合的迭代器；
  10. last()：返回集合中的最后一个元素；
  11. remove(Object o)：从集合中移除指定的元素；
  12. size()：返回集合中元素的数量；
  13. subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)：返回集合中大于等于fromElement且小于等于toElement的子集；
  14. tailSet(E fromElement, boolean inclusive)：返回集合中大于等于指定元素的子集。

测试用例

下面是一些测试用例，展示了Set接口的一些基本操作：

代码语言：java复制
package com.demo.javase.day61;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * @Author bug菌
 * @Date 2023-11-06 10:33
 */
public class SetTest {

    public static void main(String[] args) {

        // 创建一个 HashSet 对象
        Set<String> set = new HashSet<String>();

        // 向集合中添加元素
        set.add("Java");
        set.add("C  ");
        set.add("Python");

        // 打印出集合中的元素个数
        System.out.println("集合中的元素个数为："   set.size());

        // 判断集合是否为空
        System.out.println("集合是否为空："   set.isEmpty());

        // 判断集合中是否包含某个元素
        System.out.println("集合中是否包含 Python："   set.contains("Python"));

        // 从集合中移除某个元素
        set.remove("C  ");
        System.out.println("从集合中移除元素后，集合中的元素个数为："   set.size());

        // 使用迭代器遍历集合中的元素
        Iterator<String> iterator = set.iterator();
        System.out.println("遍历集合中的元素：");
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
        }

        // 清空集合中的所有元素
        set.clear();
        System.out.println("清空集合中的元素后，集合中的元素个数为："   set.size());
    }
}

该测试用例使用了HashSet作为实现Set接口的具体类，并测试了以下基本操作：

  1. 向集合中添加元素
  2. 打印出集合中的元素个数
  3. 判断集合是否为空
  4. 判断集合中是否包含某个元素
  5. 从集合中移除某个元素
  6. 使用迭代器遍历集合中的元素
  7. 清空集合中的所有元素

测试结果

  根据如上测试用例，本地测试结果如下，仅供参考，你们也可以自行修改测试用例或者添加更多的测试数据或测试方法，进行熟练学习以此加深理解。

当运行该测试用例后，我们将得到以下输出结果：

代码语言：java复制
集合中的元素个数为：3
集合是否为空：false
集合中是否包含 Python：true
从集合中移除元素后，集合中的元素个数为：2
遍历集合中的元素：
Java
Python
清空集合中的元素后，集合中的元素个数为：0

具体执行截图如下：

测试代码分析

  根据如上测试用例，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。

这段代码演示了如何使用Java中的Set接口和HashSet类。具体来说，代码实现了：

1.创建一个HashSet对象。

2.向集合中添加元素。

3.打印出集合中的元素个数。

4.判断集合是否为空。

5.判断集合中是否包含某个元素。

6.从集合中移除某个元素。

7.使用迭代器遍历集合中的元素。

8.清空集合中的所有元素。

  从这段代码可以看出，Set接口和HashSet类可以帮助我们快速地实现集合的添加、删除、查找等操作，并且还支持迭代器遍历集合中的所有元素。

  ...

  好啦，这期的内容就基本接近尾声啦，若你想学习更多，可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》，本专栏致力打造最硬核 Java 零基础系列学习内容，

2024腾讯·技术创作特训营第五期 java8

0 人点赞