Java的HashSet源码分析

🕗 发布于 2024-07-19 10:10 java 开发语言 hash

前言

在编程的世界里，有一种神奇的工具，它小巧却强大，灵活而可靠，它就是 HashSet。然而，你是否曾经好奇过，这么强大的工具，其背后的实现原理是怎样的呢？今天，让我们一起揭开 HashSet 源码的神秘面纱，探索这个 Java 世界中的神奇数据结构。

首先，我们需要明白，HashSet 并不是一个简单的集合，它是基于哈希表实现的一种集合。哈希表是一种数据结构，通过哈希函数将元素映射到数组的一个位置，实现快速的查找。而 HashSet 则在此基础上，增加了一些额外的功能，使得它在存储和查找元素时更加高效。

在这里插入图片描述

优点

HashSet是一种非常常用的集合类型，因为它具有许多优点：

快速查找： HashSet内部是基于哈希表实现的，这意味着你可以在常数时间内（O(1)）查找元素，无论集合中有多少元素。这使得HashSet非常适用于需要快速查找元素的场景，例如检查元素是否存在。
高效去重： 由于HashSet不允许重复元素，它提供了一种方便的方式来去重。无论你有多少重复的元素，最终HashSet中只会包含唯一的元素，这可以大大简化去重操作。
无序性： HashSet中的元素是无序的，它不维护元素的插入顺序或排序顺序。这在某些情况下可以带来性能上的优势，因为不需要维护元素的顺序。
线程不安全： HashSet是非线程安全的，这意味着在多线程环境中使用HashSet可能需要额外的同步措施。如果需要在多线程环境中使用，可以考虑使用Collections.synchronizedSet()方法来创建线程安全的HashSet。

HashSet的内部实现

HashSet的内部实现是基于HashMap，实际上，HashSet是通过创建一个基于HashMap的实例来实现的。HashSet使用HashMap中的键来存储集合中的元素，而值始终是一个虚拟常量（PRESENT），它在HashSet中不起实际作用。

注意事项

虽然HashSet在许多场景中非常有用，但也有一些需要注意的事项：

无序性： 如果你需要按照元素的插入顺序或特定顺序遍历集合元素，HashSet可能不适合你。在这种情况下，可以考虑使用LinkedHashSet，它是HashSet的一个变种，保留了元素的插入顺序。
哈希冲突： 在HashSet内部，不同的元素可能会产生相同的哈希码，这被称为哈希冲突。HashSet使用链表解决哈希冲突，当链表长度超过一定阈值时，链表会转换为红黑树以提高性能。
元素类型： HashSet中的元素需要正确实现hashCode()和equals()方法，以确保元素能够正确存储和查找。如果你自定义了类，并将其用作HashSet中的元素，务必重写这两个方法。

工作原理

那么，HashSet 是如何工作的呢？它的工作原理可以简化为以下几个步骤：

初始化：当我们创建一个 HashSet 对象时，它会调用构造函数，创建一个新的哈希表。

/**
 * 构造一个空的 `HashSet`，具有默认的初始容量（16）和默认的负载因子（0.75）。
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * 构造一个包含指定集合中元素的新集合。`HashMap` 使用默认的负载因子（0.75）和足够容纳指定集合中元素的初始容量。
 *
 * @param c 要放入此集合的元素的集合
 * @throws NullPointerException 如果指定的集合为null
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

/**
 * 构造一个新的、空的集合；底层的 `HashMap` 实例具有指定的初始容量和默认的负载因子（0.75）。
 *
 * @param      initialCapacity   哈希表的初始容量
 * @throws     IllegalArgumentException 如果初始容量小于零
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}


/**
 * 构造一个新的、空的集合；底层的 `HashMap` 实例具有指定的初始容量和指定的负载因子。
 *
 * @param      initialCapacity   哈希映射的初始容量
 * @param      loadFactor        哈希映射的负载因子
 * @throws     IllegalArgumentException 如果初始容量小于零，或者负载因子不是正数
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * 构造一个新的、空的链式哈希集合。 （这是包私有构造函数，仅由LinkedHashSet使用。）底层的
 * HashMap 实例是一个具有指定初始容量和指定负载因子的LinkedHashMap。
 *
 * @param      initialCapacity   哈希映射的初始容量
 * @param      loadFactor        哈希映射的负载因子
 * @param      dummy             忽略的参数（用于区分此构造函数和其他int、float构造函数。）
 * @throws     IllegalArgumentException 如果初始容量小于零，或者负载因子不是正数
 */
public HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

public HashSet(): 默认构造方法创建一个具有默认初始容量（16）和默认负载因子（0.75）的 HashSet 对象。
HashSet(Collection<? extends E> c): 构造函数接受一个集合作为参数，将集合中的元素放入新的HashSet中。它会根据集合的大小自动计算合适的初始容量，并使用默认的负载因子0.75。
public HashSet(int initialCapacity): 带初始容量参数的构造方法创建一个具有指定初始容量和默认负载因子的 HashSet 对象。
public HashSet(int initialCapacity, float loadFactor): 带初始容量和负载因子参数的构造方法创建一个 HashSet 对象。
public HashSet(int initialCapacity, float loadFactor, boolean dummy): 这个构造函数是包私有的，仅供LinkedHashSet使用。它创建一个基于LinkedHashMap的HashSet，允许指定初始容量和负载因子，同时忽略了一个名为dummy的参数。

插入：当我们向HashSet中插入一个元素时，首先会使用元素的hashCode()方法计算出其在哈希表中的位置，然后检查该位置是否已经有Node对象存在。如果不存在，则创建一个新的Node对象并放入该位置；如果存在，则不执行插入操作。

/**
 * 将指定的元素添加到 `HashSet` 中。
 */
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

public boolean add(E e): 此方法将指定的元素添加到 HashSet 中。它实际上是通过调用底层的 HashMap 的 put 方法来实现的。如果 put 方法返回 null，则表示元素之前不存在，插入成功。

查找：当我们需要查找一个元素是否存在于HashSet中时，同样会先计算元素的hashCode()值，然后根据该值找到数组中的一个位置。如果该位置的Node对象包含要查找的元素，返回true，否则返回false。

/**
 * 如果 `HashSet` 包含指定的元素，则返回 `true`。
 */
public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean contains(Object o): 此方法用于检查 HashSet 是否包含指定的元素。它实际上是通过调用底层的 HashMap 的 containsKey 方法来实现的。

删除：当我们需要从HashSet中删除一个元素时，首先计算元素的hashCode()值，然后检查该位置的Node对象是否包含要删除的元素。如果包含，则将该元素从哈希表中移除；如果不包含，则不执行删除操作。

/**
 * 如果 `HashSet` 中存在指定的元素，则将其删除。
 */
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

public boolean remove(Object o): 此方法用于从 HashSet 中删除指定的元素。它实际上是通过调用底层的 HashMap 的 remove 方法来实现的。如果 remove 方法返回 PRESENT，则表示删除成功。

使用场景

在Java中，HashSet是一个常用的数据结构，适用于多种编程场景。以下是一些常见的HashSet使用场景，每个场景都伴随着相应的Java代码示例：

1. 去重数据

import java.util.HashSet;

public class DeduplicationExample {
    public static void main(String[] args) {
        HashSet<String> uniqueNames = new HashSet<>();
        
        uniqueNames.add("Alice");
        uniqueNames.add("Bob");
        uniqueNames.add("Alice"); // 重复元素，不会被添加
        
        System.out.println(uniqueNames); // 输出: [Bob, Alice]
    }
}

2. 快速成员检查

import java.util.HashSet;

public class MemberCheckExample {
    public static void main(String[] args) {
        HashSet<Integer> numbers = new HashSet<>();
        
        numbers.add(10);
        numbers.add(20);
        
        boolean contains = numbers.contains(10); // 成员检查
        
        System.out.println("Contains 10: " + contains); // 输出: Contains 10: true
    }
}

3. 查找交集、并集和差集

import java.util.HashSet;

