基本介绍

HashSet位于java.util包，在JDK1.2引入，属于Collection家族的一员，实现了Set接口，与List所不同的是，其内部元素不能重复，而且不能保证元素添加和遍历的有序性，同样Set允许添加null元素。查看其UML类图：
HashSet.png
HashSet提供了五个构造方法，HashSet的实现利用了Map接口中两个实现类的特性，Map属于K-V结构，要求K可以为null，但是其元素不能重复，而Set也有这一特性，因此HashSet的底层实现使用了HashMap。

构造方法

HashSet中维护了两个比较重要的成员变量，由于HashSet基于HashMap实现，为了维护K-V结构，Map中所有的K均指向一个固定的对象引用PRESENT。

  1. // 用来进行数据存储的HashMap
  2. private transient HashMap<E,Object> map;
  4. // 维护Map中K-V结构的虚拟Value值
  5. private static final Object PRESENT = new Object();

接下来分别对HashSet的构造方法进行分析：

  • HashSet()

    1. // 无参构造，HashSet的初始容量及加载因子基于HashMap而定
    2. public HashSet() {
    3.   map = new HashMap<>();
    4. }

  • HashSet(Collection<? extends E> c)

    1. // 包含了一个Collection实现的有参构造，HashMap的默认初始大小取决于c的大小
    2. // 如果c.size/.75 + 1 < 16，初始容量为16
    3. // 如果c.size/.75 + 1 > 16，初始容量为c.size/.75 + 1
    4. public HashSet(Collection<? extends E> c) {
    5.   map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    6.   addAll(c);
    7. }

  • HashSet(int initialCapacity)

    1. // 指定初始容量的构造方法
    2. public HashSet(int initialCapacity) {
    3.   map = new HashMap<>(initialCapacity);
    4. }

  • HashSet(int initialCapacity, float loadFactor)

    1. // 指定初始容量，及加载因子的构造方法
    2. public HashSet(int initialCapacity, float loadFactor) {
    3.   map = new HashMap<>(initialCapacity, loadFactor);
    4. }

  • HashSet(int initialCapacity, float loadFactor, boolean dummy)

    1. // 需要注意非public修饰，构造一个新的空链接哈希集。 
    2. //（此包私有构造函数仅由 LinkedHashSet 使用。）
    3. // 支持 HashMap 实例是具有指定初始容量和指定负载因子的 LinkedHashMap。
    4. HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    5.   map = new LinkedHashMap<>(initialCapacity, loadFactor);
    6. }

    常用方法

    ```java public boolean add(E e) { return map.put(e, PRESENT)==null; }

public boolean remove(Object o) { return map.remove(o)==PRESENT; }

public void clear() { map.clear(); }

public boolean contains(Object o) { return map.containsKey(o); } ``` HashSet中常用的方法包含add、remove、clear、contains都基于HashMap来实现。

总结

  • HashSet的底层实现基于HashMap，HashMap的K-V结构中，K的集合被维护为HashSet，V通过维护一个统一的固定对象来构造结构。
  • 需要注意的是HashSet并不是线程安全的，如果需要一个线程安全的Set集合，可以通过用Collections.synchronizedSet方法包装该Set集合。
  • 假设哈希函数将元素正确地分散在桶中，迭代这个集合需要的时间与HashSet实例的大小（元素的数量）加上支持HashMap实例的容量（桶的数量）的总和成正比。如果迭代性能很重要，则不要将初始容量设置得太高或负载因子太低。