Java教程

【集合】HashSet 源码分析

本文主要是介绍【集合】HashSet 源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

Github:https://github.com/yihonglei/jdk-source-code-reading

HashTable 源码

HashMap 源码

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);
        }
    }
}

运行结果 

三 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 线程池,工作线程的存储列表。

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

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

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

 

这篇关于【集合】HashSet 源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!