滚雪球学Java(62):HashSet的底层实现原理解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 【6月更文挑战第16天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!

在这里插入图片描述

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

在这里插入图片描述


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

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

@[toc]

前言

  在Java中,我们常常使用HashSet来存储一组不重复的对象,但是在使用它的时候,我们可能并没有意识到它的底层实现原理。本篇文章将会深入分析HashSet的底层实现原理,以便更好地理解它的使用和优化。

摘要

  本篇文章将会深入分析Java中HashSet的底层实现原理,包括HashSet的源代码解析,应用场景案例,优缺点分析,类代码方法介绍,以及测试用例和全文小结。

HashSet

概述

  HashSet是Java中一个常用的集合类,它继承了AbstractSet类,并且实现了Set接口。与List不同的是,HashSet中的元素是无序的,并且不允许有重复的元素。在使用HashSet时,我们通常会使用add()方法来向其中添加元素,并且使用contains()方法来判断元素是否存在于集合中。

  HashSet的底层实现原理是基于HashMap实现的。HashSet中的元素在底层都是存储在HashMap的key上的,而value则是一个"PRESENT"常量,它并没有实际的作用,只是用于填充HashMap的value值。因此,HashSet中的元素都是唯一的,并且无序。

源代码解析

下面是HashSet的源代码:

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;

    // 内部默认的value值
    private static final Object PRESENT = new Object();

    // 无参构造函数,默认创建一个空的HashSet
    public HashSet() {
   
   
        map = new HashMap<>();
    }

    // 可以接收集合类型的构造函数
    public HashSet(Collection<? extends E> c) {
   
   
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    // 可以接收初始容量和负载因子的构造函数
    public HashSet(int initialCapacity, float loadFactor) {
   
   
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // 可以接收初始容量的构造函数
    public HashSet(int initialCapacity) {
   
   
        map = new HashMap<>(initialCapacity);
    }

    // 添加元素到HashSet中
    public boolean add(E e) {
   
   
        return map.put(e, PRESENT)==null;
    }

    // 将另一个集合中的元素添加到当前HashSet中
    public boolean addAll(Collection<? extends E> c) {
   
   
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

    // 清空HashSet
    public void clear() {
   
   
        map.clear();
    }

    // 判断HashSet是否包含某个元素
    public boolean contains(Object o) {
   
   
        return map.containsKey(o);
    }

    // 判断HashSet是否为空
    public boolean isEmpty() {
   
   
        return map.isEmpty();
    }

    // 删除HashSet中的某个元素
    public boolean remove(Object o) {
   
   
        return map.remove(o)==PRESENT;
    }

    // 获取HashSet的大小
    public int size() {
   
   
        return map.size();
    }

    // 返回HashSet的对象数组
    public Object[] toArray() {
   
   
        return map.keySet().toArray();
    }

    // 返回HashSet的泛型数组
    public <T> T[] toArray(T[] a) {
   
   
        return map.keySet().toArray(a);
    }

    // 返回HashSet的迭代器
    public Iterator<E> iterator() {
   
   
        return map.keySet().iterator();
    }

    // 克隆当前HashSet
    public Object clone() {
   
   
        try {
   
   
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E,Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
   
   
            throw new InternalError(e);
        }
    }

    // 序列化
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
   
   
        s.defaultWriteObject();
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());
        s.writeInt(map.size());
        for (E e : map.keySet())
            s.writeObject(e);
    }

    // 反序列化
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
   
   
        s.defaultReadObject();
        int capacity = s.readInt();
        if (capacity < 0) {
   
   
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
   
   
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }
        int size = s.readInt();
        if (size < 0) {
   
   
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<>(capacity, loadFactor) :
               new HashMap<>(capacity, loadFactor));
        for (int i=0; i<size; i++) {
   
   
            E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }
}

  从上面的源代码可以看出,HashSet实际上是基于HashMap实现的,也就是说HashSet本身的操作都是委托给底层的HashMap来完成的。如下是对该源码的一些分析:

  该HashSet类实现了Set接口,是一个基于HashMap实现的无序且不允许重复元素的集合。

  该类拥有一系列构造函数,可以根据不同的参数创建不同的HashSet。其中,无参构造函数默认创建一个空的HashSet,可以接收集合类型的构造函数会将传入的集合中的元素添加到当前HashSet中,可以接收初始容量和负载因子的构造函数会创建一个空的HashMap并指定初始容量和负载因子,可以接收初始容量的构造函数会创建一个空的HashMap并指定初始容量。

  该类定义了一系列方法,包括添加元素到HashSet中、将另一个集合中的元素添加到当前HashSet中、判断HashSet是否包含某个元素、从HashSet中删除某个元素、获取HashSet的大小、判断HashSet是否为空、清空HashSet等方法。

  该类还实现了Cloneable和Serializable接口,可以实现克隆和序列化。其中,克隆时会克隆一个新的HashSet并将当前HashSet中的所有元素添加到新的HashSet中,序列化时会将当前HashSet中的所有元素按顺序写到输出流中,并在反序列化时读取这些元素并添加到新的HashSet中。

  该类的内部实现使用HashMap来存储HashSet中的元素,利用HashMap不允许键重复的特性保证HashSet中元素的唯一性。同时,HashSet中的元素顺序是不确定的,因为HashMap中元素的顺序是基于哈希算法裂解的。

  此外,可以看到,HashSet中定义了一个transient的HashMap对象map,这个Map对象中的key存储了HashSet中的元素,而value则使用了一个"PRESENT"常量,它并没有实际的作用,只是用于填充Map中的value值。

  在HashSet中,添加元素的方法是add(),我们来详细解析一下这个方法的实现:

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

