HashSet 源码分析【面试+工作】

前言

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的目标ID;这时,我们可以使用 HashSet 来存放我们的ID,HashSet可以自动的帮助我们去重,比如HashSet<String> set = new HashSet<>(list) 等。接下来看下 HashSet 的内部是怎么实现的。

HashSet的特点

从 HashSet 的 Javadoc 的说明中,可以得到以下信息:

1. HashSet 底层是使用 HashMap 来保存元素的

2.它不保证集合中存放元素的顺序,即是无序的,且这种顺序可能会随着时间的推移还会改变

3.允许 null 值,且只有一个

4.HashSet 不是线程安全的,底层的 HashMap 不是线程安全的,它自然就不是啦,可以使用 Collections.synchronizedSet(new HashSet()) 来创建线程安全的 HashSet

5.集合中的元素不会重复

类图

先来看看 HashSet 的一个类图

从类图中,可以看到, HashSet 继承了 AbstractSet 抽象类, 而 AbstractSet 又继承了 AbstractCollection 抽象类,此外,HashSet 还实现了 Set 接口等。

AbstractSet 抽象类主要实现了两个方法 equals 和 hashcode 方法,因为 HashSet 中没有重复元素,就是根据这两个方法来进行判断的:

Set 接口,它是一个顶层接口,主要定义了一些公共的方法,如 add, isEmpty, size, remove, contains 等一些方法;HashSet, SortedSet,TreeSet 都实现了该接口。

源码分析

接下来看下它的内部实现,它内部使用 HashMap 来存放元素,它的所有方法基本上都是调用 HashMap 的方法来实现的,相等于对HashMap包装了一层。

从上面声明可看到,HashSet 底层是使用 HashMap 来存放元素的,且 HashMap 中所有元素的 value 都是同一个 Object 对象,且它被 final 修饰。

接下来看下它的方法实现:

以上就是 HashSet 源码的全部实现了,看着很简单,但是要知道 HashMap 的实现过程才会清楚。

HashSet 如何保证元素的不重复

接下来,看下 HashSet 的 add 方法,看下它是如何保证添加的元素不重复的

之后来看下 HashMap 的 put 方法:

put 方法会调用 putVal 方法进行添加元素,来看下 putVal 方法的实现:

所以,在向 HashSet 添加元素的时候,如果要添加元素的 hashcode 已存在,且 equals 相等,则会替换掉旧的值。

以上就是 HashSet 的实现。看起来很简单,但是前提是得知道 HashMap 的实现。

总结

HashSet的特点

1. HashSet 底层是使用 HashMap 来保存元素的

2.它不保证集合中存放元素的顺序,即是无序的,且这种顺序可能会随着时间的推移还会改变

3.允许 null 值,且只有一个

4.HashSet 不是线程安全的,底层的 HashMap 不是线程安全的,它自然就不是啦,可以使用 Collections.synchronizedSet(new HashSet()) 来创建线程安全的 HashSet

5.集合中的元素不会重复

原文发布于微信公众号 - Java帮帮(javahelp)

原文发表时间:2018-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

二叉堆

容易证明: 一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。 这就意味着,完全二叉树的高是[logN] 特点: 任意位置i: 左儿子在位置2i上,...

21280
来自专栏大数据钻研

Java 集合框架 ArrayList 源码剖析

总体介绍 ArrayList实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余...

360120
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

240100
来自专栏marsggbo

链表、头指针、头结点

 图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针 指示链表中第一个结点(即第一个数据元素...

24670
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11140
来自专栏IMWeb前端团队

ES6 Set

本文作者:IMWeb kurtshen 原文出处:IMWeb社区 未经同意,禁止转载 ES6 Set ES6 新增了几种集合类型,本文主要介绍Set以...

18670
来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19290
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

7310
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

29370
来自专栏从流域到海域

《数据结构》 循环链表和双向链表常用操作代码集合

Ps:每段代码中,添加了署名Solo的代码为博主本人所写,其余来自课本或者老师。 大量操作等同于单链表。重复的操作不再贴出,可以查看之前的博文。 循环链表 //...

20070

扫码关注云+社区

领取腾讯云代金券