How Does Java’s HashSet Ensure No Duplicate Elements?

In Java, the Set interface represents an unordered collection that does not allow duplicate elements. The most common implementation is HashSet, which internally wraps a HashMap to store its elements.

Constructors

public HashSet() {
    map = new HashMap<E,Object>();
}
public HashSet(Collection<? extends E> c) {
    map = new HashMap<E,Object>(Math.max((int)(c.size()/.75f) + 1, 16));
    addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

The class declares a transient HashMap<E,Object> map and a static final placeholder object PRESENT used as the map’s value.

add(E e) method

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

The add method delegates to HashMap.put, which in turn calls putVal. The putVal method computes the bucket index from the key’s hash code, creates a new node when the bucket is empty, or traverses the existing chain/tree to detect collisions. If a key with the same hash and equal value already exists, the method returns the existing node without inserting a new one, causing HashSet.add to return false. Thus, attempting to add an element that is already present does not replace the existing element, preserving the set’s uniqueness guarantee.