HashSet

A HashSet stores unique elements only. Try adding duplicates and see what happens!

HashSet Operations

Value

Enter a value and click Add

Size: 0

Capacity: 8

Index	Elements
0	(empty)
1	(empty)
2	(empty)
3	(empty)
4	(empty)
5	(empty)
6	(empty)
7	(empty)

HashSet Properties

• No duplicates - adding an existing element does nothing
• O(1) average for add, remove, contains
• Unordered - iteration order is not guaranteed
• Implemented using HashMap internally (element → dummy value)

HashSet = HashMap Wrapper

Internally, a HashSet uses a HashMap where:

• The element is stored as the key
• A dummy constant is stored as the value

// HashSet internally
set.add("apple")
↓
map.put("apple", PRESENT)

This is why HashSet operations have the same O(1) average time complexity.

Java Implementation

add()

public boolean add(E element) {
    // HashSet uses HashMap internally
    // Stores element as key, dummy value as value
    return map.put(element, PRESENT) == null;
}

contains()

public boolean contains(E element) {
    return map.containsKey(element);
}

remove()

public boolean remove(E element) {
    return map.remove(element) == PRESENT;
}

Common Use Cases

1. Remove Duplicates

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> unique = new HashSet<>(list);
// unique = {1, 2, 3}

2. Membership Testing

Set<String> visited = new HashSet<>();
if (!visited.contains(node)) {
    visited.add(node);
    // process node
}

3. Find Common Elements

Set<Integer> set1 = new HashSet<>(list1);
Set<Integer> set2 = new HashSet<>(list2);
set1.retainAll(set2); // intersection

4. Count Unique Items

Set<String> words = new HashSet<>();
for (String word : document) {
    words.add(word);
}
int uniqueCount = words.size();

HashSet vs TreeSet vs LinkedHashSet

Feature	HashSet	TreeSet	LinkedHashSet
Ordering	None	Sorted	Insertion order
add/remove/contains	O(1)	O(log n)	O(1)
Implementation	HashMap	Red-Black Tree	HashMap + LinkedList