介绍
在往期文章中，我们从源码层面详细分析了java集合框架中List的实现如ArrayList、LinkedList、Vector，Queue的实现如PriorityQueue、ArrayDeque，Map的实现如HashMap、TreeMap、LinkedHashMap、HashTable。他们有各自的底层实现和不同的特点。
今天开始，我们进入java集合框架的新篇——Set，先看一下jdk对Set的定义是什么
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.
翻译：不包含重复元素的集合。更正式地说，集合不包含e1.equals(e2)这样的元素对e1和e2，最多包含一个空元素。
从Set的定义我们了解到
- Set集合中的元素不允许重复，且元素是否重复是通过元素的
equals()方法判断的。 - Set集合中最多包含一个空元素。这其实是取决于它的底层实现。
再看一下Set有哪些实现类供我们使用，下面是Set的UML类图
Set的主要实现有三个：TreeSet、HashSet、LinkedHashSet，今天我们先从HashSet入手，从源码层面详细分析它的实现原理。下面我们把上面Set类图中与HashSet无关的类去掉，把注意力放在HashSet上。而在学习HashSet源码之前，必须对HashMap的源码了如指掌。
类的声明
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
从类的声明和上面的UML类图中可以了解到：
- 继承AbstractSet抽象类，对其进行了扩展。
- 实现了Set接口，表示它是一个Set集合，满足Set集合的定义
- 实现了Cloneable接口，提供了对象克隆方法，但请注意，是浅克隆。
- 实现了Serializable接口，支持序列化。
成员变量
// HashSet的底层使用哈希表作为存储结构，
// 而HashMap已经实现了哈希表，因此HashSet无需再次对哈希表进行实现，直接通过HashMap对哈希表进行数据的存取即可。
private transient HashMap<E,Object> map;
// 虽然HashSet使用HashMap来操作哈希表，
// 但是HashMap存储的是<key,value>键值对，
// 因此HashSet在保存数据时，key为实际保存的数据，使用一个固定的对象PRESENT作为假的value值
private static final Object PRESENT = new Object();
构造函数
HashSet提供了四个构造函数，由于HashSet的底层为HashMap，因此在HashSet的构造方法中，都是先实例化一个HashMap对象。
无参构造
直接调用HashMap的无参构造来实例化一个HashMap对象。
public HashSet() { map = new HashMap<>(); }通过传入一个集合构造
先调用HashMap的
HashMap(int initialCapacity)构造方法来实例化HashMap对象，再通过putAll()方法将集合中的元素添加到当前实例中。public HashSet(Collection<? extends E> c) { // HashMap的默认初始容量为16， // (int) (c.size()/.75f) + 1 是通过传入的集合中元素的数量 除以 0.75，将所得的商+1， // 从两个数中取最大值是为了避免底层哈希表的频繁扩容。在HashMap中我们有聊过这个逻辑。 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); // 将集合中的元素批量保存 addAll(c); }通过初始容量和加载因子实例化
可以看到，其实还是调用了HashMap对应的构造方法，对HashMap的实例指定了初始容量和加载因子
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); }通过初始容量实例化
调用了HashMap对应的构造方法，对HashMap的实例指定了初始容量
public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); }
另外还有一个构造方法，该方法没有被public关键字修饰，即默认的修饰符，因此只能被同一个包内的子类调用。而且该构造方法的第三个boolean参数dummy并没有被使用，只有另外两个参数初始容量和加载因子被使用了，因此可以判断该参数的作用是为了与上面public HashSet(int initialCapacity, float loadFactor)构造方法做区分用的。另外我们还发现，该构造方法内部实例化的不是HashMap对象而是LinkedHashMap对象，是因为该构造方法是由Set的另一个实现LinkedHashSet调用的，简单说一下，LinkedHashSet的底层实现为HashSet，和HashSet同包，且为HashSet的子类。所以，该构造函数是为了实例化LinkedHashSet对象而来的。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
常用方法
因为HashSet是通过HashMap来操作其底层的哈希表的，因此我们对HashSet中数据的存取都是通过调用HashMap提供的方法实现的。
size()
直接调用HashMap的
size()方法public int size() { return map.size(); }isEmpty()
直接调用HashMap的
isEmpty()方法public boolean isEmpty() { return map.isEmpty(); }contains()
直接调用HashMap的
contains()方法public boolean contains(Object o) { return map.containsKey(o); }add()
直接调用HashMap的
add()方法public boolean add(E e) { return map.put(e, PRESENT)==null; }addAll()
调用父类
AbstractCollection的allAll()方法，就是对集合进行遍历并调用add()方法保存元素public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; }remove()
直接调用HashMap的
remove()方法public boolean remove(Object o) { return map.remove(o)==PRESENT; }clear()
直接调用HashMap的
clear()方法public void clear() { map.clear(); }
总结
- HashSet的底层实现为HashMap，HashMap的底层实现为哈希表，因此HashSet的底层实现为哈希表
- 元素不允许重复，且元素是否重复是通过元素的
equals()方法判断的。 - 线程不安全
纸上得来终觉浅，绝知此事要躬行。
————————————————我是万万岁，我们下期再见————————————————
