10.HashSet源码解析

1.类注释

1. HashSet的底层实现基于HashMap，因此迭代时不能保证按照插入顺序进行迭代。
2. HashSet的add、remove、contanins、size等方法的耗时性能，不会随着数据量的增加而增加，原因跟HashMap底层的数组数据结构有关，不管数据量多大，不考虑hash冲突的情况下，时间复杂度都是O(1)。
3. HashSet是线程不安全的，如果需要安全请自行加锁，或者使用Collections的synchronizedSet方法。
4. 迭代过程中，如果数据结构被改变，会快速失败，会抛出 ConcurrentModificationException异常。

2.实现方式

从类注释中看到，HashSet的实现是基于HashMap的，在Java中，要基于基础类进行创新实现，有两种办法。一是继承基础类，覆写基础类的方法，比如说继承HashMap , 覆写其add方法。另一种方法是组合基础类，通过调用基础类的方法，来复用基础类的能力。

HashSet使用的是后者，通过组合HashMap，来使用其提供的功能，其优点主要有如下两点。首先，继承表示父子类是同一个事物，而Set和Map表达的是两种事物，所以继承不妥，而且Java语法限制，子类只能继承一个父类，后续难以扩展。其次，组合更加灵活，可以任意的组合现有的基础类，并且可以在基础类的方法基础上进行扩展、编排等，而且方法命名相对灵活，无需和基础类的方法名称保持一致，具体实现源码如下所示。

源码

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    //把HashMap组合进来，key是Hashset的key，value是下面的PRESENT
    private transient HashMap<E,Object> map;
    
    //HashMap中的value
    private static final Object PRESENT = new Object();
}      

源码解析

1. 在使用HashSet时，比如add方法，只有一个入参，但组合的Map的add方法却有key和value两个入参，对应上Map的话，key就是add的入参，value就是第二行代码中的PRESENT，此处设计非常巧妙，用一个默认值PRESENT来代替Map的Value。
2. 如果HashSet是被共享的，当多个线程访问的时候，就会有线程安全问题，因为后续的所有操作中，并没有加锁。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    //对HashMap的容量进行计算
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    public boolean add(E e) {
    //直接使用HashMap的put方法，进行一些简单的逻辑判断
        return map.put(e, PRESENT)==null;
    }
}      

1. Math.max((int)(c.size() / .75f) + 1 , 16)，是对HashMap的容量进行了计算，翻译成中文就是取括号中两个数的最大值(期望的值 / 0.75 + 1，默认值是16)。从计算中可以看出HashSet的实现者对HashMap的底层实现是非常清楚的，主要体现在两个方面，和16比较大小的意思是说，如果给定HashMap初始容量小于16 ，就按照HashMap默认的16初始化即可，如果大于16，就按照给定值进行初始化。
2. HashSet的其他方法就相对简单了，就是对Map的API进行了一些包装，如上述的add方法。