Understanding Java HashSet: Overview, Constructors, add/remove Methods, Traversal, and Related Set Implementations

HashSet is a commonly used implementation of the Java Set interface, backed by a HashMap; it is frequently asked about in interviews and serves as a practical example of collection design.

The class definition shows that HashSet extends AbstractSet and implements Set, Cloneable, and Serializable:

public class HashSet
extends AbstractSet
implements Set
, Cloneable, java.io.Serializable {}

HashSet provides several overloaded constructors, including a default constructor, a constructor that accepts a Collection, one that specifies initial capacity and load factor, and one that only specifies initial capacity.

private transient HashMap
map;
// default constructor
public HashSet() { map = new HashMap<>(); }
// collection constructor
public HashSet(Collection
c) { map = new HashMap<>(Math.max((int)(c.size()/.75f)+1, 16)); addAll(c); }
// capacity and load factor constructor
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); }
// capacity only constructor
public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); }

The add method delegates to HashMap.put , storing the element as a key with a constant dummy value:

private static final Object PRESENT = new Object();
public boolean add(E e) { return map.put(e, PRESENT) == null; }

The remove method also forwards to HashMap.remove , checking the dummy value to confirm removal:

public boolean remove(Object o) { return map.remove(o) == PRESENT; }

Traversal can be performed using an iterator, as demonstrated by a simple example that prints each element:

public static void main(String[] args) {
    HashSet
set = new HashSet<>();
    set.add("Monday");
    set.add("Tuesday");
    set.add("Wednesday");
    set.add("Thursday");
    set.add("Friday");
    Iterator
it = set.iterator();
    while (it.hasNext()) {
        System.out.println(it.next());
    }
}

Because HashSet relies on HashMap's hashing, its iteration order is not guaranteed to match insertion order.

LinkedHashSet extends HashSet and internally uses a LinkedHashMap to preserve insertion order. Its constructors simply forward to the parent class with a flag that enables ordering:

public class LinkedHashSet
extends HashSet
{
    public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); }
    public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); }
    public LinkedHashSet() { super(16, .75f, true); }
    public LinkedHashSet(Collection
c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); }
    public Spliterator
spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); }
}

TreeSet extends AbstractSet and implements NavigableSet, delegating all its functionality to a TreeMap, which provides sorted order based on natural ordering or a supplied comparator:

public class TreeSet
extends AbstractSet
implements NavigableSet
, Cloneable, java.io.Serializable {
    public TreeSet() { this(new TreeMap
()); }
    public TreeSet(Comparator
comparator) { this(new TreeMap<>(comparator)); }
    public TreeSet(Collection
c) { this(); addAll(c); }
    public TreeSet(SortedSet
s) { this(s.comparator()); addAll(s); }
}

In summary, HashSet is essentially a thin wrapper around HashMap, providing set semantics; LinkedHashSet adds ordering by using LinkedHashMap, and TreeSet offers sorted behavior via TreeMap. Understanding these implementations helps grasp Java's collection framework and its underlying data structures.