在这里插入图片描述

  首先,add()方法从map中调用put()方法,并将元素e作为key,"PRESENT"常量作为value加入map中。如果put()方法返回null,则说明添加的元素在HashSet中并不存在,返回true表示添加成功;否则说明添加的元素已经存在于HashSet中,返回false表示添加失败。

  如下是部分源码截图:

在这里插入图片描述

应用场景案例

HashSet的应用场景非常广泛,常见的使用场景有:

  1. 去重:使用HashSet可以非常方便地去重,只需要将需要去重的对象添加到HashSet中,最后再将HashSet转换成需要的数据结构即可。

  2. 查找:由于HashSet中的元素都是唯一的,因此我们可以使用HashSet来查找某个元素是否存在于HashSet中。

  3. 缓存:由于HashSet具有快速查找和去重的特点,因此在缓存场景中也经常使用HashSet来存储数据。

优缺点分析

优点

  1. 去重:HashSet中的元素都是唯一的,这个特点非常适合去重场景。

  2. 快速查找:由于HashSet中的元素是基于HashMap实现的,因此在查找元素时具有非常快的速度。

  3. 高效率:HashSet的实现非常高效,支持快速的添加、删除、查找等操作。

缺点

  1. 无序:由于HashSet中的元素是无序的,因此如果需要有序的元素,我们需要使用LinkedHashSet。

  2. 线程不安全:HashSet是线程不安全的,因此在多线程的情况下,我们需要使用ConcurrentHashMap。

类代码方法介绍

  1. add(E e)方法:向HashSet中添加元素,并返回是否添加成功。

  2. addAll(Collection<? extends E> c)方法:将另一个集合中的元素添加到当前HashSet中,并返回是否添加成功。

  3. clear()方法:清空HashSet中的所有元素。

  4. contains(Object o)方法:判断HashSet中是否包含某个元素。

  5. isEmpty()方法:判断HashSet是否为空。

  6. remove(Object o)方法:从HashSet中删除某个元素,并返回是否删除成功。

  7. size()方法:获取HashSet的大小。

  如下是部分源码截图:

在这里插入图片描述
在这里插入图片描述

常用方法

HashSet的常用方法列举如下:

  1. iterator()方法:返回HashSet的迭代器。

  2. toArray()方法:返回一个包含HashSet中所有元素的Object数组。

  3. toArray(T[] a)方法:返回一个包含HashSet中所有元素的泛型数组。

  4. clone()方法:克隆当前HashSet。

  5. equals(Object o)方法:判断当前HashSet是否与另一个对象o相等。

  6. hashCode()方法:返回当前HashSet的哈希码。

  7. retainAll(Collection<?> c)方法:保留HashSet与另一个集合c中相同的元素,删除不同的元素。

  8. removeAll(Collection<?> c)方法:删除HashSet中与另一个集合c中相同的元素。

测试用例

package com.demo.javase.day62;

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

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

    public static void main(String[] args) {
   
   
        // 创建一个空的HashSet
        HashSet<String> set = new HashSet<>();

        // 添加元素到HashSet中
        set.add("A");
        set.add("B");
        set.add("C");
        set.add("D");
        set.add("E");

        // 判断HashSet是否包含某个元素
        System.out.println(set.contains("D"));

        // 删除HashSet中的某个元素
        set.remove("B");

        // 获取HashSet的大小
        System.out.println(set.size());

        // 遍历HashSet
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
   
   
            System.out.println(it.next());
        }

        // 清空HashSet
        set.clear();

        // 判断HashSet是否为空
        System.out.println(set.isEmpty());
    }
}

测试结果

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

在这里插入图片描述

测试代码分析

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

  此代码演示了如何使用HashSet。首先,它创建了一个空的HashSet并添加了五个元素。然后,它检查HashSet是否包含一个给定的元素“D”,并删除元素“B”。接下来,它打印HashSet的大小并遍历HashSet并打印每个元素。然后,它清空HashSet并检查HashSet是否为空。此代码演示了如何使用HashSet。首先,它创建了一个空的HashSet并添加了五个元素。然后,它检查HashSet是否包含一个给定的元素“D”,并删除元素“B”。接下来,它打印HashSet的大小并遍历HashSet并打印每个元素。然后,它清空HashSet并检查HashSet是否为空。

