HashSet

A HashSet is a hash table implementation of the Set interface. It is backed internally by a HashMap instance, using the Set's elements as keys.

Backing HashMap implementation

The internal source code of HashSet reveals its structure:

public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
public HashSet() {
        map = new HashMap<>();
    }
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

Common Pitfalls

• Assuming element sorting: Writing logic that assumes elements are retrieved in the order they were inserted, which breaks on resizing.
• Missing hashCode override: Storing custom objects without overriding hashCode() and equals(), which allows duplicate objects to be stored.

Best Practices

• Override hashCode and equals: Always implement both methods together on elements stored inside HashSet.
• Pre-size backing maps: Provide initial capacities for sets to avoid resizing overhead on large datasets.

Interview-Relevant Information