Problem 40.8 · Designing Data StructuresEasy

Design HashSet

PatternCombine Structures to Design Hash Map Lookup (Complement)

What it teaches: What's inside a hash set: an array of buckets, a hash function to pick the bucket, and a small list per bucket for collisions.

Practise it on judges as “Design HashSet”.

In plain words

Imagine a cloakroom with 1000 numbered hooks. To store a ticket number, you look at its last three digits and hang it on that hook. To check whether a ticket is stored, you only look at one hook, not all of them. Two tickets can land on the same hook, so each hook holds a short list.

Build a set of whole numbers with add(key), remove(key) and contains(key), without using Java's built-in HashSet.

The problem

Design MyHashSet with add(key), remove(key) and contains(key) for keys 0..10⁶, without built-in hash tables.

Example 1

Input: add(1), add(2), contains(1), contains(3), add(2), contains(2), remove(2), contains(2)
Output: true, false, true, false

Constraints

0 ≤ key ≤ 10⁶
Up to 10⁴ calls

Pattern clues in the wording

→ Implement a hash table yourself

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MyHashSet · starter

import java.util.*;

class MyHashSet {
    public MyHashSet() {}
    public void add(int key) {}
    public void remove(int key) {}
    public boolean contains(int key) { return false; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["MyHashSet","add","add","contains","contains","add","contains","remove","contains"] args = [[],[1],[2],[1],[3],[2],[2],[2],[2]]	[null,null,null,true,false,null,true,null,false]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Buckets with chaining · O(1) average per call 2. Direct-address array · O(1) per call

Buckets with chaining

Time O(1) average per call Space O(n + buckets)

An array of 1009 lists (a prime spreads keys well). add appends if absent, remove deletes, contains searches one bucket.

Approach 1

import java.util.*;

class MyHashSet {
    private static final int BUCKETS = 1009;
    private final List<List<Integer>> table = new ArrayList<>();

    public MyHashSet() {
        for (int i = 0; i < BUCKETS; i++) table.add(new LinkedList<>());
    }

    private List<Integer> bucket(int key) { return table.get(key % BUCKETS); }

    public void add(int key) {
        if (!bucket(key).contains(key)) bucket(key).add(key);
    }

    public void remove(int key) {
        bucket(key).remove(Integer.valueOf(key));            // remove the value, not the index
    }

    public boolean contains(int key) { return bucket(key).contains(key); }
}

Verdict: This is how real hash sets work (plus resizing).

Direct-address array

Time O(1) per call Space O(10⁶)

Keys are at most 10⁶, so a boolean[1_000_001] answers everything in O(1).

▶ Dry run: One true/false slot per key (keys 0–3 shown)add(1), add(2), contains(1), contains(3), add(2), contains(2), remove(2), contains(2)

returned(list)

empty

Step 1/4add(1), add(2): set present[1] and present[2] to true. The array has a slot for every key up to 10⁶.

Approach 2

class MyHashSet {
    private final boolean[] present = new boolean[1_000_001];

    public MyHashSet() {}

    public void add(int key) { present[key] = true; }

    public void remove(int key) { present[key] = false; }

    public boolean contains(int key) { return present[key]; }
}

Verdict: Fastest, but only because the key range is small and known.

Before you submit

Edge cases and common mistakes

Test these inputs

Removing a key that isn't there
Adding the same key twice

Mistakes people make

list.remove(key) with an int removes by index; use Integer.valueOf(key).

Interview

Follow-up questions

What happens when buckets get long?

Command Palette