HashSet source code parsing

1.1 Member Variables

Private TRANSIENT HashMap<E,Object> map; Private static final Object PRESENT = new Object(); private static final Object PRESENT = new Object();Copy the code

1.2 Construction method

    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);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
Copy the code

The constructors are all constructs of the HashMap, including capacity and load factors, and the last one constructs a LinkedHashMap.

1.3 the add operation

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
Copy the code

The add operation is essentially a HashMap put operation, with the element to be added as the HashMap key and an immutable object as the HashMap value. HashMap put (); 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; / / compare hash first, and then compare the if (p.h ash = = hash && ((k = p.k ey) = = 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; } / / compare hash first, and then compare the if (e.h ash = = hash && ((k = e.k ey) = = 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; }Copy the code

If the hashCode of the key is the same and the content of the key is the same, the new value overwrites the old value, so the key cannot be repeated. A HashSet stores keys, so a HashSet cannot be repeated.

HashSet interview questions

2.1 How is a HashSet de-duplicated?

Calculate the position in the bucket based on the object’s hashcode and compare whether hashCode is equal to the hashcode of the existing object. If hashCode is equal, call equals() to determine whether the contents are also equal. If hashCode is equal, it is the same object and will not be inserted.

Third, summary

A HashSet is a collection of keys for a HashMap.