Java Set collections are built on top of Map implementations to enforce their unique-element constraint. Specifically, a Set’s elements are stored as the keys of a underlying Map—since Map keys cannot be duplicated, this inherently preevnts duplicate entries in the Set.

HashSet relies on HashMap for its internal operations, TreeSet uses TreeMap, and LinkedHashSet leverages LinkedHashMap to maintain insertion order alongside uniqueness.

Source Code Analysis

HashSet Source Code Deep Dive:

HashSet uses a HashMap as its backing store, with dummy values since only the keys are relevant for Set functionality.

// Constructors
public HashSet() {
    backingMap = new HashMap<>();
}

public HashSet(int initialCapacity, float loadFactor) {
    backingMap = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    backingMap = new HashMap<>(initialCapacity);
}

// Constructor reserved for LinkedHashSet subclass instantiation
HashSet(int initialCapacity, float loadFactor, boolean dummyFlag) {
    backingMap = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// Adds an element by inserting it as a HashMap key
public boolean add(E element) {
    return backingMap.put(element, DUMMY_VALUE) == null;
}

// Underlying HashMap storage
private transient HashMap<E, Object> backingMap;

// Dummy value used to fill HashMap entries (only keys are used for Set behavior)
private static final Object DUMMY_VALUE = new Object();

// Returns an iterator over the HashMap's key set
public Iterator<E> iterator() {
    return backingMap.keySet().iterator();
}

// Removes an element by deleting the corresponding HashMap entry
public boolean remove(Object obj) {
    return backingMap.remove(obj) == DUMMY_VALUE;
}

LinkedHashSet Source Code:

LinkedHashSet extends HashSet and uses a LinkedHashMap as its backing store by invoking a specialized parent constructor:

// Default constructor
public LinkedHashSet() {
    super(16, 0.75f, true);
}

// Constructor with custom initial capacity
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, 0.75f, true);
}

// Constructor with custom capacity and load factor
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

TreeSet Source Code:

TreeSet uses a NavigableMap (TreeMap by default) to maintain elements in sorted order, again using dummy values for Map entries:

// Default constructor initializes with a TreeMap
public TreeSet() {
    this(new TreeMap<E, Object>());
}

// Constructor with pre-configured NavigableMap
TreeSet(NavigableMap<E, Object> map) {
    this.backingNavMap = map;
}

// Underlying NavigableMap storage
private transient NavigableMap<E, Object> backingNavMap;

// Dummy value for Map entries
private static final Object DUMMY_VALUE = new Object();

// Adds an element as a NavigableMap key
public boolean add(E element) {
    return backingNavMap.put(element, DUMMY_VALUE) == null;
}

// Removes an element by deleting the corresponding NavigableMap entry
public boolean remove(Object obj) {
    return backingNavMap.remove(obj) == DUMMY_VALUE;
}