5.8 HashSet

1. What Is It?

An unordered, non-duplicating collection implemented using HashMap.

2. How to Use It

public class HashSetTest
{
    public static void main(String[] args)
    {
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.remove(2);
        System.out.println(set.contains(1));
        System.out.println(set.contains(2));
        System.out.println(set.contains(3));
    }

}

3. Source-Code Analysis

3.1. UML

Serializable and cloneable.

3.2. Constructor

public HashSet() {
    // Implemented using HashMap.
    map = new HashMap<>();
}

3.3. Fields

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // Uses a map underneath.
    private transient HashMap<E,Object> map;
    // Placeholder used as the value.
    private static final Object PRESENT = new Object();
}

3.4. add Method

Efficiency is O(1).

public boolean add(E e) {
    // Use e as the map key and PRESENT as the value.
    return map.put(e, PRESENT)==null;
}

3.5. contains Method

Efficiency is O(1).

public boolean contains(Object o) {
    // Call HashMap's containsKey method.
    return map.containsKey(o);
}

3.6. remove Method

Efficiency is O(1).

 public boolean remove(Object o) {
 // Call HashMap's remove method.
    return map.remove(o)==PRESENT;
}

4. Summary

HashSet is implemented using HashMap underneath, with new Object() used as the value placeholder.