摘要
前面两篇博文，博主分别为小伙伴们分享了JDK1.7/1.8的HashMap底层原理；本篇博文将继续为大家分享HashSet底层源码；由于HashSet实现较为简单，博主这里只基于JDK1.8进行分享；
介绍
这个类实现了由哈希表(实际上是HashMap实例)支持的Set接口。 它不保证集合的迭代顺序; 特别是，它不能保证顺序会随着时间的推移保持不变。 这个类允许使用空元素。
这个类为基本操作(添加、删除、包含和大小)提供了恒定的时间性能，前提是哈希函数将元素适当地分散到存储桶中。 遍历这个集合所需的时间与HashSet实例的大小(元素的数量)加上后面的HashMap实例的“容量”(桶的数量)的总和成正比。 因此，如果迭代性能很重要，那么初始容量不要设置得太高(或者负载因子太低)是非常重要的。
注意，这个实现不是同步的。 如果多个线程同时访问一个hash set，并且至少有一个线程修改了该散列集，那么它必须在外部进行同步。 这通常通过对自然封装该集合的某些对象进行同步来完成。 如果不存在这样的对象，则应该使用Collections.synchronizedSet方法“包装”。 这最好在创建时完成，以防止意外的对集合的非同步访问: Set s = Collections.synchronizedSet(new HashSet(...));
这个类的迭代器方法返回的迭代器是快速失败的:如果在迭代器创建后的任何时间修改了集合，除了通过迭代器自己的remove方法之外的任何方式，迭代器都会抛出ConcurrentModificationException。 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是冒着在未来某个不确定的时间发生任意的、不确定的行为的风险。请注意，迭代器的快速失败行为不能得到保证，因为一般来说，在存在非同步的并发修改时，不可能做出任何硬保证。 快速失败迭代器尽可能抛出ConcurrentModificationException。 因此，编写依赖此异常来保证其正确性的程序是错误的:迭代器的快速失败行为应该只用于检测错误。
源码解析
(1)、类定义
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
//底层使用HashMap来存数据
private transient HashMap<E,Object> map;
//在后台映射中关联一个对象的虚拟值
private static final Object PRESENT = new Object();
...
}
从上面定义可以看出，HashSet底层是使用HashMap来实现的；并且存数据的时候，HashMap中key就是set中的真实数据对象，HashMap中value的都是虚拟对象PRESENT的引用;
(2)、构造方法
/**
* 构造一个新的空集; 后台HashMap实例具有默认的初始容量(16)和负载因子(0.75)。
*/
public HashSet() {
map = new HashMap<>();
}
/**
* 构造一个包含指定集合中的元素的新集合。 HashMap是用默认的加载因子(0.75)和足够容纳指定集合中的元素的初始容量创建的。
*
* @param C是一个集合，它的元素被放置到这个集合中
* @throws NullPointerException 如果指定的集合为空
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 构造一个新的空集; 后台HashMap实例具有指定的初始容量和指定的负载因子。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* 构造一个新的空集; 后台HashMap实例具有指定的初始容量和默认负载因子(0.75)。
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
* 构造一个新的空的链接哈希集。 (此包私有构造函数仅用于LinkedHashSet。) 后备HashMap实例是一个LinkedHashMap，
* 具有指定的初始容量和指定的加载因子。
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy 忽略(区分这 构造函数来自其他int, float构造函数。)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
由上面的构造方法可以看出，HashSet底层使用的是HashMap，LinkedHashSet底层使用LinkedHashMap来实现。
(3)、iterator方法
/**
* 返回一个遍历该集合元素的迭代器。 返回的元素没有特定的顺序。
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
此处即表明HashSet的集合对象就是Map中的key集合。
(4)、add方法
/**
* 如果指定元素不存在，则将其添加到此集合。
*
* @param e element to be added to this set
* @return 如果此集合尚未包含指定的对象，true
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
将set要存的对象作为key，PRESENT作为value存进底层map中；如果添加之前不包含该key，则返回true；否则，返回false.
(5)、remove方法
/**
* 如果指定元素存在，则从该集合中移除该元素。
*
* @param o object to be removed from this set, if present
* @return 如果集合包含指定的元素，返回true；否则，返回false.
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
总结：
1、以上就是HashSet的核心实现，可以看出，HashSet底层实现是靠HashMap来完成的。LinkedHashSet底层实现是靠LinkedHashMap来完成的。
2、HashSet的集合对象其实就是底层Map中的key的集合，底层Map中所有key映射的value都是同一个Object对象.
3、由于HashSet使用的是Hash定位，所以一般在元素较多，且用于判断元素是否存在的这种场景，使用HashSet的效率会比List效率高出很多。
