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.集合中的元素不会重复