滚雪球学Java(61):从源码角度解读Java Set接口底层实现原理

简介: 【6月更文挑战第15天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!

在这里插入图片描述

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

在这里插入图片描述


🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

@[toc]

前言

  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方法来判断是否重复,如果重复则不添加,如果不重复则添加到该位置。当然,由于哈希表中可能会存在多个元素都哈希到同一个位置的情况,因此这些元素会被存储在同一个位置上,形成一个链表。在查找元素时,先通过哈希值定位到链表的头部,然后在链表中进行搜索,直到找到匹配的元素或到达链表的末尾。

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,即:

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

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

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

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

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

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

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

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

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

  如下是部分源码截图:

在这里插入图片描述

TreeSet

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

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>,Cloneablejava.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来去除列表中的重复元素,代码如下:

代码演示

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接口的一些基本操作:

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. 清空集合中的所有元素

测试结果

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

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

集合中的元素个数为:3
集合是否为空:false
集合中是否包含 Python:true
从集合中移除元素后,集合中的元素个数为:2
遍历集合中的元素:
Java
Python
清空集合中的元素后,集合中的元素个数为:0

具体执行截图如下:

在这里插入图片描述

测试代码分析

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

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

1.创建一个HashSet对象。

2.向集合中添加元素。

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

4.判断集合是否为空。

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

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

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

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

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

  ...
  好啦,这期的内容就基本接近尾声啦,若你想学习更多,可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》,本专栏致力打造最硬核 Java 零基础系列学习内容,🚀打造全网精品硬核专栏,带你直线超车;欢迎大家订阅持续学习。

附录源码

  如上涉及所有源码均已上传同步在「Gitee」,提供给同学们一对一参考学习,辅助你更迅速的掌握。

☀️建议/推荐你


  无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。

  最后,如果这篇文章对你有所帮助,帮忙给作者来个一键三连,关注、点赞、收藏,您的支持就是我坚持写作最大的动力。


目录
相关文章
|
6天前
|
Java 应用服务中间件 开发者
Java面试题:解释Spring Boot的优势及其自动配置原理
Java面试题:解释Spring Boot的优势及其自动配置原理
28 0
|
5天前
|
JavaScript Java 测试技术
基于Java的智慧医疗服务平台系统设计和实现(源码+LW+部署讲解)
基于Java的智慧医疗服务平台系统设计和实现(源码+LW+部署讲解)
26 8
|
5天前
|
JavaScript Java 测试技术
基于Java的人事管理系统设计和实现(源码+LW+部署讲解)
基于Java的人事管理系统设计和实现(源码+LW+部署讲解)
18 7
|
5天前
|
JavaScript Java 测试技术
基于Java的儿童福利院管理系统设计和实现(源码+LW+部署讲解)
基于Java的儿童福利院管理系统设计和实现(源码+LW+部署讲解)
16 7
|
6天前
|
缓存 监控 算法
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
31 8
|
4天前
|
存储 监控 Java
揭秘Java虚拟机:探索JVM的工作原理与性能优化
本文深入探讨了Java虚拟机(JVM)的核心机制,从类加载到垃圾回收,再到即时编译技术,揭示了这些复杂过程如何共同作用于Java程序的性能表现。通过分析现代JVM的内存管理策略和性能监控工具,文章提供了实用的调优建议,帮助开发者有效提升Java应用的性能。
23 3
|
6天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
15 1
|
6天前
|
缓存 Java
Java面试题:描述Java中的线程池及其实现方式,详细说明其原理
Java面试题:描述Java中的线程池及其实现方式,详细说明其原理
10 0
|
6天前
|
设计模式 Java
Java面试题:描述观察者模式的工作原理及其在Java中的应用。
Java面试题:描述观察者模式的工作原理及其在Java中的应用。
10 0
|
10月前
|
Java
Java接口和抽象类
Java接口和抽象类
66 0