HashSet源码分析

HashSet是一个HashMap的一个实例，它不保证它的元素们的相对顺序始终是一样的。它也允许null元素的存在。和其他的集合一样，它也是线程不安全，具有fail-fast机制的。

private transient HashMap<E,Object> map;

// 这里构造了一个虚拟的对象来充当HashMap中的value值。
//这个对象是用final修饰的，所以这个value值也是保持不变的
private static final Object PRESENT = new Object();
复制代码

上面是它的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);
}

复制代码

上面是4种构造本类实例的方法。

public Iterator<E> iterator() {
    return map.keySet().iterator();
}
复制代码

HashSet的迭代器也是来自HashMap。从这里可以看出HashSet中的元素其实是HashMap中的key的集合，因为该迭代器就是遍历的HashMap的key集合。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}复制代码

上面是他的add方法。从这里也可以看出value就是用这个虚拟的对象来充当的。

其他的方法也都是基于HashMap来实现的。

另外，HashSet是怎么保证元素不重复的呢？因为它的add方法其实就是HashMap的put方法实现的，所以它的这个性质也是由这个方法来保证的。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;

        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}复制代码

上面就是底层方法的实现，说明下期中一些变量的作用。p节点是用来接收集合中的第一个元素以及利用它来调用next来遍历集合中的其他元素，而e节点则是来接收p节点。用K k来接收集合中元素的key值。

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;复制代码

从上面这段代码可以看出先是比较集合中的元素的hash值是否与要添加的元素的hash值相等，以及他们的key是否相等（此处是用==来判断的）；然后用元素的equals方法比较key值是否相等。如果条件成立则把p节点赋给e节点，此时说明要加入的元素的hash值与集合中的一个元素的hash值相等了，也就是说对于key有了相同的映射。今儿判断e是否为null，若不为null，就把集合中的这个元素的value值赋给oldValue作为返回值，然后把要添加的元素的value值赋给e节点。

从上面的分析可以看出它是怎么保证元素的不重复的性质，也知道了其实HashMap本身的元素们也是具有不重复的性质的。

Set<String> set = new HashSet();
set.add(null);
set.add("null");
System.out.println(set);//[null, null]复制代码

最后发现了一个有趣的地方。