HashMap & HashSet API

HashSet Core Methods

add, remove, contains (all O(1)), size, isEmpty. Constructors: new HashSet<>(list), new HashSet<>(otherSet), new HashSet<>(Arrays.asList(...)). Set ops: addAll (union), retainAll (intersection), removeAll (difference). Convert back: new ArrayList<>(set).

O(1) average per op

O(n)

say this out loud

I only need membership, not an associated value, so a set. contains at O(1) average is what collapses a nested loop into one pass.

How It Works

HashSet stores unique elements with O(1) average add, remove, and contains. Internally it is a HashMap using elements as keys. add returns false instead of inserting a duplicate, which doubles as a free duplicate detector. Common constructors include new HashSet<>(list) to deduplicate a collection in one step, and new HashSet<>(Arrays.asList(...)) for literals.

The bulk operations implement set algebra in place: addAll is union, retainAll is intersection, and removeAll is difference; convert back with new ArrayList<>(set) when list operations are needed afterward. Membership testing at O(1) is what turns quadratic scans into linear passes, as in Longest Consecutive Sequence, where the set answers 'does num - 1 exist?' instantly.

Step-by-Step Visualization

A list holding 1, 2, 2, 3 with a duplicate in it

size4

1/9

Code

Java

// ─── Constructors ───────────────────────────────────────────
Set<Integer> set = new HashSet<>();
Set<Integer> unique  = new HashSet<>(list);              // dedupe list
Set<Integer> copy    = new HashSet<>(otherSet);          // copy constructor
Set<Integer> fromArr = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> immut   = Set.of(1, 2, 3);                 // immutable, Java 9+

// ─── Core methods, all O(1) average ─────────────────────────
set.add(5);      // true if newly added, false if already present
set.remove(5);   // true if removed, false if not found
set.contains(5); // O(1) lookup. The main reason to use a Set
set.size();      // number of elements
set.isEmpty();   // true if empty

// ─── Set operations (mutate the calling set) ─────────────────
Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> b = new HashSet<>(Arrays.asList(2, 3, 4));
a.addAll(b);     // union        → {1, 2, 3, 4}
a.retainAll(b);  // intersection → {2, 3}
a.removeAll(b);  // difference   → {1}

// ─── Conversions ─────────────────────────────────────────────
List<Integer> backToList = new ArrayList<>(set);        // Set → List
Integer[]     backToArr  = set.toArray(new Integer[0]); // Set → array

// ─── Iteration ───────────────────────────────────────────────
for (int x : set) { System.out.println(x); }
set.forEach(x -> System.out.println(x));

Tips & Gotchas

1new HashSet<>(list) is the fastest way to deduplicate a list

2contains() is O(1). Use a Set instead of List.contains() (which is O(n))

3addAll/retainAll/removeAll mutate the set in-place; use copies if you need originals

4LinkedHashSet preserves insertion order; TreeSet keeps sorted order

Practice Problems

1Contains Duplicate
2Longest Consecutive Sequence
3Intersection of Two Arrays
4Happy Number
5Single Number

About the HashMap & HashSet API Pattern

The complete Java API for HashMap and HashSet. Constructors, every core method, iteration patterns, and set-based conversions. These are your building blocks for every hash-based problem.

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

When should I choose a HashSet instead of a HashMap?

Use a set when you only care about membership. 'have I seen this before?', and a map when each element carries associated data such as a count or index. If you find yourself mapping every key to a dummy value like true, a set is the cleaner choice.

Do retainAll and removeAll modify the set in place?

Yes, both mutate the receiver: retainAll keeps only elements present in the argument (intersection) and removeAll deletes them (difference). Copy the set first with new HashSet<>(original) if the original contents are still needed.

Why does my HashSet of custom objects contain duplicates?

Uniqueness relies on equals and hashCode being consistently overridden; the defaults compare object identity, so two logically equal objects hash differently. Override both together (equal objects must produce equal hash codes) or the set cannot deduplicate them.