【集合】HashSet 源码分析

深碍√TFBOYSˉ_ 2022-10-05 08:50 220阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/jdk-source-code-reading][https_github.com_yihonglei_jdk-source-code-reading]

[HashTable 源码][HashTable]

[HashMap 源码][HashMap]

[ConcurrentHashMap 源码][ConcurrentHashMap]

# 一 概述 #

HashSet 是专用来存放对象的 HashMap，底层用的 HashMap 数据结构存储。

很困惑，HashMap 不也能存储对象吗？为毛还要 HashSet 呢？应用场景是什么，

这个技术存在的价值是什么？下面看看源码吧！

# 二 实例 #

package com.jpeony.collection.set;
    
    import java.util.HashSet;
    import java.util.Set;
    
    /**
     * 存放不重复对象。
     *
     * @author yihonglei
     */
    public class HashSetTest {
        public static void main(String[] args) {
            // add
            Set<String> set = new HashSet<>();
            set.add("a");
            set.add("b");
            set.add("c");
            set.add("d");
            set.add("e");
    
            // remove
            set.remove("e");
    
            // print
            for (String str : set) {
                System.out.println(str);
            }
        }
    }

**运行结果 **

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70][]三 HashSet 底层实现 #

**重点分析 add()方法。**

## 构造器 ##

public HashSet() {
    	// 默认 HashMap 存储
        map = new HashMap<>();
    }

# HashSet\#add() #

// Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

元素的添加底层是 HashMap 的 put 方法，但是，value 每次 add 都会创建一个空对象。

# 四 总结 #

1、我们发现 HashSet 的 add 底层是 HashMap 的 put，只是每次 add 的 value 都是创建一个

哑结点对象，这么说 HashSet 是添加一组数据集合，是否可以用 ArrayList 替代？

有些场景下，不能，从 HashSet 的源码可以看出，HashSet 存储一组没有重复元素的数组，

支持按照对象进行查找元素，就凭这两点，ArrayList 就做不到，ArrayList 不能自然保证元素

的不重复，并且，ArrayList 没法指定对象查找，时间复杂度是 O(n)，而 HashSet 的时间复杂

度是 O(1)，对于 jdk 7 来说，HashMap 最坏退到链表查找 O(n)，在 jdk8，一般退到链表O(n），

大数据量时退到红黑树O(logn)，总体来说，根据对象查找元素，HashSet 时间复杂度优于数组。

2、既然有了 HashMap，为啥还需要 HashSet？HashMap 专注于存储 k-v 结构，而 HashSet

则专注于存储 对象，实际中 HashSet 是不是没怎么用过？其实各种技术源码底层用得还是比较

多的。

**JDK 线程池，工作线程的存储列表。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1][]

主要是方便进行工作线程对象的添加和移出。

**RocketMQ 注册 Broker 到 NameServer 时存储 broker 集群名称。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

主要用于存储不重复对象集合，并能根据对象快速进行删除。

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[HashTable]: https://jpeony.blog.csdn.net/article/details/109698072
[HashMap]: https://jpeony.blog.csdn.net/article/details/110446413
[ConcurrentHashMap]: https://jpeony.blog.csdn.net/article/details/110677912
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70]: /images/20221005/e72569f7228c4c42835336ee4f9de2f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1]: /images/20221005/014485f00f33406a9d75bba3bd3175f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2]: /images/20221005/4d5ea92da9184a9bbf499882da1afa13.png