HashSet 源码分析-结构

从 HashSet 看源码先看类注释上，我们可以得到的信息有：

1. HashSet 底层是基于 HashMap 实现的，迭代时不保证顺序

2. 由于底层是基于 HashMap 实现的，其 add 方法、remove 方法等，时间复杂度都是 O(1)

3. 线程不安全

4. 迭代过程中如果结构被修改，会失败并抛出异常

其中比较重要的一个点：底层直接使用 HashMap 组合，更加灵活，可以任意的组合现有的其他基础类，并且在已有基础上进行扩展等。

public class HashSet<E>    extends AbstractSet<E>    implements Set<E>, Cloneable, java.io.Serializable{    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;        private static final Object PRESENT = new Object();            ......}

private transient HashMap<E,Object> map; 组合 HashMap，通过调用 HashMap 的基础方法，来复用 HashMap 的能力。

private static final Object PRESENT = new Object(); HashMap 中的 value

初始化

HashSet 的初始化比较简单，初始化方法中是直接 new HashMap

当入参有原始集合数据传入进行初始化的情况下，会对 HashMap 的初始容量进行设置。

public HashSet(Collection<? extends E> c) {    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));    addAll(c);}

new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); 对 HashMap 的容量进行设置，取括号中两个数的最大值（期望的值 / 0.75+1，默认值 16）。

此处和 16 比较大小，如果给定 HashMap 初始容量小于 16 ，就按照 HashMap 默认的 16 初始化，如果大于 16，就按照给定值初始化。

HashMap 扩容的计算公式是：Map 的容量 * 0.75f（扩容因子），一旦达到这个条件就会扩容。HashSet 中用的是 (int) (c.size ()/.75f) + 1 来表示初始化的值，这样使期望的值比扩容的阀值大 1，这样就不会触发扩容。

增加元素

public boolean add(E e) {    return map.put(e, PRESENT)==null;}
public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}

add 方法内部是直接使用 HashMap 的 put 方法，这也是直接使用 HashMap 当做内部元素作为扩展使用的好处。