小结

  本篇文章深入分析了Java中HashSet的底层实现原理,包括源代码解析、应用场景案例、优缺点分析、类代码方法介绍和测试用例。通过学习HashSet的底层实现原理,我们能够更好地理解HashSet的使用和优化,并且能够更好地应用HashSet来解决实际问题。

总结

  本篇文章深入分析了Java中HashSet的底层实现原理,包括源代码解析、应用场景案例、优缺点分析、类代码方法介绍和测试用例。从源代码解析可以看出HashSet是基于HashMap实现的,添加元素的方法是add()方法,它将元素作为key,"PRESENT"常量作为value加入map中,成功返回true,失败返回false。HashSet的优点包括去重、快速查找和高效率,缺点包括无序和线程不安全。常用方法包括iterator()、toArray()、clone()等,测试用例包括添加元素、判断是否包含元素、遍历、删除元素等。

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

附录源码

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

☀️建议/推荐你


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

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


目录
相关文章
|
12天前
|
存储 算法 安全
Java面试题:Java内存模型及相关知识点深度解析,Java虚拟机的内存结构及各部分作用,详解Java的垃圾回收机制,谈谈你对Java内存溢出(OutOfMemoryError)的理解?
Java面试题:Java内存模型及相关知识点深度解析,Java虚拟机的内存结构及各部分作用,详解Java的垃圾回收机制,谈谈你对Java内存溢出(OutOfMemoryError)的理解?
22 0
|
5天前
|
存储 监控 算法
Java 内存管理与垃圾回收机制深度解析
本文深入探讨了Java的内存管理与垃圾回收(GC)机制,从JVM内存结构出发,详细分析了堆、栈、方法区的职能及交互。文章重点讨论了垃圾回收的核心概念、常见算法以及调优策略,旨在为Java开发者提供一套系统的内存管理和性能优化指南。 【7月更文挑战第17天】
|
5天前
|
Java 编译器 开发者
Java 内存模型深度解析
本文旨在深入探讨Java内存模型的复杂性及其对并发编程的影响。通过揭示内存模型的核心原理、JMM的结构,并结合具体案例和数据分析,本文将帮助读者理解Java内存模型如何确保多线程程序的正确性和性能,以及如何在实际应用中有效利用这一模型进行高效的并发编程。 【7月更文挑战第17天】
12 4
|
6天前
|
Java
Java中的异常处理机制深度解析
本文旨在深入探讨Java语言中异常处理的机制,从基础概念到高级应用,全面剖析try-catch-finally语句、自定义异常以及异常链追踪等核心内容。通过实例演示和代码分析,揭示异常处理在Java程序设计中的重要性和应用技巧,帮助读者构建更为健壮和易于维护的程序。
|
8天前
|
监控 Java API
Java并发编程之线程池深度解析
【7月更文挑战第14天】在Java并发编程领域,线程池是提升性能、管理资源的关键工具。本文将深入探讨线程池的核心概念、内部工作原理以及如何有效使用线程池来处理并发任务,旨在为读者提供一套完整的线程池使用和优化策略。
|
12天前
|
存储 安全 Java
Java面试题:Java内存管理、多线程与并发框架:一道综合性面试题的深度解析,描述Java内存模型,并解释如何在应用中优化内存使用,阐述Java多线程的创建和管理方式,并讨论线程安全问题
Java面试题:Java内存管理、多线程与并发框架:一道综合性面试题的深度解析,描述Java内存模型,并解释如何在应用中优化内存使用,阐述Java多线程的创建和管理方式,并讨论线程安全问题
11 0
|
12天前
|
存储 并行计算 安全
Java面试题:Java内存管理、多线程与并发框架的面试题解析与知识点梳理,深入Java内存模型与垃圾回收机制,Java多线程机制与线程安全,Java并发工具包与框架的应用
Java面试题:Java内存管理、多线程与并发框架的面试题解析与知识点梳理,深入Java内存模型与垃圾回收机制,Java多线程机制与线程安全,Java并发工具包与框架的应用
19 0
|
1月前
|
XML Java 数据格式
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
33 3
|
18天前
|
存储 安全 Java
深度长文解析SpringWebFlux响应式框架15个核心组件源码
以上是Spring WebFlux 框架核心组件的全部介绍了,希望可以帮助你全面深入的理解 WebFlux的原理,关注【威哥爱编程】,主页里可查看V哥每天更新的原创技术内容,让我们一起成长。
|
19天前
|
关系型数据库 分布式数据库 数据库
PolarDB-X源码解析:揭秘分布式事务处理
【7月更文挑战第3天】**PolarDB-X源码解析:揭秘分布式事务处理** PolarDB-X,应对大规模分布式事务挑战,基于2PC协议确保ACID特性。通过预提交和提交阶段保证原子性与一致性,使用一致性快照隔离和乐观锁减少冲突,结合故障恢复机制确保高可用。源码中的事务管理逻辑展现了优化的分布式事务处理流程,为开发者提供了洞察分布式数据库核心技术的窗口。随着开源社区的发展,更多创新实践将促进数据库技术进步。
21 3

推荐镜像

更多