Java 8 容器源码-HashSet

今天开始学习HashSet。HashSet是依赖于HashMap的Set接口的实现，实际上是个HashMap的实例。如果对HashMap源码很熟悉，那么学习HashSet就会很简单了。HashSet的特点是不保证set的迭代顺序，特别是它不保证该顺序恒久不变，允许使用null 元素。本文将从数据结构、实现原理、源码等多个方面详细讲解HashSet。

数据结构

HashSet是依赖于HashMap的。所以HashSet的数据结构也是哈希表+链表+红黑树。

HashSet是依赖于HashMap的。这点可以从源码中很清楚地看出来。

                private transient HashMap<E,Object> map;
            
                /*
                 * 构造方法之一，其他几个构造方法也是类似的。
                 */
                public HashSet() {
                    map = new HashMap<>();
                }

顶部注释

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此set进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

注意，此实现不是同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须保持外部同步。这通常是通过对自然封装该set的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该set进行意外的不同步访问：
Set s = Collections.synchronizedSet(new HashSet(…));

此类的 iterator 方法返回的迭代器是fail-fast的：在创建迭代器之后，如果对set进行修改，除非通过迭代器自身的 remove 方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来在某个不确定时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器在尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测 bug。

此类是 Java Collections Framework 的成员。

定义

public class HashSet extends AbstractSet implements Set , Cloneable, java.io.Serializable

从中我们可以了解到：

HashSet ：TreeMap存储的是元素。
extends AbstractSet ：继承了AbstractSet，实现Set接口时需要实现的工作量大大减少了。
implements Set ：实现了Set，实现了Set中声明的操作set的基本方法。
implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
implements Serializable：表明该类是可以序列化的。

下图是HashSet的类结构层次图。

域

                /**
                 * 说明HashSet是依赖于HashMap的，底层就是一个HashMap实例。
                 */
                private transient HashMap<E,Object> map;
                /**
                 * 前面讲了，HashSet是依赖于HashMap的，底层就是一个HashMap实例。HashMap是保存键值对的，但我们保存hashSet的时候肯定只是想保存key，那么调用hashMap(key,value)时value应该传什么值呢？PRESENT就是value。
                 */
                private static final Object PRESENT = new Object();

构造方法

HashSet有5种构造方法：

public HashSet()：构造一个新的空set，其底层HashMap实例的默认初始容量是 16，加载因子是0.75。
public HashSet(Collection<? extends E> c)：构造一个包含指定集合c中的元素的新set。使用默认的加载因子0.75和足以包含指定指定集合c中所有元素的初始容量来创建HashMap。
public HashSet(int initialCapacity, float loadFactor)：构造一个新的空set，其底层HashMap实例具有指定的初始容量initialCapacity和指定的加载因子loadFactor。
HashSet(int initialCapacity)：构造一个新的空set，其底层HashMap实例具有指定的初始容量initialCapacity和默认的加载因子（0.75）。
HashSet(int initialCapacity, float loadFactor, boolean dummy)：构造一个新的空set。这个构造方法仅仅被LinkedHashSet使用。

源码这里就不展示了，从源码中可以看到，HashSet完全依赖于HashMap，几乎么有自己的东西。

也不作总结了，主要的点都在文章开头和【顶部注释】中。

阅读全文