[简单集合] HashSet源码分析

1 前言

HashSet是Set的一种实现方式，底层主要使用HashMap来确保元素不重复。

2 源码分析

2.1 属性

   // 内部使用HashMap
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    // 虚拟对象，用来作为value放到map中
    private static final Object PRESENT = new Object();

2.2 构造方法

    public HashSet() {
        map = new HashMap<>();
    }
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
   public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    // 非public，主要是给LinkedHashSet使用的
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

构造方法都是调用HashMap对应的构造方法。

最后一个构造方法有点特殊，它不是public的，意味着它只能被同一个包调用，这是LinkedHashSet专属的方法。

3 总结

• HashSet内部使用HashMap的key存储元素，以此来保证元素不重复
• HashSet是无序的，因为HashMap的key是无序的
• HashSet中允许有一个null元素，因为HashMap允许key为null
• HashSet是非线程安全的
• HashSet是没有get()方法的

4 面试问题

1. 什么是fail-fast？

fail-fast集合是java集合中的一种错误机制。

当使用迭代器迭代时，如果发现集合有修改，则快速失败做出响应，抛出ConcurrentModificationException异常。

这种修改有可能是其它线程的修改，也有可能是当前线程自己的修改导致的，比如迭代的过程中直接调用remove()删除元素。

另外，并不是java中所有的集合都有fail-fast的机制。比如，像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。

那么，fail-fast是怎么实现的？

像ArrayList、HashMap中都有一个属性叫 modCount，每次对集合的修改这个值都会加1，在遍历前记录这个值到 expectedModCount中，遍历中检查两者是否一致，如果出现不一致就说明有修改，则抛出ConcurrentModificationException异常。