public class SetOperationsExample {
    public static void main(String[] args) {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);

        set2.add(2);
        set2.add(3);
        set2.add(4);

        // 交集
        set1.retainAll(set2);
        System.out.println("Intersection: " + set1); // 输出: Intersection: [2, 3]

        // 并集
        set1.addAll(set2);
        System.out.println("Union: " + set1); // 输出: Union: [1, 2, 3, 4]

        // 差集
        set1.removeAll(set2);
        System.out.println("Difference: " + set1); // 输出: Difference: [1]
}
}

4. 过滤元素

import java.util.HashSet;
import java.util.stream.Collectors;

public class FilterElementsExample {
    public static void main(String[] args) {
        HashSet<String> names = new HashSet<>();
        
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("David");
        
        // 过滤以字母 'A' 开头的元素
        HashSet<String> filteredNames = names.stream()
            .filter(name -> name.startsWith("A"))
            .collect(Collectors.toCollection(HashSet::new));
            
        System.out.println(filteredNames); // 输出: [Alice]
    }
}

原文地址：https://blog.csdn.net/hellwindy/article/details/140539073

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：2、如何发行自己的数字代币（truffle智能合约项目实战）
下一篇：webrtc QOS方法十三（视频渲染平滑）

【QT基础】创建项目&项目代码解释
本篇文章详细介绍了QT是如何创建项目的，并且解释了项目中各个默认文件代码的意思。内附大量图文。
阅读更多2024-09-20
什么品牌超声波清洗机质量好？四大绝佳超声波清洗机品牌推荐！
在关键部件——声波换能震动器的研发上，团队耗时两年，斥资逾百万，反复经历了上百轮的产品优化试验，深入探究了频率与真空冲击波能量对提升清洁效果及保护清洗物件免受损伤的细微作用。此超声波清洗器呈现出时尚的
阅读更多2024-09-20
基于eBPF的procstat软件追踪程序垃圾回收（GC）事件
procstat是一款基于eBPF的监控软件，运行在Linux平台，主要用于跟踪目标程序的运行状态，并报告异常指标，是分析程序性能问题的一大利器。procstat软件能够用于追踪golang及jvm程
阅读更多2024-09-20
VBA技术资料MF198：禁用下拉拖放
我给VBA的定义：VBA是个人小型自动化处理的有效工具。利用好了，可以大大提高自己的工作效率，而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套，分为初级、中级、高级三大部分，教程是对VB
阅读更多2024-09-20
ISSTA 2024现场精彩：“杰出论文奖”超半数属于中国学者
开幕式还展示了一些有趣的统计，从1990年代至今的年录取率变化趋势，到每篇论文背后作者数量的分布图，再到年投稿量的变化趋势，每一个数字都见证了ISSTA的成长与辉煌，也映射出软件测试与分析领域日益蓬勃
阅读更多2024-09-20
解决selenium爬虫被浏览器检测问题
解决selenium爬虫被浏览器检测问题
阅读更多2024-09-20
极越联手百度这你受得了吗！SU7还能稳坐“7字辈”头把交椅？
方向盘采用了经典的圆形设计，其上的红色按键可轻松切换不同的驾驶模式，为驾驶者提供了更多的操控选择。尾部的扩散器和与车身同色的后保险杠装饰件，不仅提升了车辆的运动感，还让尾部看起来更加饱满和谐。座椅采用
阅读更多2024-09-20
【云安全】云服务安全攻防
本文主要介绍了场景的云服务攻击场景。
阅读更多2024-09-20
工程师 - .NET程序反编译器
它允许开发人员检查已编译的 .NET 应用程序、库和组件的底层代码，即使在无法获得原始源代码的情况下也是如此。.NET Reflector 可将已编译的 .NET 程序集（如`.dll`和`.exe`
阅读更多2024-09-20
【混淆矩阵】Confusion Matrix！定量评价的基础！如何计算全面、准确的定量指标去衡量模型分类的好坏？？
【混淆矩阵】Confusion Matrix！定量评价的基础！学习笔记
阅读更多2024-09-20